Problema de Roteamento de Entregas Speedy Delivery - Otimização com PLI

Questão 3 30 pontos A Speedy Delivery oferece serviços de entrega em dois dias de grandes encomendas ao longo dos Estados Unidos De manhã em cada um dos centros de coleta as encomendas que chegaram durante a noite são carregadas em vários caminhões para entrega em determinada aérea Já que o diferencial competitivo nesse segmento é a velocidade na entrega as encomendas são divididas entre os caminhões de acordo com seus destinos geográficos para minimizar o tempo médio necessário para fazer as entregas Nessa manhã em particular a despachante para o centro de coleta Blue River Valley Sharon Lofton está sobrecarregada de trabalho Seus três motoristas chegarão em menos de uma hora para fazer as entregas do dia Há nove encomendas a ser entregues todas em locais distantes muitos quilômetros um dos outros Como de praxe Sharon carregou esses locais em seu computador Ela está usando o pacote de software especial da empresa um sistema de apoio à decisão chamado Dispatcher A primeira coisa que o Dispatcher faz é usar esses locais para gerar um considerável número de possíveis rotas vantajosas para cada um dos caminhões de entrega Essas rotas são mostradas na tabela a seguir na qual os números em cada coluna indicam a ordem das entregas junto com o tempo estimado para percorrer a rota Dispatcher é um sistema interativo que mostra essas rotas para que Sharon possa aproválas ou modificálas Por exemplo o computador pode não saber que uma enchente tornou inviável determinada rota Após Sharon aprovar essas rotas como possibilidades vantajosas com estimativas de tempo razoáveis o Dispatcher formula e soluciona um modelo de PIB para selecionar três rotas que minimizam seu tempo total enquanto inclui cada local de entrega exatamente em uma rota Essa manhã Sharon aprova todas as rotas Local de entrega Possível rota vantajosa 1 2 3 4 5 6 7 8 9 10 A 1 1 1 B 2 1 2 2 C 3 3 3 D 2 1 1 E 2 2 3 F 1 2 G 3 1 2 3 H 1 3 I 3 4 2 Tempo em horas 6 4 7 5 4 6 5 3 7 6