Problema de roteirização de veículos com janelas de atendimento, frotas heterogeneas e entregas fracionadas
Resumo
Este artigo apresenta uma solução para o problema de roteirização veículos utilizando a técnica de construção de rotas por inserção sequencial. A construção de rotas baseia-se na heurística de economia inspirada em algoritmos clássicos, como o desenvolvido por Clarke e Wright em 1964. A heurística de economia empregada faz uso de quatro algoritmos, Economia Combinada (EC), Oportunidade Otimista de Economia (OOE), Oportunidade Real de Economia (ORE) e Oportunidade Real de Economia com parâmetro modelador de rota (OREλ). Os algoritmos são testados por um conjunto de benchmarks e apresentam soluções gráficas e numéricas.
Palavras-chave:
Roteirização de Veículos, Frotas Heterogêneas, Entregas Fracionadas
Referências
Belfiore, P. and Yoshida Yoshizaki, H. T. (2009). Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil. European Journal Of Operational Research, 199(3):750–758.
Brandao, J. (1997). A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal Of Operational Research, 100(1):180–191.
Clarke, G. and Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4):568–581.
Dror, M. and Trudeau, P. (1989). Savings by Split Delivery Routing. Transportation Science, 23(2):141–145.
Dullaert, W., Janssens, G. K., Sorensen, K., and Vernimmen, B. (2002). New heuristics for the Fleet Size and Mix Vehicle Routing Problem with Time Windows. Journal of the Operational Research Society, 53(11):1232–1238.
Golden, B., Assad, A., Levy, L., and Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1):49–66.
Ho, S. C. and Haugland, D. (2004). A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers & Operations Research, 31(12):1947–1964.
Liu, F.-h. and Shen, S.-y. (1999). A method for vehicle routing problems with multiple vehicle types and time windows. In Proceedings of Natural Science Council.
Rochat, Y. and Semet, F. (1994). A Tabu Search Approach for Delivering Pet Food and Flour in Switzerland. The Journal of the Operational Research Society, 45(11):1233.
Semet, F. and Taillard, E. (1993). Solving real-life vehicle routing problems efficiently using tabu search. Annals of Operations Research, 41(4):469–488.
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2):254–265.
Brandao, J. (1997). A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal Of Operational Research, 100(1):180–191.
Clarke, G. and Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4):568–581.
Dror, M. and Trudeau, P. (1989). Savings by Split Delivery Routing. Transportation Science, 23(2):141–145.
Dullaert, W., Janssens, G. K., Sorensen, K., and Vernimmen, B. (2002). New heuristics for the Fleet Size and Mix Vehicle Routing Problem with Time Windows. Journal of the Operational Research Society, 53(11):1232–1238.
Golden, B., Assad, A., Levy, L., and Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1):49–66.
Ho, S. C. and Haugland, D. (2004). A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers & Operations Research, 31(12):1947–1964.
Liu, F.-h. and Shen, S.-y. (1999). A method for vehicle routing problems with multiple vehicle types and time windows. In Proceedings of Natural Science Council.
Rochat, Y. and Semet, F. (1994). A Tabu Search Approach for Delivering Pet Food and Flour in Switzerland. The Journal of the Operational Research Society, 45(11):1233.
Semet, F. and Taillard, E. (1993). Solving real-life vehicle routing problems efficiently using tabu search. Annals of Operations Research, 41(4):469–488.
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2):254–265.
Publicado
16/05/2012
Como Citar
DE QUEIROZ, Marc A. Vieira; CAMPOS, Pedro Casagrande; DE BARROS, Rodolfo Miranda; BRANCHER, Jacques Duílio.
Problema de roteirização de veículos com janelas de atendimento, frotas heterogeneas e entregas fracionadas. In: SIMPÓSIO BRASILEIRO DE SISTEMAS DE INFORMAÇÃO (SBSI), 8. , 2012, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 411-422.
DOI: https://doi.org/10.5753/sbsi.2012.14424.
