A Solution to the Problem of Vehicle Routing with Collection and Simultaneous Delivery in the Context of Force Brazilian Air
DOI:
https://doi.org/10.22480/revunifa.2011.23.636Keywords:
Routing, Metaheuristic, Air cargo transportation, Scatter searchAbstract
This article presents a solution for a problem which arises in the Brazilian Air Force (FAB), that consists in defining the simultaneous pickup and delivery routes for the transportation of goods from a distribution center in Rio de Janeiro, considering a homogeneous fleet with a restriction on the weight capacity of the aircrafts. It is proposed a method of solution based on the Scatter Search metaheuristic integrated with the Variable Neighborhood Descent metaheuristic used as a method of solution improvement. This proposal of solution was applied to a real instance of the Brazilian Air Force problem and to three- problem sets of the literature, as well. The results showed that the proposed method is competitive with other approaches for the solution of that problem, considering the same restrictions.
References
ANILY, S. The vehicle routing problem with delivery and backhaul options. Naval Research Logistics, v. 43, p. 415-434, 1996.
BEASLEY, J.E.: Route first: cluster second methods for vehicle routing. Omega, v. 11, p. 403-408, 1983.
BALLOU, R.H., Business Logistics Management: planning, organizing and controlling the supply chain. 4. ed. [ S.l.]: Prentice Hall, 1999.
BELFIORE, P. P. Scatter Search para problemas de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas. Tese (Doutorado) - Escola Politécnica, Universidade de São Paulo, São Paulo, 2006.
BELMORE M.; NEMHAUSER, G. L. The traveling salesman problem: a survey. Operations Research, V. 538-558, 1968.
BIANCHESSI, N.; RIGHINI, G. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers and Operations Research, v. 34, p. 578-594, 2007.
CHEN, J. F.; WU, T. H. Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, v. 57, p. 579-587, 2006.
CLARKE, G.; WRIGHT, J. W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, v.12, n.4, p. 568-581, 1964.
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, p. 1296-1302, 2005.
CROES, G.A. A method for solving the Traveling Salesman Problems. Operations Research, n. 6, p. 791-812, 1958.
DETHLOFF, J. Vehicle routing and reverse logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-up. OR Spektrum, v. 23, p. 79-96. 2001.
DUARTE, A.; MARTÍ, R.; GLOVER, F.; GORTAZAR, F. Hybrid scatter tabu search for unconstrained global otimization. Annals of Operations Research, Springer Netherlands, Aug, 2009.
FEO, T.A;. e RESENDE, M.G.C. Greedy randomized adaptive search procedures. Journal Global Optimization, n. 6, p. 109-133. 1995.
FREITAS, L. M. B.; ARROYO, J. E. C.; MONTANÉ, F. A. T. Heurística VNS para o Problema de Roteamento de Veículos com Coleta e Entrega Simultânea. In: Simpósio de Pesquisa Operacional e Logística da Marinha - SPOLM, 10, Rio de Janeiro, 2007.
GAJPAL, Y.; PRAKASH, A. An Ant Colony System (ACS) for Vehicle Routing Problem with Simultaneous Delivery and Pickup. Computers & Operations Research,Ontario, Canada, p. 1-9, mar. 2009.
GENDREAU, M.; HERTZ, A.; LAPORTE, G. New Insertion and Postoptimization Procedures for the Traveling Salesman Problem. Operations Research, v. 40, n. 6, p. 1086-1094, 1992.
GLOVER, F. A Template for Scatter Search and Path Relinking. In. HAO, J. K. et al. Lecture Notes in Computer Science. Springer:[ s.n.], 1998, p. 13-54.
GÖKÇE, E. I. A revised ant colony system approach to vehicle routing problems. Turkey: Sabanci University, 2004.
KESKIN, B. B., ÜSTER, H. A Scatter Search based heuristic to locate capacitated transshipment points. Computers and Operations Research. n. 34, p. 3112-3125, 2007.
MESQUITA, A. C. P. A meta-heurística Busca Dispersa em Problemas de Roteirização de Veículos com Coleta e Entrega Simultâneas: Aplicação na Força Aérea Brasileira. Dissertação (Mestrado) - Programa de Engenharia de Sistemas Logísticos. Escola Politécnica, Universidade de São Paulo, São Paulo, 2010.
MIN, H. The multiple the vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part , v. 5, p. 377-386, 1989.
MINE, M. T.; SILVA, M. S. A.; OCHI, L. S.; SOUZA, M. J. F. Um algoritmo heurístico híbrido para o Problema de Roteamento de Veículos com Entrega e Coleta Simultânea. In: ENCONTRO NACIONAL DE ENGENHARIA DE PRODUÇÃO, 29, 2009, A Engenharia de Produção e o Desenvolvimento Sustentável:Integrando Tecnologia e Gestão. Salvador, BA, 2009.
MONTANÉ, F. A. T.; GALVÃO, R. D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers and Operations Research, v. 33, p. 595-619, 2006.
MLADENOVIC, N.; HANSEN, P. Variable neighborhood Search. Computers and Operations Research, v. 24, p. 1097-1100, 1997.
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.
Downloads
Published
Issue
Section
License
Copyright (c) 2011 Antonio Celio Pereira de Mesquita
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Revista da UNIFA permite que o (s) autor (es) mantenha(m) seus direitos autorais sem restrições. Atribuição-NãoComercial 4.0 Internacional (CC BY-NC 4.0) - Revista da UNIFA é regida pela licença CC-BY-NC
