Roteirização de Veículos

Prévia do material em texto

<p>Roteirização de veículos</p><p>Prof. Kalil Figueiredo Almeida</p><p>1</p><p>O que é roteirizar?</p><p>Um conjunto de pontos a serem atendidos, para os quais são conhecidos sua localização, quantidade demandada, horários de atendimento, etc.</p><p>Uma frota de veículos disponíveis para realizar os atendimentos e sua localização</p><p>As distâncias e os tempos de viagem entre todos os pares de pontos</p><p>Roteirizar é ....</p><p>© CLAUDIO BARBIERI DA CUNHA, 2012</p><p>DIREITOS RESERVADOS - REPRODUÇÃO PROIBIDA</p><p>Definir e determinar:</p><p>quantos e quais veículos utilizar?</p><p>que atendimentos alocar/atribuir a cada veículo?</p><p>para cada veículo, em que ordem/sequência atender? (roteiros)</p><p>Contexto da Roteirização</p><p>Uma das estratégias para distribuição física urbana</p><p>Envolve somente entregas?</p><p>O que mais pode incluir? Coletas, atendimentos, ...</p><p>Por quê roteirizar?</p><p>Quantidade de carga para cada cliente, frequência de entrega não permitem entrega direta com carga completa</p><p>Portanto, necessidade de compartilhamento de veículos para atendimento de vários clientes</p><p>Necessário definir que veículos servem que clientes e em que ordem/sequência, de maneira ótima</p><p>Roteirização: aplicações</p><p>Roteirização diária</p><p>Clientes e quantidades mudam diariamente</p><p>Muita flutuação para permitir rotas estáticas</p><p>Planejamento estratégico e tático</p><p>Análise de cenários</p><p>Impacto de criação de novos CDs</p><p>Impacto de políticas operacionais (hora extra, número máximo de entregas por rota, etc.)</p><p>Estimar custo de entrega/atendimento de cliente</p><p>Roteiros de entregas</p><p>500 entregas</p><p>25 veículos</p><p>2h para concluir programação!!!</p><p>1,0439 x 1042 combinações (formas de agrupamento)</p><p>–	1.043.900.000.000.000.000.000.000.000.000.000.000.000.000</p><p>Sem considerar roteiros/sequências de entrega</p><p>D</p><p>TIPOS DE PROBLEMA DE ROTEIRIZAÇÃO</p><p>O REAL problema de roteirização</p><p>Origem e destino coincidentes, passando por todos os pontos</p><p>Principais desafios da roteirização</p><p>Congestionamentos nos centros urbanos</p><p>Restrições à circulação de veículos de carga</p><p>Horários, tamanhos de veículos</p><p>Rever estratégia de distribuição</p><p>Roteirização</p><p>Objetivos:</p><p>Descobrir os melhores roteiros para os veículos a fim de minimizar tempos e distâncias</p><p>Aumentar a eficiência por meio da máxima utilização dos equipamentos e pessoal de transporte</p><p>Roteirização</p><p>Variações:</p><p>Um ponto de origem e um ponto de destino: PROBLEMA DO CAMINHO MÍNIMO</p><p>Ponto de origem e destino coincidente: PROBLEMA DO CAIXEIRO VIAJANTE</p><p>Problema do caminho mínimo</p><p>Consiste em encontrar a rota de custo mínimo entre uma origem e um destino, dada uma rede de fluxos possíveis</p><p>Problema do caminho mínimo</p><p>Exemplo:</p><p>Buscar a rota mais rápida na rede abaixo</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>F</p><p>G</p><p>H</p><p>I</p><p>J</p><p>90</p><p>84</p><p>84</p><p>126</p><p>138</p><p>348</p><p>156</p><p>90</p><p>66</p><p>48</p><p>120</p><p>132</p><p>126</p><p>48</p><p>132</p><p>150</p><p>60</p><p>Problema do caminho mínimo</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>F</p><p>G</p><p>H</p><p>I</p><p>J</p><p>90</p><p>84</p><p>84</p><p>126</p><p>138</p><p>348</p><p>156</p><p>90</p><p>66</p><p>48</p><p>120</p><p>132</p><p>126</p><p>48</p><p>132</p><p>150</p><p>60</p><p>0	0</p><p>A	90</p><p>A	138</p><p>C	294</p><p>B	174</p><p>C	228</p><p>*</p><p>*</p><p>E	258</p><p>F	278</p><p>F	360</p><p>*</p><p>I</p><p>384</p><p>*</p><p>Problema do caixeiro viajante</p><p>Consiste em encontrar uma rota que:</p><p>Parta de um ponto de origem</p><p>Passe por todos os demais pontos uma única vez</p><p>Retorne à origem ao final do percurso</p><p>Percorra a menor distância possível</p><p>Problema do caixeiro viajante</p><p>Em geral, boas soluções podem ser obtidas através de heurísticas:</p><p>Procedimentos que seguem uma intuição para resolver o problema, sem confirmação matemática (forma humana de resolver o problema, fenômenos naturais, processos biológicos etc)</p><p>Não garantem que a solução final seja ótima</p><p>Em geral, produzem soluções finais de boa qualidade rapidamente</p><p>Heurísticas de construção</p><p>Vizinho mais próximo:</p><p>Construir uma rota passo a passo, adicionando à solução corrente o ponto mais próximo (ainda não visitado) do último ponto inserido</p><p>Vizinho mais próximo</p><p>1</p><p>4</p><p>i	j	dij</p><p>6	1	1</p><p>6	2	2</p><p>6	3	6</p><p>6	4	6</p><p>6	5	2</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 1</p><p>1</p><p>Vizinho mais próximo</p><p>1</p><p>4</p><p>i	j	dij</p><p>1	2	2</p><p>1	3	1</p><p>1	4	4</p><p>1	5	9</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 2</p><p>1</p><p>1</p><p>Vizinho mais próximo</p><p>1</p><p>4</p><p>i	j	dij</p><p>3	2	5</p><p>3	4	3</p><p>3	5	8</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 5</p><p>1</p><p>1</p><p>3</p><p>Vizinho mais próximo</p><p>1</p><p>4</p><p>i	j	dij</p><p>4	2	9</p><p>4	5	2</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 7</p><p>1</p><p>1</p><p>3</p><p>2</p><p>Vizinho mais próximo</p><p>1</p><p>4</p><p>i	j	dij</p><p>5	2	7</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 14</p><p>1</p><p>1</p><p>3</p><p>2</p><p>7</p><p>Vizinho mais próximo</p><p>1</p><p>4</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 16</p><p>1</p><p>3</p><p>2</p><p>7</p><p>1</p><p>2</p><p>Heurísticas de construção</p><p>Inserção mais barata:</p><p>Construir uma rota passo a passo, partindo de uma rota inicial envolvendo 3 pontos, e adicionar, a cada passo, o ponto cujo custo de inserção entre a ligação de pontos já visitados seja o mais barato</p><p>Inserção mais barata</p><p>1</p><p>4</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 11</p><p>2</p><p>7</p><p>2</p><p>Inserção mais barata</p><p>1</p><p>4</p><p>i	k	j	dik + dkj – dij</p><p>6	1	2	1 + 2 – 2 = 1</p><p>6	3	2	6 + 5 – 2 = 9</p><p>6	4	2	6 + 9 – 2 = 3</p><p>2	1	5	2 + 9 – 7 = 4</p><p>2	3	5	5 + 8 – 7 = 6</p><p>2	4	5	9 + 2 – 7 = 4</p><p>5	1	6	9 + 1 – 2 = 8</p><p>5	3	6	8 + 6 – 2 = 12</p><p>5	4	6	2 + 6 – 2 = 6</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 11 + 1 = 12</p><p>7</p><p>2</p><p>1</p><p>2</p><p>2</p><p>Inserção mais barata</p><p>1</p><p>4</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 12 + 4 = 16</p><p>7</p><p>2</p><p>1</p><p>2</p><p>Inserção mais barata</p><p>1</p><p>4</p><p>i	k	j	dik + dkj – dij</p><p>6	3	1	6 + 1 – 1 = 6</p><p>6	4	1	6 + 4 – 1 = 9</p><p>1	3	2	1 + 5 – 2 = 4</p><p>1	4	2	4 + 9 – 2 = 11</p><p>2	3	5	5 + 8 – 7 = 6</p><p>2	4	5	9 + 2 – 7 = 4</p><p>5	3	6	8 + 6 – 2 = 12</p><p>5	4	6	2 + 6 – 2 = 6</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 12 + 4 = 16</p><p>7</p><p>2</p><p>1</p><p>2</p><p>5</p><p>1</p><p>Inserção mais barata</p><p>1</p><p>4</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 16 + 4 = 20</p><p>7</p><p>2</p><p>1</p><p>5</p><p>1</p><p>Inserção mais barata</p><p>1</p><p>4</p><p>i	k	j	dik + dkj – dij</p><p>6	4	1	6 + 4 – 1 = 9</p><p>1	4	3	4 + 3 – 1 = 6</p><p>3	4	2	3 + 9 – 5 = 7</p><p>2	4	5	9 + 2 – 7 = 4</p><p>5	4	6	2 + 6 – 2 = 6</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 16 + 4 = 20</p><p>7</p><p>2</p><p>1</p><p>5</p><p>1</p><p>9</p><p>2</p><p>Inserção mais barata</p><p>1</p><p>4</p><p>i	k	j	dik + dkj – dij</p><p>6	4	1	6 + 4 – 1 = 9</p><p>1	4	3	4 + 3 – 1 = 6</p><p>3	4	2	3 + 9 – 5 = 7</p><p>2	4	5	9 + 2 – 7 = 4</p><p>5	4	6	2 + 6 – 2 = 6</p><p>3</p><p>2</p><p>5</p><p>6</p><p>Cid.	1	2	3	4	5	6</p><p>1	0	2	1	4	9	1</p><p>2	2	0	5	9	7	2</p><p>3	1	5	0	3	8	6</p><p>4	4	9	3	0	2	6</p><p>5	9	7	8	2	0	2</p><p>6	1	2	6	6	2	0</p><p>Distância Total = 16 + 4 = 20</p><p>2</p><p>1</p><p>5</p><p>1</p><p>9</p><p>2</p><p>Roteirização e Programação de Veículos (RPV)</p><p>Extensão do problema básico de roteirização</p><p>Inclusão de restrições realistas:</p><p>Escalas com entregas e coletas simultaneamente</p><p>Janelas de tempo</p><p>Caminhões múltiplos com diferentes capacidades de peso e volume</p><p>Tempo máximo de permanência ao volante em cada roteiro</p><p>Velocidades máximas diferentes em diferentes zonas</p><p>Barreiras ao tráfego (lagos, desvios, montanhas)</p><p>Intervalos para os motoristas (descanso e refeição)</p><p>Roteirização e Programação de Veículos (RPV)</p><p>Características do problema</p><p>Tipo de operação</p><p>Coleta</p><p>Entrega</p><p>Coleta e entrega simultâneas</p><p>Tipo de carga</p><p>Única</p><p>Fracionada</p><p>Tamanho da frota</p><p>Limitada</p><p>Ilimitada</p><p>Tipo de frota</p><p>Homogênea</p><p>Heterogênea</p><p>Depósito e localização de veículos</p><p>Depósito único</p><p>Vários depósitos</p><p>Produtos disponíveis no</p><p>Depósito central</p><p>Número de bases de origem e destino dos veículos</p><p>Jornada de trabalho</p><p>Duração</p><p>Horário de almoço e outras interrupções</p><p>Permissão para viagem com mais de um dia de duração</p><p>Roteirização e Programação de Veículos (RPV)</p><p>Função objetivo:</p><p>Minimizar os custos totais de distribuição</p><p>Minimizar a distância total percorrida</p><p>Minimizar o número de veículos utilizados</p><p>Roteirização e Programação de Veículos (RPV)</p><p>Restrições:</p><p>Veículos:</p><p>Limite de capacidade (peso ou volume)</p><p>Tipo de carga que pode ser transportada</p><p>Operação de carga e descarga</p><p>Número e tipo de veículos disponíveis</p><p>Roteirização e Programação de Veículos (RPV)</p><p>Restrições:</p><p>Clientes:</p><p>Horário para recebimento/coleta</p><p>Atendimento total ou parcial das demandas</p><p>Tempo máximo permitido para carga e descarga</p><p>Necessidade ou restrição de serviço em algum dia específico da semana</p><p>Disponibilidade de área para estacionamento do veículo</p><p>Roteirização e Programação de Veículos (RPV)</p><p>Restrições:</p><p>Rotas:</p><p>Horário de início e término das viagens</p><p>Tempo máximo de viagem de um veículo</p><p>Distância máxima percorrida</p><p>Locais de paradas fixas</p><p>Roteirização e Programação de Veículos (RPV)</p><p>Variáveis de decisão:</p><p>Quantos veículos serão utilizados</p><p>Roteiro a ser percorrido por cada veículo</p><p>Qual veículo será designado para cada cliente</p><p>Qual a quantidade de carga transportada para cada cliente da rota</p><p>Roteirização e Programação de Veículos (RPV)</p><p>Em geral, os problemas de RPV são tratados por:</p><p>Princípios</p><p>Heurísticas</p><p>Princípios para uma boa RPV</p><p>Problema em que caminhões devem partir de um depósito central, visitar múltiplas escalas para efetuar entregas e retornar ao depósito no mesmo dia</p><p>Princípios para uma boa RPV</p><p>Carregar caminhões com volumes destinados a paradas que estejam mais próximas entre si</p><p>A coleta deve ser combinada nas rotas de entrega em vez de reservada para o final dos roteiros</p><p>As pequenas janelas de tempo devem ser evitadas</p><p>Evitar o cruzamento de rotas...</p><p>Princípios para uma boa RPV</p><p>D</p><p>(a) Conjunto ruim</p><p>(b) Conjunto melhor</p><p>D</p><p>Heurísticas de construção para RPV</p><p>Método da Varredura</p><p>Simples, não exige solução computacional</p><p>Índice médio de erro é de cerca de 10%</p><p>Método de 2 estágios:</p><p>Atribuição de paradas a cada veículo</p><p>Estabelecimento da sequência de parada</p><p>Questões de tempo não são adequadamente tratadas</p><p>Método da Varredura</p><p>Localizar todas as paradas, inclusive o depósito, em um mapa</p><p>Método da Varredura</p><p>Estender uma linha reta do depósito em qualquer direção</p><p>Método da Varredura</p><p>Girar a linha no sentido horário (ou anti-horário) até cruzar uma parada</p><p>Verificar se a introdução da parada na rota excede a capacidade do caminhão</p><p>SIM – Excluir a parada e definir a rota NÃO – Voltar ao passo 3</p><p>Método da Varredura</p><p>Método da Varredura</p><p>Definir a rota</p><p>Método da Varredura</p><p>Dentro de cada rota, sequenciar as paradas de forma a minimizar a distância</p><p>Método da Varredura</p><p>Heurísticas de construção para RPV</p><p>Método das Economias (Método Clarke-Wright)</p><p>Solução computacional rápida</p><p>Soluções, em média, são 2% mais caras que o nível ótimo</p><p>Elabora roteiros e sequencia paradas simultaneamente</p><p>Consegue lidar com restrições práticas</p><p>Objetivo: minimizar a distância total percorrida por todos os veículos, minimizando o número de veículos necessários</p><p>Método das Economias (Método Clarke-Wright)</p><p>Heurísticas de construção para RPV</p><p>dO,A</p><p>dA,O</p><p>dO,B</p><p>dB,O</p><p>A</p><p>B</p><p>O</p><p>dO,A</p><p>dA,B</p><p>dB,O</p><p>A</p><p>B</p><p>O</p><p>Distância máxima da rota = dO,A + dA,O + dO,B + dB,O</p><p>Distância da rota (c/ combinação) =</p><p>dO,A + dA,B + dB,O</p><p>Economia = dA,O + dO,B - dA,B</p><p>Método das Economias – Passo 1</p><p>Cid.	0	1	2	3	4	5</p><p>0	0	6	7	8	9	10</p><p>1	6	0	3	2	1	4</p><p>2	7	3	0	5	3	4</p><p>3	8	2	5	0	8	1</p><p>4	9	1	3	8	0	5</p><p>5	10	4	4	1	5	0</p><p>Capacidade do Veículo: 20</p><p>Distância Total = (5+5)+(6+6)+(7+7)+(8+8)+(9+9) = 70</p><p>Número de veículos = 5</p><p>1</p><p>4</p><p>3</p><p>2</p><p>5</p><p>0</p><p>6</p><p>6</p><p>5</p><p>5</p><p>9</p><p>9</p><p>8</p><p>8</p><p>7</p><p>7</p><p>Distância Total = 80 – S35 = 63</p><p>Número de veículos = 4</p><p>Método das Economias – Passo 2</p><p>Cid.	0	1	2	3	4	5</p><p>0	0	6	7	8	9	10</p><p>1	6	0	3	2	1	4</p><p>2	7	3	0	5	3	4</p><p>3	8	2	5	0	8	1</p><p>4	9	1	3	8	0	5</p><p>5	10	4	4	1	5	0</p><p>1</p><p>4</p><p>i	j	d0i	dj0	dij	Sij = d0i + dj0 – dij</p><p>1	2	6	7	3	10</p><p>1	3	6	8	2	12</p><p>1	4	6	9	1	14</p><p>1	5	6	10	4	12</p><p>2	3	7	8	5	10</p><p>2	4	7	9	3	13</p><p>2	5	7	10	4	13</p><p>3	4	8	9	8	9</p><p>3	5	8	10	1	17</p><p>4	5	9	10	5	14</p><p>3</p><p>2</p><p>5</p><p>0</p><p>7</p><p>7</p><p>6</p><p>6</p><p>10</p><p>9</p><p>9</p><p>8</p><p>1</p><p>10</p><p>8</p><p>Capacidade do Veículo: 20</p><p>Método das Economias – Passo 3</p><p>Cid.	0	1	2	3	4	5</p><p>0	0	6	7	8	9	10</p><p>1	6	0	3	2	1	4</p><p>2	7	3	0	5	3	4</p><p>3	8	2	5	0	8	1</p><p>4	9	1	3	8	0	5</p><p>5	10	4	4	1	5	0</p><p>i	j	d0i	dj0	dij	Sij = d0i + dj0 – dij</p><p>1	2	6	7	3	10</p><p>1	3	6	8	2	12</p><p>1	4	6	9	1	14</p><p>1	5	6	10	4	12</p><p>2	3	7	8	5	10</p><p>2	4	7	9	3	13</p><p>2	5	7	10	4	13</p><p>3	4	8	9	8	9</p><p>4	5	9	10	5	14</p><p>Capacidade do Veículo: 20</p><p>1</p><p>4</p><p>3</p><p>2</p><p>5</p><p>0</p><p>7</p><p>7</p><p>6</p><p>6</p><p>10</p><p>9</p><p>9</p><p>8</p><p>1</p><p>1</p><p>Distância Total = 63 – S14 = 49</p><p>Número de veículos = 3</p><p>Método das Economias – Passo 4</p><p>Cid.	0	1	2	3	4	5</p><p>0	0	6	7	8	9	10</p><p>1	6	0	3	2	1	4</p><p>2	7	3	0	5	3	4</p><p>3	8	2	5	0	8	1</p><p>4	9	1	3	8	0	5</p><p>5	10	4	4	1	5	0</p><p>1</p><p>4</p><p>i	j	d0i	dj0	dij	Sij = d0i + dj0 – dij</p><p>1	2	6	7	3	10</p><p>1	3	6	8	2	12</p><p>1	5	6	10	4	12</p><p>2	3	7	8	5	10</p><p>2	4	7	9	3	13</p><p>2	5	7	10	4	13</p><p>3	4	8	9	8	9</p><p>4	5	9	10	5	14</p><p>3</p><p>2</p><p>5</p><p>0</p><p>7</p><p>7</p><p>6</p><p>10</p><p>9</p><p>8</p><p>1</p><p>1</p><p>3</p><p>Capacidade do Veículo: 20</p><p>Distância Total = 49 – S24 = 36</p><p>Número de veículos = 2</p><p>Método das Economias – Passo Final</p><p>Cid.	0	1	2	3	4	5</p><p>0	0	6	7	8	9	10</p><p>1	6	0	3	2	1	4</p><p>2	7	3	0	5	3	4</p><p>3	8	2	5	0	8	1</p><p>4	9	1	3	8	0	5</p><p>5	10	4	4	1	5	0</p><p>1</p><p>4</p><p>i	j	d0i	dj0	dij	Sij = d0i + dj0 – dij</p><p>1	3	6	8	2	12</p><p>1	5	6	10	4	12</p><p>2	3	7	8	5	10</p><p>2	5	7	10	4	13</p><p>3	4	8	9	8	9</p><p>4	5	9	10	5	14</p><p>3</p><p>2</p><p>5</p><p>0</p><p>7</p><p>6</p><p>10</p><p>8</p><p>1</p><p>1</p><p>3</p><p>Capacidade do Veículo: 20</p><p>Distância Total = 36</p><p>Número de veículos = 2</p><p>image2.jpg</p><p>image3.png</p><p>image4.png</p><p>image5.jpg</p><p>image6.jpg</p><p>image7.png</p><p>image8.png</p><p>image9.png</p><p>image10.png</p><p>image11.png</p><p>image12.png</p><p>image13.png</p><p>image14.png</p><p>image15.png</p><p>image16.png</p><p>image17.png</p><p>image18.png</p><p>image19.png</p><p>image20.png</p><p>image21.png</p><p>image22.png</p>