8 ENG1507 Método de Inserção do Ponto Mais Distante

Prévia do material em texto

MÉTODO DE INSERÇÃO 
DO PONTO MAIS 
DISTANTE 
TRANSLOG 
A heurística da inserção mais distante contrapõe a do vizinho 
mais próximo por inserir cidades na solução final de forma a 
não gerar cruzamentos de rotas. O algoritmo inicia com uma 
sub-rota que só contém o ponto de origem. Para cada ponto k 
que não esteja na rota, é calculada a distância mínima entre k 
e todos os pontos que estejam na rota, e armazenada a menor 
distância, que chamaremos min_dist(k). Depois, é escolhido o 
ponto, tal que min_dist(k) seja máxima. Finalmente, o local de 
inserção de k na sub-rota atual é dada pelo par de vértices i e 
j, ligando k na forma (i,k) e (k,j), minimizando (Cik+Ckj – Cij). 
A aplicação do algoritmo produz uma solução que é iniciada 
pelas pontas, como se fosse uma corda em círculo que é 
esticada primeiramente nas pontas e depois levada até os 
pontos interiores. Esta forma de atuação permite que o 
algoritmo não produza cruzamentos, se o problema respeitar a 
desigualdade do triângulo. 
 
MÉTODO DE INSERÇÃO DO PONTO MAIS DISTANTE 
TRANSLOG 
8 
7 
6 
5 
4 
3 
2 
1 
D 
1 2 3 4 5 6 7 8 D 
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2 
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3 
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5 
4 - - - - 43,3 70,5 44,3 94,3 120,5 
5 - - - - - 42,1 42,9 70,3 108,2 
6 - - - - - - 35,6 28,3 68,6 
7 - - - - - - - 52,5 76,5 
8 - - - - - - - - 43,5 
De acordo com a 
matriz de distâncias 
euclidianas a seguir, 
determine o 
comprimento do 
roteiro otimizado de 
distribuição de 
carga pelo método 
de inserção do ponto 
mais distante. O 
fator de correção 
da métrica 
euclidiana para essa 
região é de 25%. 
TRANSLOG 
1 2 3 4 5 6 7 8 D 
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2 
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3 
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5 
4 - - - - 43,3 70,5 44,3 94,3 120,5 
5 - - - - - 42,1 42,9 70,3 108,2 
6 - - - - - - 35,6 28,3 68,6 
7 - - - - - - - 52,5 76,5 
8 - - - - - - - - 43,5 
Para os pontos 1,3,4,5,6,7 e 8 são calculadas as distâncias mínimas entre cada um 
deles e os pontos D e 2 que estão na rota, e armazenada a menor distância, que 
chamaremos min_dist(k). Depois, é escolhido o ponto, tal que min_dist(k) seja 
máxima. 
min_dist(1) : 1-2=65,0 
min_dist(3) : 3-2=54,9 
min_dist(4) : 4-2= 34,1 
min_dist(5) : 5-2=62,8 
min_dist(6) : 6-D=68,6 
min_dist(7) : 7-D=76,5 
min_dist(8) : 8-D=43,5 
8 
7 
6 
5 
4 
3 2 
1 
D 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-2-D 
D-7-2-D 
TRANSLOG 
1 2 3 4 5 6 7 8 D 
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2 
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3 
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5 
4 - - - - 43,3 70,5 44,3 94,3 120,5 
5 - - - - - 42,1 42,9 70,3 108,2 
6 - - - - - - 35,6 28,3 68,6 
7 - - - - - - - 52,5 76,5 
8 - - - - - - - - 43,5 
8 
7 
6 
5 
4 
3 2 
1 
D 
min_dist(1) : 1-2=65,0 
min_dist(3) : 3-2=54,9 
min_dist(4) : 4-2= 34,1 
min_dist(5) : 5-7=42,9 
min_dist(6) : 6-7=35,6 
min_dist(8) : 8-D=43,5 8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-2-D 
D-7-2-1-D 
TRANSLOG 
1 2 3 4 5 6 7 8 D 
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2 
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3 
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5 
4 - - - - 43,3 70,5 44,3 94,3 120,5 
5 - - - - - 42,1 42,9 70,3 108,2 
6 - - - - - - 35,6 28,3 68,6 
7 - - - - - - - 52,5 76,5 
8 - - - - - - - - 43,5 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-2-1-D 
min_dist(3) : 3-2=54,9 
min_dist(4) : 4-2= 34,1 
min_dist(5) : 5-1=30,7 
min_dist(6) : 6-7=35,6 
min_dist(8) : 8-D=43,5 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-3-2-1-D 
TRANSLOG 
1 2 3 4 5 6 7 8 D 
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2 
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3 
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5 
4 - - - - 43,3 70,5 44,3 94,3 120,5 
5 - - - - - 42,1 42,9 70,3 108,2 
6 - - - - - - 35,6 28,3 68,6 
7 - - - - - - - 52,5 76,5 
8 - - - - - - - - 43,5 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-3-2-1-8-D 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-3-2-1-D 
min_dist(4) : 4-2= 34,1 
min_dist(5) : 5-1=30,7 
min_dist(6) : 6-7=35,6 
min_dist(8) : 8-D=43,5 
TRANSLOG 
1 2 3 4 5 6 7 8 D 
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2 
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3 
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5 
4 - - - - 43,3 70,5 44,3 94,3 120,5 
5 - - - - - 42,1 42,9 70,3 108,2 
6 - - - - - - 35,6 28,3 68,6 
7 - - - - - - - 52,5 76,5 
8 - - - - - - - - 43,5 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-3-2-1-8-D 
min_dist(4) : 4-2= 34,1 
min_dist(5) : 5-1=30,7 
min_dist(6) : 6-8=28,3 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-3-4-2-1-8-D 
TRANSLOG 
min_dist(5) : 5-1=30,7 
min_dist(6) : 6-8=28,3 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-3-4-2-1-8-D 1 2 3 4 5 6 7 8 D 
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2 
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3 
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5 
4 - - - - 43,3 70,5 44,3 94,3 120,5 
5 - - - - - 42,1 42,9 70,3 108,2 
6 - - - - - - 35,6 28,3 68,6 
7 - - - - - - - 52,5 76,5 
8 - - - - - - - - 43,5 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-3-4-2-1-5-8-D 
TRANSLOG 
min_dist(6) : 6-8=28,3 
8 
7 
6 
5 
4 
3 2 
1 
D 
1 2 3 4 5 6 7 8 D 
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2 
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3 
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5 
4 - - - - 43,3 70,5 44,3 94,3 120,5 
5 - - - - - 42,1 42,9 70,3 108,2 
6 - - - - - - 35,6 28,3 68,6 
7 - - - - - - - 52,5 76,5 
8 - - - - - - - - 43,5 
8 
7 
6 
5 
4 
3 2 
1 
D 
D-7-3-4-2-1-5-8-D 
D-7-3-4-2-1-5-6-8-D 
TRANSLOG 
1 2 3 4 5 6 7 8 D 
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2 
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3 
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5 
4 - - - - 43,3 70,5 44,3 94,3 120,5 
5 - - - - - 42,1 42,9 70,3 108,2 
6 - - - - - - 35,6 28,3 68,6 
7 - - - - - - - 52,5 76,5 
8 - - - - - - - - 43,5 
8 
7 
6 
5 
4 
3 2 
1 
D 
Resp: 
(43,5+28,3+42,1+30,7+65,0+34,1+40,7+ 
+64,8+76,5)km=425,7km 
TRANSLOG 
Exercício Proposto 
 
