Roteirizacao de Entregas - Encontre a Rota Minima

Roteirização de entregas Rota Minima Problema Suponha a malha viária desenhada a seguir Na mesma estão indicados alfabeticamente pontos possíveis de parada Um caminhão deve sair do ponto A e fazer entrega no ponto N percorrendo a malha viária descrita Qual o percurso que o caminhão deve fazer saindo da origem e chegando ao destino percorrendo a menor distância possível para a entrega A distância entre dois nós está indicada no ramo que liga os nós O sentido entre dois nós está indicada pela seta que liga os nós A figura 1 é o grafo representativo pictórico da malha viária Figura 01 Grafo da malha viária Precisamos sair de A e chegar em N mas não precisamos necessariamente passar por todos os nós origem destino A B C D E F G H I J K L M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 0 3 4 5 6 7 9 9 10 12 12 12 13 17 Marcamos no nó A qual a distância que possui em relação à origem Como a distância é 0 marcamos 0 em A conforme a figura 2 no passo 01 Figura 2 Grafo da malha viária passo 01 origem destino A 0 B C D E F G H I J K L M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto B e a distância B do ponto à origem Como a distância é 3 marcamos 3 em B conforme a figura 3 no passo 02 Figura 3 Grafo da malha viária passo 02 origem destino A 0 B 3 C D E F G H I J K L M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto C e a distância C do ponto à origem Como a distância é 4 marcamos 4 em C conforme a figura 4 no passo 03 Figura 4 Grafo da malha viária passo 03 origem destino A 0 B 3 C 4 D E F G H I J K L M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto D e a distância D do ponto à origem Como a distância é 5 marcamos 5 em D conforme a figura 5 no passo 04 Figura 5 Grafo da malha viária passo 04 origem destino A 0 B 3 C 4 D 5 E F G H I J K L M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto F e a distância F do ponto à origem Como a distância de B até F é 3 e B já está à distância 3 marcamos 6 em F conforme a figura 6 no passo 05 Figura 6 Grafo da malha viária passo 05 origem destino A 0 B 3 C 4 D 5 E F 6 G H I J K L M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto E e a distância E do ponto à origem Como a distância de B até E é 4 e B já está à distância 3 marcamos 7 em E conforme a figura 7 no passo 06 Figura 7 Grafo da malha viária passo 06 origem destino A 0 B 3 C 4 D 5 E 7 F 6 G H I J K L M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto G e a distância G do ponto à origem Como a distância de C até G é 5 e C já está à distância 4 marcamos 9 em G Analogamente como a distância entre D e G é 4 e D já está à distância 5 marcamos 9 em G Marcamos o ponto J e a distância J do ponto até a origem Como a distância de J até F é 3 e F já está a distância 6 marcamos 9 em J A figura 8 passo 07 mostra isso Figura 8 Grafo da malha viária passo 07 origem destino A 0 B 3 C 4 D 5 E 7 F 6 G 9 H I J 9 K L M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto I e a distância I do ponto à origem Como a distância de I até E é 3 e E já está à distância 7 marcamos 10 em I Analogamente como a distância entre I e F é 4 e D já está à distância 6 marcamos 10 em I A figura 9 passo 08 mostra isso Figura 9 Grafo da malha viária passo 08 origem destino A 0 B 3 C 4 D 5 E 7 F 6 G 9 H I 10 J 9 K L M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto L e a distância L do ponto à origem Como a distância de L até J é 3 e J já está à distância 9 marcamos 12 em L Analogamente como a distância entre K e D é 7 e D já está à distância 5 marcamos 12 em K Análogamente como a distância entre H e D é 7 e D já está à distância 5 marcamos 12 em H A figura 11 passo 09 mostra isso Figura 11 Grafo da malha viária passo 09 origem destino A 0 B 3 C 4 D 5 E 7 F 6 G 9 H 12 I 10 J 9 K 12 L 12 M N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto M e a distância M do ponto à origem Como a distância de M até J é 4 e J já está à distância 9 marcamos 13 em M A figura 12 passo 10 mostra isso Figura 12 Grafo da malha viária passo 10 origem destino A 0 B 3 C 4 D 5 E 7 F 6 G 9 H 12 I 10 J 9 K 12 L 12 M 13 N 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6 Quem está à menor distância da origem A Marcamos o ponto N e a distância N do ponto à origem Como a distância de N até L é 5 e L já está à distância 12 marcamos 17 em N Analogamente como a distância entre N e M é 4 e M já está à distância de 13 marcamos 17 em N A figura 13 passo 11 mostra isso Figura 13 Grafo da malha viária passo 11 Temos assim 2 caminhos com distância de 17 entre A e N A B F J L N A B F J M N origem destino A 0 B 3 C 4 D 5 E 7 F 6 G 9 H 12 I 10 J 9 K 12 L 12 M 13 N 17 5 3 4 4 3 6 5 4 2 5 4 7 7 5 3 4 3 2 3 3 4 3 5 2 4 3 4 6