ExemploDeCaixeiroViajante

Prévia do material em texto

Roteirização 
 
A figura abaixo apresenta a localização de um escritório, que se encontra no ponto A, e de três clientes 
desse escritório que estão localizados nos pontos B, C e D, de acordo com a figura a seguir. 
 
 
 
Um funcionário desse escritório precisa entregar alguns documentos a cada um desses clientes e, em 
seguida, retornar ao escritório. É fácil perceber que há alternativas diferentes em relação à ordem de 
entrega desses documentos. Por exemplo, o funcionário, partindo do ponto A, pode ir para B e depois 
para C e D, retornando logo após ao ponto A. Ele pode também partir de A, passar por C, D e B e retornar 
ao ponto A e assim por diante. A escolha da ordem das entregas pode interferir na distância total 
percorrida pelo funcionário. Para isso, é importante conhecer as distâncias entre todas as localidades 
envolvidas. A tabela a seguir apresenta as distâncias, em quilômetros, entre os pontos A, B, C e D. 
 
 A B C D 
A 0 3 2 5 
B 3 0 1 3 
C 2 1 0 2 
D 5 3 2 0 
 
Com base nessas informações, escreva todas as possibilidades de rotas existentes para que o funcionário, 
partindo de A, passe uma única vez pelas demais localidades apresentadas e, em seguida, retorne ao 
ponto A. Determine também a distância total percorrida em cada uma dessas rotas e indique, dentre as 
rotas apresentadas, qual é a rota cuja distância total percorrida é a menor possível. 
 
Resposta: 
A-B-C-D-A; Total: 3+1+2+5=11 
A-B-D-C-A; Total: 3+3+2+2=10 
A-C-B-D-A; Total: 2+1+3+5=11 
A-C-D-B-A; Total: 2+2+3+3=10 
A-D-B-C-A; Total: 5+3+1+2=11 
A-D-C-B-A; Total: 5+2+1+3=11 
 
Menor rota: 
A-B-D-C-A; Total: 10 
ou 
A-C-D-B-A; Total: 10