Roteirização

EXERCÍCIO 1: Uma transportadora precisa definir a melhor rota de entrega entre as cidades A e J, tendo como base os tempos de deslocamento entre ambas, bem como os cruzamentos existentes entre as diferentes estradas possíveis de serem escolhidas para a composição do percurso, conforme mostrado na figura abaixo. Com base no método da rota mais curta, defina o melhor caminho.

Admita que os tempos de deslocamento entre os pontos são os seguintes:

A e B = 80 minutos
A e C = 100 minutos
A e G = 310 minutos
B e E = 90 minutos
B e C = 60 minutos
C e F = 90 minutos
E e I = 44 minutos
E e F = 50 minutos
F e H = 24 minutos
G e H = 40 minutos
I e H = 50 minutos
I E J = 100 minutos
H e J = 100 minutos
G e J = 120 minutos

Etapa
Nós Resolvidos
Nó sem solução mais próximo
Tempo
Nó mais próximo
Tempo Mínimo do caminho
Última Conexão

1
A
B
80
B
80
AB

2
A
B
A
C
C
G
100
140
310
C

100
AC

3
B
C
A
E
F
G
80+90=170
100+90=190
310
E
170
BE

4
A
C
E
G
F
I
310
190
170+44=214

F

190

CF

5
A
E
F
G
I
H
310
214
190+24=214

I
H

214
214

EI
FH
6
A
H
I
G
G
J
310
214+40=254
214+100=314

G

254

HG
7
I
H
G
J
J
J
214+100=314
214+100=314
254+120=374
J
J
314
314
IJ
HJ

Definição do percurso ideal. Faz-se de trás para frente:
Percurso 1: J, I, E, B, A ou Percurso 2: J, H, F, C, A

EXERCÍCIO 2
Uma transportadora precisa definir a melhor rota de entrega entre as cidades A e J, tendo como base os tempos de deslocamento entre ambas, bem como os cruzamentos existentes entre as diferentes estradas possíveis de serem escolhidas para a composição do percurso, conforme mostrado na figura abaixo. Com base no método da rota mais curta, defina o melhor percurso.

Admita que os tempos de deslocamento entre os pontos são os seguintes:
A e B = 90 minutos
A e C = 138 minutos
A e D = 348 minutos
B e E = 84 minutos
B e C = 66 minutos
C e F = 90