1 2 
3 4 5 6 D 
1 51,82 28,62 79,68 81,79 111,19 50,86 
2 34,32 68,49 89,61 96,75 100,32 
3 53,67 63,70 85,34 78,95 
4 31,70 31,70 125,22 
5 44,84 117,88 
6 155,30 
De acordo com a matriz de distâncias euclidianas a 
seguir, determine o comprimento do roteiro 
otimizado de distribuição de carga pelo método de 
inserção do ponto mais distante. O fator de 
correção da métrica euclidiana para essa região é 
de 25%. 
TRANSLOG Roteirização de Veículos 
D 
100 
100 
50 
50 
25 
25 
75 
75 
1 
2 
3 
4 
5 
6 
TRANSLOG 
D 
1 
2 
3 
4 
5 
6 
 1 2 3 4 5 6 D 
1 51,82 28,62 79,68 81,79 111,19 50,86 
2 34,32 68,49 89,61 96,75 100,32 
3 53,67 63,70 85,34 78,95 
4 31,70 31,70 125,22 
5 44,84 117,88 
6 155,30 
min_dist(1) : 1-D=50,86 
min_dist(2) : 2-6= 96,75 
min_dist(3) : 3-D=78,95 
min_dist(4) : 4-6=31,70 
min_dist(5) : 5-6=44,84 
D 
1 
2 
3 
4 
5 
6 
TRANSLOG 
 1 2 3 4 5 6 D 
