PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS COM MULTICOMPARTIMENTOS COM COLETA E ENTREGA MISTA RESTRITA

PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS COM MULTICOMPARTIMENTOS COM COLETA E ENTREGA MISTA RESTRITA

Póvoa, Carlos Leonardo Ramos; Paula Jr., Geraldo Galdino de; Silva, Laura Moreira Vasconcelos Lima da; Moreira, Júlia Landeira

Artigo Completo:

Este artigo apresenta o problema de roteirização de veículos com multi-compartimentos com coleta e entrega mista restrita (MC-PRVCEMR). O mesmo é uma generalização do problema de roteirização de veículos com entregas e coletas, possibilitando o decisor a escolher o quanto de capacidade livre do veículo será aceito antes de começar a fazer as coletas. Uma heurística GRASP foi desenvolvida para solução do problema, bem como um procedimento de verificação de inserção do cliente na rota. O algoritmo foi testado com 46 instâncias, e apesar da utilização de um procedimento simples de busca local, o mesmo apresentou resultados compatíveis com a literatura.

Este artigo apresenta o problema de roteirização de veículos com multi-compartimentos com coleta e entrega mista restrita (MC-PRVCEMR). O mesmo é uma generalização do problema de roteirização de veículos com entregas e coletas, possibilitando o decisor a escolher o quanto de capacidade livre do veículo será aceito antes de começar a fazer as coletas. Uma heurística GRASP foi desenvolvida para solução do problema, bem como um procedimento de verificação de inserção do cliente na rota. O algoritmo foi testado com 46 instâncias, e apesar da utilização de um procedimento simples de busca local, o mesmo apresentou resultados compatíveis com a literatura.

Palavras-chave:

DOI: 10.5151/spolm2019-152

Referências bibliográficas

• [1] 1. BRANDÃO, J. A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research, v. 173, p. 540–555, 2006. 2. CASCO, D. O.; GOLDEN, B. L.; WASIL, E. A. Vehicle routing with backhauls: models, algorithms and case studies. In A. A. Assad (Ed.). Vehicle routing: Methods and studies. Amsterdam: Elsevier, p. 127–147, 1988. 3. CHAOVALITWONGSE, W.; KIM, D.; PARDALOS, P. M. GRASP with a new local search scheme for vehicle routing problems with time windows. Journal of Combinatorial Optimization, v. 7, n. 2, p. 179-207, 2003. 4. CRISPIM J.; BRANDÃO J.. Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls. Journal of the Operational Research Society, v. 56(7), p. 1296–1302, 2005. 5. DEIF, I.; BODIN, L. Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling. In A. E. Kidder (Ed.). Proceedings of the conference on software uses in transportation and logistics management, p. 75–96, 1984. 6. EL FALLAHI, A.; PRINS, C.; CALVO, R. W. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, v. 35, n. 5, p. 1725-1741, 2008. 7. FEO, T. A.; RESENDE, M.G.C. Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, v. 6, p. 109-133, 1995. 8. GAJPAL, Y.; ABAD, P. L. Multi-ant colony system (MACS) for a vehicle routing problem with backhauls. European Journal of Operational Research, v. 196, p.102– 117, 2009. 9. GOETSCHALCKX, M.; JACOBS-BLECHA, C. (1989). The vehicle routing problem with backhauls. European Journal of Operational Research, v. 42, p. 39–51. 10. HALSE, K. Modeling and solving complex vehicle routing problems. Lyngby: Technical University of Denmark, 1992. PhD thesis, Institute of Mathematical Statistics and Operations Research. 11. KONTORAVDIS, G.; BARD, J. F. A GRASP for the vehicle routing problem with time windows. ORSA Journal on Computing, v. 7, n. 1, p. 10-23, 1995. 12. LAPORTE, G.; M. GENDRAU, J.Y; POTVIN, F. S. Classical and modern heuristics for the vehicle routing problem. International Transaction in Operational Research, v. 7 (4/5), p. 285-300, 2000. 13. MARTELLO S., TOTH P. Lower Bounds and Reduction Procedures for the Bin Packing Problem. Discrete Applied Mathematics, v. 28, p. 59-70, 1990. 14. MINGOZZI, A.; GIORGI, S.; BALDACCI, R. An exact method for the vehicle routing problem with backhauls. Transportation Science, v. 33, p. 315–329, 1999. 15. NAGY, G.; SALHI, S. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, v. 162, p. 126–141, 2005. 16. NAGY, G.; WASSAN, N. A.; SALHI, S. The vehicle routing problem with restricted mixing of deliveries and pickups. Journal of Scheduling, v. 16, n. 2, p. 199–213, 2013. 17. PARRAGH, S. N.; DOERNER, K. F.; HARTL, R. F. A survey on pickup and delivery problems. Part I: Transportation between customers and depot. Journal für Betriebswirtschaft, v. 58, p. 21–51, 2008. 18. ROPKE, S.; PISINGER, D. A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, v. 171, p. 750– 775, 2006. 19. SALHI S.; NAGY G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the Operational Research Society, v. 50, p. 1034–1042, 1999. 20. TOTH, P.; VIGO, D. An exact algorithm for the vehicle routing problem with backhauls. Transportation Science, v. 31, p. 372–385, 1997. 21. TURKENSTEEN, M.; HASLE, G.. Combining pickups and deliveries in vehicle routing – An assessment of carbon emission effects. Transportations Research Part C, v. 80, p. 117-132, 2017. 22. TÜTÜNCÜ, G. Y.; CARRETO, C. A. C.; BAKER, B. M. A visual interactive approach to classical and mixed vehicle routing problems with backhauls. Omega, v. 37, p. 138– 154, 2009. 23. WADE, A. C.; SALHI, S. An investigation into a new class of vehicle routing problem with backhauls. Omega, v. 30, p. 479–487, 2002. 24. WADE, A. C.; SALHI, S. An ant system algorithm for the mixed vehicle routing problem with backhauls. In M. G. Resende & J. P. de Sousa (Eds.). Metaheuristics: Computer decision-making New York: Kluwer, 2003, p. 699– 719. 25. WASSAN, N. A. Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls. Journal of the Operational Research Society, v. 58, p. 1630–1641, 2007. 26. WASSAN, N. A.; NAGY, G.; AHMADI, S. A heuristic method for the vehicle routing problem with mixed deliveries and pickups. Journal of Scheduling, v. 11, p.149–161, 2008.

Como citar:

Póvoa, Carlos Leonardo Ramos; Paula Jr., Geraldo Galdino de; Silva, Laura Moreira Vasconcelos Lima da; Moreira, Júlia Landeira; "PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS COM MULTICOMPARTIMENTOS COM COLETA E ENTREGA MISTA RESTRITA", p-2112-2123. In: Anais do XIX Simpósio de Pesquisa Operacional & Logística da Marinha. São Paulo: Blucher, 2020.
ISSN 21756295, DOI 10.5151/spolm2019-152