Vehicle routing problem with time windows: performance indicators for routing plans
DOI:
https://doi.org/10.5585/exactaep.2021.16430Keywords:
Routing problems, Optimize, Logistics performance evaluation.Abstract
In the literature there are many methods to solve vehicle routing problems. Such methods seek to optimize a specific parameter, such as the total distance traveled or the computational processing time. However, it is observed that some methods present or emphasize the importance of seeking results in other parameters, such as the number of vehicles in the route plan. Thus, the present study aimed to use these indicators to compare route plans generated by three well-known algorithms. For that, firstly, it was necessary to look for in the evaluation of logistical performance which indicators could be used in this comparison for later carrying out tests in the instances used by Solomon (1987). Thus, 7 indicators were proposed that showed no correlation, that is, there was no evidence of a “trade on” or “trade off” relationship between the indicators. In addition, of the methods tested, the insertion generally presented the best performance according to the proposed indicators.
Downloads
References
Alho, A., & Silva, J. A. (2014). Freight-trip generation model: predicting urban freight weekly parking demand from retail establishment characteristics. Transportation Research Record: Journal of the Transportation Research Board, 2411, 45-54. https://doi.org/10.3141/2411-06
Alvarenga, A. C., & Novaes, A. G. N. (2011). Logística aplicada: Suprimento e distribuição física (3a Ed.). São Paulo: Blucher.
ECR Brasil (1998). ECR Brasil visão geral: potencial de redução de custos e otimização de processos. (Coleção ECR Brasil). São Paulo: Associação ECR Brasil.
Ballou, R. H. (2006). Gerenciamento da Cadeia de Suprimentos / Logística Empresarial. São Paulo: Bookman.
Ballou, R. H. (2010). Gerenciamento da Cadeia de Suprimentos/ logística (5a ed.). Porto Alegre: Bookman.
Bastos, I. D. (2003). Avaliação do desempenho logístico do serviço de transporte rodoviário de cargas: um estudo de caso no setor de revestimentos cerâmicos. Dissertação de Mestrado, Programa de Pós-Graduação em Engenharia de Produção, Universidade Federal de Santa Catarina, Florianópolis.
Bodin, L.D., Gonden, B., ASSAD, A., & BALL, M. (1983). Routing and scheduling of the vehicles and crews: The state of the art. Computers and Operations Research, 10(1), Pages 63-212. https://doi.org/10.1016/0305-0548(83)90030-8
Bowersox, D., & Closs, D. (2001). Logística empresarial: o processo de integração da cadeia de suprimento. São Paulo: Atlas.
Bräysy, O., & Gendreau, M. (2005a). Vehicle Routing Problem with Time Windows, Part I: route construction and local search algorithms. Transportation Science, 39(1), 104-118. http://dx.doi.org/10.1287/trsc.1030.0056
Bräysy, O., & Gendreau, M. (2005b). Vehicle Routing Problem with Time Windows, Part II: metaheuristics. Transportation Science, 39(1), 119-139. http://dx.doi.org/10.1287/trsc.1030.0057
Chen, R. M., Shen, Y. M., & Hong, W.Z. (2019). Neural-Like Encoding Particle Swarm Optimization for Periodic Vehicle Routing Problems. Expert Systems with Applications, 138. https://doi.org/10.1016/j.eswa.2019.112833
Christopher, M. (1997). Logística e gerenciamento da cadeia de suprimentos: estratégias para a redução de custos e melhoria dos serviços. São Paulo: Pioneira.
Da Cunha, C. B. (2000). Aspectos práticos da aplicação de modelos de roteirização de veículos a problemas reais. Transportes, 8(2). https://doi.org/10.14295/transportes.v8i2.188
Da Silva Júnior, Orivalde Soares. (2013). Roteirização Estática e Dinâmica de Veículos com Janelas de Tempo. Tese de Doutorado. PUC-Rio.
Desrochers, M., Lenstra, J., Savelsbergh, M., & Soumis, F. (1988). Vehicle routing with time windows: Optimization and approximation. Veh Rout Methods Stud, 16, 65 – 84.
Faria, A. C., & Costa, M. F. G. (2005). Gestão de custos logísticos. São Paulo, Atlas.
Ge, X.; Ge, X.; Wang, W. (2020). A Path-Based Selection Solution Approach for the Low Carbon Vehicle Routing Problem with a Time-Window Constraint. Applied sciences, 10, 1-13.
Gendreau, M., Laporte, G., & Séguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1), 3-12. https://doi.org/10.1016/0377-2217(95)00050-X
Gocken, T., Yaktubay (2019). Comparason of different clustering algorithms via genetic algorithm for VRPTW, Comparison of Different Clustering Algorithms via Genetic Algorithm for VRPTW. International Journal of Simulation Modelling, 18, 574-585. https://doi.org/10.2507/IJSIMM18(4)485
Gomes, C. F. S. (2004). Gestão da cadeia de suprimento integrada: Tecnologia da Informação. São Paulo: Cengage Learning.
Golden, B. L., & Assad, A. A. (1986). Perspectives on vehicle routing: Exciting new developments. Oper. Res., 34(5), 803–809.
Golden, B. L., & Assad, A. A. (1988). Vehicle Routing: Methods and Studies. Amsterdam, Elsevier Science Publishers.
Grüdtner, I. S. (2005). Modelo de avaliação do desempenho logístico de operadores logísticos. Dissertação de Mestrado, Programa de Pós-Graduação em Engenharia de Produção, Universidade Federal de Santa Catarina, Florianópolis.
Hijjar, M. F., Gervásio, M. H., & Figueiredo, K. F. (2005). Mensuração de desempenho logístico e o modelo World Class Logistics – Parte 1 e 2. Disponível em: http://www.cel.coppead.ufrj.br/new/fs_pesquisa.html
Holmberg, S. (2000). A systems perspective on supply chain measurements. International Journal of Physical Distribution & Logistics Management, 30(10), 847-868. https://doi.org/10.1108/09600030010351246
Jayarathna, D. G. N. D., Lanel, G. H. J., & Juman Z.A.M.S. (2019). A Contemporary Recapitulation of Major Findings on Vehicle Routing Problems: models and methodologies. International Journal Of Recent Technology And Engineering, 8(24), 581-585. http://dx.doi.org/10.35940/ijrte.b1115.0782s419
Kaplan, R. S., & Norton, D. P. (1997). A estratégia em ação: balanced scorecard. Rio de Janeiro: Campus.
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. https://doi.org/10.1016/0377-2217(92)90192-C
Laporte, G., Gendreau, M., Potvin J.Y., & Semet, E. F. (2000). Classical and modern heuristics for the vehicle routing problem, International Transactions in Operational Research, 7(4), 285-300. https://doi.org/10.1111/j.1475-3995.2000.tb00200.x
MATOS JUNIOR, C. A. A., Nunes, R. V., Assis, C. W. C., Fonseca, R. C., Adriano, N. A., & Santos, G. S. (2014). Contribuição da Roteirização na Redução de Custos Logísticos e Melhoria do Nível de Serviços em Empresa do Segmento Alimentício no Ceará. ABCustos, 9(3).
MATOS JUNIOR, C. A., Nunes, R. V., Assis, C. W. C., Fonseca, R. C., Adriano, N. A., & Santos, G. S. (2013). O papel da roteirização na redução de custos logísticos e melhoria do nível de serviço em uma empresa do segmento alimentício no Ceará. In: Anais do Congresso Brasileiro de Custos-ABC.
Melo, A.C.S., & Ferreira Filho, V.J.M. (2001). Sistemas de roteirização e programação de veículos. Pesquisa Operacional. 21(2), Rio de Janeiro. https://doi.org/10.1590/S0101-74382001000200007
Mohammed, M. A., Ghani, M. K. A., Hamed, R. I., Mostafa, S. A., Ibrahim, D. A., Jameel, H. K., & Alallah, A. H. (2017). Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution. Journal of Computational Science, 21, 232–240. http://dx.doi.org/doi:10.1016/j.jocs.2017.04.012
Nasri, M., Metrane, A., Hafidi, I., & Jamali, A. (2020). A robust approach for solving a vehicle routing problem with time windows with uncertain service and travel times. International Journal Of Industrial Engineering Computations, 1-16, 2020. Growing Science. http://dx.doi.org/10.5267/j.ijiec.2019.7.002
Ñauri, M. H. (1998). As medidas de desempenho como base para a melhoria contínua de processos: o caso da Fundação de Amparo à Pesquisa e Extensão Universitaria (FAPEU). Dissertação de Mestrado, Programa de Pós-Graduação em Engenharia de Produção, Universidade Federal de Santa Catarina, Florianópolis.
Networking And Emerging Optimization. Capacitated VRP with Time Windows Instances. São Paulo, 2013. Disponível em: http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-with-time-windows-instances/
Novaes, A. G. (2007). Logística e gerenciamento da cadeia de distribuição. Rio de Janeiro: Elsevier.
Pelizaro, C. (2000). Avaliação de desempenho do algoritmo de um programa comercial para roteirização de veículos. Tese de Doutorado. Universidade de São Paulo.
Ombuki, B., Ross, B.J. & Hanshar, F. (2006). Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows. Appl Intell, 24, 17–30. https://doi.org/10.1007/s10489-006-6926-z
Raff, S. (1983). Routing and scheduling of vehicles and crews. Computers & Operations Research, 10(2), 63-211. https://doi.org/10.1016/0305-0548(83)90030-8
Reina, C. D. (2012). Roteirização de veículos com janelas de tempo utilizando algorítmo genético. Dissertação de mestrado, Departamento de Engenharia de Transporte (EPUSP), São Paulo.
Rey, M. F. (1999). Indicadores de desempenho logístico. Revista Logmam, São Paulo.
Santos, F. L., & Leal, J. E. (2006). Uma Aplicação de Algoritmos de Colônias de Formigas em Problemas de Roteirização de Veículos com Janelas de Tempo. Dissertação de Mestrado, Departamento de Engenharia Industrial, Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro.
Solomon, M. M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2), 254-265. https://doi.org/10.1287/opre.35.2.254
Waters, C. D. J. (1984). Vehicle Scheduling Revisited. The Journal of the Operational Research Society, 35(2), 145-148. https://doi.org/10.1057/jors.1984.22
Wu, L. (2007). O Problema de Roteirização Periódica de Veículos, Dissertação de Mestrado, Escola Politécnica da Universidade de São Paulo, USP, São Paulo.
Yan, L., Grifoll, M., & Zheng, P. (2020). Model and algorithm of two-stage distribution location routing with hard time window for city cold-chain logistics. Applied sciences, 10(7), p. 1-16. http://dx.doi.org/10.3390/app10072564
Zhang, C., Zhao, Y., & Leng, L. (2020). A Hyper-Heuristic Algorithm for Time-Dependent Green Location Routing Problem With Time Windows, IEEE Access, 8(1), 83092-83104. https://doi.org/10.1109/ACCESS.2020.2991411
Zheng, J. (2020). A Vehicle Routing Problem Model With Multiple Fuzzy Windows Based on Time-Varying Traffic Flow. IEEE Access, 8(1), 39439–39444. https://doi.org/10.1109/ACCESS.2020.2974774
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Exacta
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Autores que tiverem artigos aceitos para publicação na Revista Exacta concordam com os seguintes termos:
- A Cessão dos Direitos Autorais da publicação do artigo à Revista Exacta;
- Os autores que tiverem seus trabalhos aceitos e publicados na Revista Exacta estão sujeitos a Política de Direitos Autorais CC BY NC SA https://creativecommons.org/licenses/by-nc-sa/4.0/;
- A publicação do artigo pela Revista Exacta, em caráter de exclusividade e em meio eletrônico;
- A indexação do artigo em bases de dados nacionais e internacionais, diretórios, bibliotecas digitais e bases bibliométricas em que a Revista estiver e vir a estar indexada.
