4 - Distribuição B - Roteirização

Prévia do material em texto

Odacir Graciolli
1/15
DISTRIBUIÇÃO
Roteirização
 2
Roteirização
 Atender ao cliente com o nível de serviço 
desejado
 Reduzir os custos de transporte tanto quanto 
possível, escolhendo os trajetos mais adequados 
de forma a aproveitar eficientemente a frota e 
a mão de obra operacional
Objetivos
 3
Roteirização
 Atender ao cliente com o nível de serviço 
desejado
 Reduzir os custos de transporte tanto quanto 
possível, escolhendo os trajetos mais adequados 
de forma a aproveitar eficientemente a frota e 
a mão de obra operacional
Objetivos
Odacir Graciolli
4/15
Abrangência dos problemas de roteirização segundo o 
tipo de rede de transporte 
● Rodovias
● Redes viárias urbanas
● Ferrovias
● Linhas ou rotas de navegação aquaviária ou aérea
● Rotas em fábricas e armazéns
● Outras (Placas CI, química, etc)
 
Odacir Graciolli
5/15
Configuração de um problema de roteirização em nós → 
pontos de origem e destino únicos e separados 
Odacir Graciolli
6/15
Problema do Caixeiro Viajante
Para achar a solução ótima podemos gerar 
(n - 1)! rotas (rota assimétrica), calcular o 
comprimento total das viagens de cada rota 
e ver qual delas tem o menor comprimento 
total
Odacir Graciolli
7/15
Problema do Caixeiro Viajante
Suponhamos ter um computador muito veloz , capaz de fazer 1 
bilhão (109) de adições por segundo. Isso parece uma velocidade 
imensa, capaz de tudo.
Para o caso de 20 cidades, o computador precisa apenas de 19 
adições para dizer qual o comprimento de uma rota e então será 
capaz de calcular 109 / 19 = 53 milhões de rotas por segundo.
 8
Métodos de solução
Programação matemática
Vantagens:
– Garantem a solução ótima (menos custo)
Desvantagens:
– Difícil modelagem
– Nem sempre conseguem produzir uma solução
Heurísticas
Vantagens: 
– De fácil implementação
– Produzem boas soluções rapidamente
Desvantagem:
– Não garantem a otimalidade da solução obtida
Odacir Graciolli
9/15
Características dos problemas de roteirização em nósnós 
Características Opções possíveis 
1. Tamanho disponível de frota único veículo/equipamento 
múltiplos veículos/equipamentos 
2. Tipo da frota/equipamentos homogênea 
heterogênea
tipos especiais 
3. Ponto de origem/destino única origem e único destino (coincidentes ou não) 
única origem e vários destinos 
várias origens e único destino 
várias origens e vários destinos 
4. Natureza das demandas determinísticas 
estocásticas 
5. Localização das demandas nos vértices (nós) 
6. Ocorrência das demandas em todos vértices do grafo 
em alguns vértices do grafo 
7. Rede associada não orientada 
orientada 
mista 
Odacir Graciolli
10/15
Características dos problemas de roteirização em nósnós 
Características Opções possíveis 
8. Restrições de capacidade estipulada (iguais para todas unidades de trabalho) 
estipulada (diferentes para as unidades de trabalho) 
não estipulada (capacidade ilimitada) 
9. Tempo máximo associados as rotas estipulada (igual para todas as rotas) 
estipulada (diferente para diferentes rotas) 
Não estipulada 
10. Operações coletas 
entregas 
mistas (coletas e entregas) 
outros tipos de operações 
11. Coeficiente de custo associado tempo 
distância 
custo de operação 
12. Função objetivo minimizar o custo, a distância ou o tempo 
minimizar o número de veículos ou a força de trabalho 
Odacir Graciolli
11/15
Características dos problemas de roteirização em arcosarcos 
Características Opções possíveis 
1. Tamanho disponível de frota único veículo/equipamento 
ou da força de trabalho única pessoa 
múltiplos veículos/equipamentos 
várias pessoas 
2. Tipo da frota/equipamentos homogênea 
ou da força de trabalho heterogênea 
tipos especiais 
3. Ponto de origem/destino única origem e único destino (coincidentes ou não) 
única origem e vários destinos 
várias origens e único destino 
várias origens e vários destinos 
4. Natureza das demandas determinísticas 
estocásticas 
5. Localização das demandas nos arcos e/ou arestas 
6. Ocorrência das demandas em todos arcos e/ou arestas do grafo 
em alguns arcos e/ou arestas do grafo 
7. Rede associada não orientada 
orientada 
mista 
Odacir Graciolli
12/15
Características dos problemas de roteirização em arcosarcos 
Características Opções possíveis 
8. Restrições de capacidade estipulada (iguais para todas unidades de trabalho) 
estipulada (diferentes para as unidades de trabalho) 
não estipulada (capacidade ilimitada) 
9. Tempo máximo associados as rotas estipulada (igual para todas as rotas) 
estipulada (diferente para diferentes rotas) 
não estipulada 
10. Operações coletas 
entregas 
mistas (coletas e entregas) outros tipos de 
operações 
11. Coeficiente de custo associado tempo 
distância 
custo de operação 
12. Função objetivo minimizar o custo, a distância ou o tempo 
minimizar o número de veículos ou a força de trabalho 
 13
 Fluxo
 Euler Path - PCC
A
restas
 
 Zoneamento
 Caminhos 
 Sequênciamento
Atribuição
Localização
 O-D
 Hamilton Path - PCV
 Simétricas
 Assimétricas
 Mistas
 Euclidianas
 Deterministicas
 Probabilisticas
V
értices
R
e
d
es
 P-Centros
 P-Madianas
 Cobertura
• demanda
• tempo atendimento
• nº pontos
• tempo de viagem
• sem restrição
• rest. capacidade
• rest. tempo/jornada
• janela tempo/scheduling
• frota 
homogênia/heterogênia
• nº depósitos/garagens
Odacir Graciolli
14/15
Aplicativos comerciais
TMS (Transportation Management System) 
ArcLogistics Route 3 RoutePro 
Compass RouteSmart 
Direct Route Routronic 2000 
Edgar Transp. Mang. System ShorTrec product suite 
Fleetwise Enterprise Rout. and 
STARS 
Sched. System 
ILOG Dispatcher Territory Planner 
Intertour/Interload tmsRouter 
Manugistics Fleet Management tmsZoneDesigner 
Optrak4 TransCad 
Prophesy Mileage & Routing Trapeze 
TruckSTOPS Routing & Scheduling for 
Protour 
Windows 
VersaTrans Routing & Planning 
RoadNet 5000 Software 
RoadShow System 
 15
TMS (Transportation Management System) 
 Claudio F. Caetano Fonseca Costa
 https://www.linkedin.com/pulse/softwares-de-roteiriza%C3%A7%C3%A3o-claudio-f-caetano-fonse
ca-costa/?originalSubdomain=pt

https://www.linkedin.com/pulse/softwares-de-roteiriza%C3%A7%C3%A3o-claudio-f-caetano-fonseca-costa/?originalSubdomain=pt
https://www.linkedin.com/pulse/softwares-de-roteiriza%C3%A7%C3%A3o-claudio-f-caetano-fonseca-costa/?originalSubdomain=pt
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15