1 51,82 28,62 79,68 81,79 111,19 50,86 
2 34,32 68,49 89,61 96,75 100,32 
3 53,67 63,70 85,34 78,95 
4 31,70 31,70 125,22 
5 44,84 117,88 
6 155,30 
min_dist(1) : 1-D=50,86 
min_dist(3) : 3-2=34,32 
min_dist(4) : 4-6=31,70 
min_dist(5) : 5-6=44,84 
D 
1 
2 
3 
4 
5 
6 
D 
1 
2 
3 
4 
5 
6 
TRANSLOG 
 1 2 3 4 5 6 D 
1 51,82 28,62 79,68 81,79 111,19 50,86 
2 34,32 68,49 89,61 96,75 100,32 
3 53,67 63,70 85,34 78,95 
4 31,70 31,70 125,22 
5 44,84 117,88 
6 155,30 
min_dist(3) : 3-1=28,62 
min_dist(4) : 4-6=31,70 
min_dist(5) : 5-6=44,84 
D 
1 
2 
3 
4 
5 
6 
D 
1 
2 
3 
4 
5 
6 
TRANSLOG 
 1 2 3 4 5 6 D 
1 51,82 28,62 79,68 81,79 111,19 50,86 
2 34,32 68,49 89,61 96,75 100,32 
3 53,67 63,70 85,34 78,95 
4 31,70 31,70 125,22 
5 44,84 117,88 
6 155,30 
min_dist(3) : 3-1=28,62 
min_dist(4) : 4-6=31,70 
D 
1 
2 
3 
4 
5 
6 
D 
1 
2 
3 
4 
5 
6 
TRANSLOG 
 1 2 3 4 5 6 D 
1 51,82 28,62 79,68 81,79 111,19 50,86 
2 34,32 68,49 89,61 96,75 100,32 
3 53,67 63,70 85,34 78,95 
4 31,70 31,70 125,22 
544,84 117,88 
6 155,30 
min_dist(3) : 3-1=28,62 
D 
1 
2 
3 
4 
5 
6 
D 
1 
2 
3 
4 
5 
6 
TRANSLOG 
 1 2 3 4 5 6 D 
1 51,82 28,62 79,68 81,79 111,19 50,86 
2 34,32 68,49 89,61 96,75 100,32 
3 53,67 63,70 85,34 78,95 
4 31,70 31,70 125,22 
5 44,84 117,88 
6 155,30 
D 
1 
2 
3 
4 
5 
6 
Roteiro(D-1-3-2-4-6-5-D)=(50,86+28,62+34,32+68,49+31,70+44,84+117,88)km= 
 =376,71km 
Com o ajuste da métrica euclidiana tem-se: 
 
Roteiro(D-1-3-2-4-6-5-D) ajustado=376,71km x1,25=470,88km