A empresa de logística Entrega Tudo, localizada na cidade de Patópolis, deve realizar 10 entregas (viagens) de Patópolis à Cidade de Gotham. O mapa rodoviário da região é esquematizado abaixo, apresentando as distâncias de cada trecho.

Essa empresa possui apenas 1 caminhão, não há restrições de motoristas, as estradas estão nas mesmas condições em qualquer trecho, permitindo o tráfego a 50 km/h. Os custos variáveis (combustível) são de R$ 1,00 por quilômetro. No trecho entre Kriptom e Gotham, há uma série de pedágios totalizando R$ 200,00 por viagem.

Com o intuito de reduzir os custos, quando possível, a empresa de logística