Uma Solução para o Problema de Roteirização de Veículos com Coleta e Entrega Simultâneas no Contexto da Força Aérea Brasileira
DOI:
https://doi.org/10.22480/revunifa.2011.23.636Palavras-chave:
Roteirização, Metaheurística, Transporte aéreo de carga, Busca dispersaResumo
Este trabalho apresenta uma proposta de solução para um problema da Força Aérea Brasileira (FAB), que consiste em definir os roteiros de transporte com coleta e entrega simultâneas a partir de um terminal central localizado no Rio de Janeiro, considerando frota homogênea com restrição de capacidade de peso das aeronaves. É proposto um método de solução baseado na metaheurística Busca Dispersa integrada com a metaheurística Descida em Vizinhança Variável como método de melhoria de soluções. Esta proposta de solução foi aplicada em uma instância real do problema da FAB e em três conjuntos de problemas-teste da literatura, tendo apresentado resultados indicativos de que o método desenvolvido é competitivo com outras abordagens de solução para esse problema considerando as mesmas restrições.
Referências
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
Publicado
Edição
Seção
Licença
Copyright (c) 2011 Antonio Celio Pereira de Mesquita
Este trabalho está licenciado sob uma licenç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
