Sistema para roteamento de veículos capacitados aplicando Métodos de Monte Carlo
Resumo
O Problema de Roteamento de Veículos (Vehicle Routing Problem, VRP) é um dos problemas de Otimização Combinatória mais estudados dentro da Computação e de grande relevância para as áreas de logística e transporte. Este trabalho apresenta um novo algoritmo para resolução do Problema de Roteamento de Veículos Capacitados (Capacitated Vehicle Routing Problem, CVRP), utilizando Métodos de Monte Carlo. Métodos de Monte Carlo são métodos estatísticos que utilizam amostragem aleatória para resolver problemas probabilísticos e determinísticos. O algoritmo proposto foi desenvolvido baseado em Simulações de Monte Carlo e na heurística de Clarke e Wright Savings e demonstrou resultados comparáveis aos melhores algoritmos existentes na literatura, superando trabalhos anteriores com Métodos de Monte Carlo. A comparação, análise e avaliação do algoritmo foram feitas com base em benchmarks de problemas existentes na literatura.
Palavras-chave:
Problema de Roteamento de Veículos Capacitados, Métodos de Monte Carlo, Otimização Combinatória, Algoritmos Heurísticos, Algoritmos Meta-heurísticos
Referências
B. M. Baker and M. Ayechew. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5):787–800, 2003.
C. Z. Mooney. Monte Carlo Simulation. Number 116. Sage, 1997.
D. Bindel and J. Goodman. Principles of Scientific Computing. Manuscript, 2009.
F. Takes and W. Kosters. Applying Monte Carlo techniques to the Capacitated Vehicle Routing Problem. In Proceedings of 22th Benelux Conference on Artificial Intelligence (BNAIC 2010), 2010. 8 p.
F. Takes and W. Kosters. Applying Monte Carlo Techniques to the Capacitated Vehicle Routing Problem. Master’s thesis, Leiden University, Leiden, Holanda, 2010. 61 f.
G. B. Dantzig and J. H. Ramser. The Truck Dispatching Problem. Management Science, 6(1):80–91, 1959.
G. Clarke and J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4):568–581, 1964.
G. Gutin and A. P. Punnen, editors. The traveling salesman problem and its variations. Combinatorial optimization. Kluwer Academic, Dordrecht, London, 2002.
G. Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3):345–358, 1992.
G. M. Giaglis et al. Minimizing logistics risk through real-time vehicle routing and mobile technologies: Research to date and future trends. International Journal of Physical Distribution & Logistics Management, 34(9):749–764, 2004.
G. Perboli, R. Tadei, and D. Vigo. The two-echelon capacitated vehicle routing problem: Models and math-based heuristics. Transportation Science, 45(3):364–380, 2011.
I. H. Osman and J. P. Kelly. Meta-heuristics: An overview. In Meta-Heuristics, pages 1–21. Springer, 1996.
I. J. Taneja et al. On generalized information and divergence measures and their applications: A brief review. Questiió: Quaderns d’Estadística, Sistemes, Informatica i Investigació Operativa, 13(1):47–73, 1989.
J. E. Bell and P. R. Mcmullen. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1):41–48, 2004.
J. E. Gentle. Random number generation and Monte Carlo methods. Springer Science & Business Media, 2003.
J. Faulin and A. Juan. ALGACEA-2: An entropy-based heuristics for the Capacitated Vehicle Routing Problem. In Seventh Metaheuristics International Conference, 2007. 3 p.
J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of Vehicle Routing and Scheduling Problems. Networks, 11:221–227, 1981.
J. Leeuewn. Handbook of theoretical computer science: Algorithms and complexity, volume 1. Elsevier, 1990.
J. Lysgaard, A. N. Letchford, and R. W. Eglese. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100(2):423–445, 2004.
J. Pearl. Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley Pub. Co., Inc., Reading, MA, 1984.
J. S. Christie, S. Satir, and T. P. Campus. Saving our energy sources and meeting Kyoto emission reduction targets while minimizing costs with application of vehicle logistics optimization. In 2006 Annual conference and exhibition of the Transportation Association of Canada: Transportation without boundaries, Charlottetown, Prince Edward Island, 2006.
J. Y. Kanda. Sistema de meta-aprendizado para a seleção de meta-heurística para o problema do caixeiro viajante. In Anais do X Simpósio Brasileiro de Sistemas de Informação (SBSI), Londrina, pages 651–662, 2014.
K. Shin and S. Han. A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem. Computing and Informatics, 30(4):721–732, 2011.
M. Fischetti, P. Toth, and D. Vigo. A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Operations Research, 42(5):846–859, 1994.
N. Metropolis and S. Ulam. The Monte Carlo Method. Journal of the American statistical association, 44(247):335–341, 1949.
P. Augerat. Approche polyèdrale du problème de tournées de véhicules. PhD thesis, Institut National Polytechnique de Grenoble-INPG, 1995. Disponível em. Acesso em: 24 ago 2014.
P. Toth and D. Vigo. The granular tabu search and its application to the vehicle-routing problem. Informs Journal on computing, 15(4):333–346, 2003.
P. Toth and D. Vigo. The Vehicle Routing Problem, pages 1–26. 9 edition, 2002.
T. A. Cruse. Reliability-based mechanical design, volume 108. CRC Press, 1997.
TSPLIB, 2014. Disponível em
V. P. Barbosa and R. M. Takakura. Implementação e Comparação de Algoritmos que Resolvam o Problema do Roteamento de Veículos Capacitados, 2014. Bachelor’s thesis, Escola de Artes, Ciências e Humanidades, Universidade de São Paulo, São Paulo, Brasil. 44 f.
VRPLIB: A Vehicle Routing Problem LIBrary, 2014. Disponível em. Acesso em: 24 ago 2014.
W. d. O. Bussab and P. A. Morettin. Estatística básica. Saraiva, São Paulo, 5 edition, 2004.
C. Z. Mooney. Monte Carlo Simulation. Number 116. Sage, 1997.
D. Bindel and J. Goodman. Principles of Scientific Computing. Manuscript, 2009.
F. Takes and W. Kosters. Applying Monte Carlo techniques to the Capacitated Vehicle Routing Problem. In Proceedings of 22th Benelux Conference on Artificial Intelligence (BNAIC 2010), 2010. 8 p.
F. Takes and W. Kosters. Applying Monte Carlo Techniques to the Capacitated Vehicle Routing Problem. Master’s thesis, Leiden University, Leiden, Holanda, 2010. 61 f.
G. B. Dantzig and J. H. Ramser. The Truck Dispatching Problem. Management Science, 6(1):80–91, 1959.
G. Clarke and J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4):568–581, 1964.
G. Gutin and A. P. Punnen, editors. The traveling salesman problem and its variations. Combinatorial optimization. Kluwer Academic, Dordrecht, London, 2002.
G. Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3):345–358, 1992.
G. M. Giaglis et al. Minimizing logistics risk through real-time vehicle routing and mobile technologies: Research to date and future trends. International Journal of Physical Distribution & Logistics Management, 34(9):749–764, 2004.
G. Perboli, R. Tadei, and D. Vigo. The two-echelon capacitated vehicle routing problem: Models and math-based heuristics. Transportation Science, 45(3):364–380, 2011.
I. H. Osman and J. P. Kelly. Meta-heuristics: An overview. In Meta-Heuristics, pages 1–21. Springer, 1996.
I. J. Taneja et al. On generalized information and divergence measures and their applications: A brief review. Questiió: Quaderns d’Estadística, Sistemes, Informatica i Investigació Operativa, 13(1):47–73, 1989.
J. E. Bell and P. R. Mcmullen. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1):41–48, 2004.
J. E. Gentle. Random number generation and Monte Carlo methods. Springer Science & Business Media, 2003.
J. Faulin and A. Juan. ALGACEA-2: An entropy-based heuristics for the Capacitated Vehicle Routing Problem. In Seventh Metaheuristics International Conference, 2007. 3 p.
J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of Vehicle Routing and Scheduling Problems. Networks, 11:221–227, 1981.
J. Leeuewn. Handbook of theoretical computer science: Algorithms and complexity, volume 1. Elsevier, 1990.
J. Lysgaard, A. N. Letchford, and R. W. Eglese. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100(2):423–445, 2004.
J. Pearl. Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley Pub. Co., Inc., Reading, MA, 1984.
J. S. Christie, S. Satir, and T. P. Campus. Saving our energy sources and meeting Kyoto emission reduction targets while minimizing costs with application of vehicle logistics optimization. In 2006 Annual conference and exhibition of the Transportation Association of Canada: Transportation without boundaries, Charlottetown, Prince Edward Island, 2006.
J. Y. Kanda. Sistema de meta-aprendizado para a seleção de meta-heurística para o problema do caixeiro viajante. In Anais do X Simpósio Brasileiro de Sistemas de Informação (SBSI), Londrina, pages 651–662, 2014.
K. Shin and S. Han. A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem. Computing and Informatics, 30(4):721–732, 2011.
M. Fischetti, P. Toth, and D. Vigo. A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Operations Research, 42(5):846–859, 1994.
N. Metropolis and S. Ulam. The Monte Carlo Method. Journal of the American statistical association, 44(247):335–341, 1949.
P. Augerat. Approche polyèdrale du problème de tournées de véhicules. PhD thesis, Institut National Polytechnique de Grenoble-INPG, 1995. Disponível em
P. Toth and D. Vigo. The granular tabu search and its application to the vehicle-routing problem. Informs Journal on computing, 15(4):333–346, 2003.
P. Toth and D. Vigo. The Vehicle Routing Problem, pages 1–26. 9 edition, 2002.
T. A. Cruse. Reliability-based mechanical design, volume 108. CRC Press, 1997.
TSPLIB, 2014. Disponível em
V. P. Barbosa and R. M. Takakura. Implementação e Comparação de Algoritmos que Resolvam o Problema do Roteamento de Veículos Capacitados, 2014. Bachelor’s thesis, Escola de Artes, Ciências e Humanidades, Universidade de São Paulo, São Paulo, Brasil. 44 f.
VRPLIB: A Vehicle Routing Problem LIBrary, 2014. Disponível em
W. d. O. Bussab and P. A. Morettin. Estatística básica. Saraiva, São Paulo, 5 edition, 2004.
Publicado
26/05/2015
Como Citar
OLIVEIRA, Rômulo; DELGADO, Karina.
Sistema para roteamento de veículos capacitados aplicando Métodos de Monte Carlo. In: SIMPÓSIO BRASILEIRO DE SISTEMAS DE INFORMAÇÃO (SBSI), 11. , 2015, Goiânia.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 1-8.
DOI: https://doi.org/10.5753/sbsi.2015.5795.
