Uma nova abordagem para o problema de roteamento de veículos green bi-objetivo: otimização na distribuição de jornais

Júlio César Ferreira; Maria Teresinha Arns Steiner

doi:10.5585/exactaep.2021.18447

Autores

Júlio César Ferreira Pontifícia Universidade Católica do Paraná – PUCPR https://orcid.org/0000-0001-7525-672X
Maria Teresinha Arns Steiner Pontifícia Universidade Católica do Paraná - PUCPR https://orcid.org/0000-0002-8712-7957

DOI:

https://doi.org/10.5585/exactaep.2021.18447

Palavras-chave:

Problema de Roteamento de Veículos Green Bi-objetivo, Logística Verde, Procedimentos meta-heurísticos, Estudo de caso, Instâncias da literatura.

Resumo

O objetivo deste trabalho é apresentar uma metodologia para fornecer uma solução para o Problema de Roteamento de Veículos Green Bi-objetivo (Bi-objective Green Vehicle Routing Problem, BGVRP). A metodologia, ilustrada por meio de um estudo de caso (problema de distribuição de jornais) e instâncias da literatura, foi dividida em três etapas: Etapa 1, tratamento dos dados; Etapa 2, abordagens meta-heurísticas (híbridas ou não híbridas), utilizadas comparativamente; Etapa 3, análise dos resultados, com comparação dos algoritmos. Uma otimização de 19,9% foi alcançada para a Função Objetivo 1 (FO1; minimização das emissões de CO2) e, consequentemente, o mesmo percentual para a minimização da distância total, e 87,5% para a Função Objetivo 2 (FO2; minimização da diferença na demanda). Abordagens meta-heurísticas híbridas alcançaram resultados superiores para o estudo de caso e as instâncias. Desta forma, o procedimento aqui apresentado poderá trazer benefícios para a sociedade já que considera questões ambientais, além do balanceamento do trabalho entre os roteiros, garantindo economia e satisfação para possíveis usuários.

Downloads

Não há dados estatísticos.

Biografia do Autor

Júlio César Ferreira, Pontifícia Universidade Católica do Paraná – PUCPR

Ph.D. in Production Engineering and Systems at the Pontifícia Universidade Católica do Paraná (2020). Professor in Engineering Department at Unicuritiba University Center of Curitiba, Paraná, Brazil.

Maria Teresinha Arns Steiner, Pontifícia Universidade Católica do Paraná - PUCPR

Postdoctoral at ITA (2005) and IST Lisbon (2014). She worked at Universidade Federal do Paraná (UFPR) from August 1978 to October 2010. Since February 2011, she has been working at PPGEPS/PUCPR. She has experience in Operational Research topics.

Referências

Abad, H. K. E. A., Vahdani, B., Sharifi, M., & Etebari, F. (2018). A bi-objective model for pickup and delivery pollution-routing problem with integration and consolidation shipments in cross-docking system. J. Clean. Prod., 193, 784–801. https://doi.org/10.1016/j.jclepro.2018.05.046.

Amer, H., Salman, N., Hawes, M., Chaqfeh, M., Mihaylova, L., & Mayfield, M. (2016). An improved simulated annealing technique for enhanced mobility in smart cities. Sensors (Switzerland), 16, 1-23. https://doi.org/10.3390/s16071013.

Braekers, K., Ramaekers, K., & Nieuwenhuyse, I. V. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313. https://doi.org/10.1016/j.cie.2015.12.007.

Carvalho, C. H. R. (2011). 1606: Texto para discussão. Emissões relativas de poluentes do transporte motorizado de passageiros nos grandes centros urbanos brasileiros. Instituto de Pesquisa Econômica Aplicada (IPEA), Brasília, april, 2011.

Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568–582. https://www.jstor.org/stable/167703.

Coello, C. A. (2000). MOPSO: a proposal for multiple objective particle swarm optimization. Proceedings of the 2002 Congress on Evolutionary Computation, 2, CEC 2002, 1051-1056. https://doi.org/10.1109/CEC.2002.1004388.

Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6, 80-91. https://www.jstor.org/stable/2627477.

Deb, K., Pratap. A., Aguarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197. https://doi.org/10.1109/4235.996017.

Deb, K. (2001). Multi-objective optimization using evolutionary algorithms. [S.l.]: John Wiley & Sons, Inc.

Demir, E., Bektas, T., & Laporte, G. (2014). A review of recent research on green road freight transportation. European Journal of Operational Research, 237(3), 775-793. https://doi.org/10.1016/j.ejor.2013.12.033.

Ebrahimi, S. B. (2018). A stochastic multi-objective location-allocation-routing problem for tire supply chain considering sustainability aspects and quantity discounts. J. Clean. Prod., 198, 704-720. https://doi.org/10.1016/j.jclepro.2018.07.059.

Ehrgott, M., Wang, J. Y. T., Raith, A., & Van Houtte, C. (2012). A bi-objective cyclist route choice model. Transp. Res. Part A Policy Pract, 46, 652–663. https://doi.org/10.1016/j.tra.2011.11.015.

Erdelic, T., & Caric, T. (2019). A Survey on the Electric Vehicle Routing Problem: Variants and Solution Approaches. Journal of Advanced Transportation, 2019, 1-48. https://doi.org/10.1155/2019/5075671.

Fathollahi-Fard, A. M., Hajiaghaei-Keshteli, M. H. K., & Tavakkoli-Moghaddam, R. (2018). A Bi-objective green home health care routing problem. J. Clean. Prod, 200, 423–443. https://doi.org/10.1016/j.jclepro.2018.07.258.

Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124. https://doi.org/10.1002/net.3230110205.

Fu, P., Li, H., Wang, X., Luo, J., Zhan, S.L., & Zuo, C. (2017). Multiobjective Location Model Design Based on Government Subsidy in the Recycling of CDW. Math. Probl. Eng. 1-9. https://doi.org/10.1155/2017/9081628.

Ferreira, J. C., Steiner, M. T. A., & Guersola, M. S. (2017). A Vehicle Routing Problem Solved Through Some Metaheuristics Procedures: A Case Study. IEEE Latin America Transactions, 15(5), 943-949. https://doi.org/10.1109/TLA.2017.7910210.

Ghezavati, V. R., & Beigi, M. (2016). Solving a bi-objective mathematical model for location-routing problem with time windows in multi-echelon reverse logistics using metaheuristic procedure. Journal of Industrial Engineering International, 12, 469–483. https://doi.org/10.1007/s40092-016-0154-x.

Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers an Operational Research, 13(5), 533-549. https://doi.org/10.1016/0305-0548(86)90048-1.

Gong, X., Deng, Q., Gong, X., Zhang, L., Wang, H., & Xie, H. (2018). A Bee Evolutionary Algorithm for multiobjective Vehicle Routing Problem with Simultaneous Pickup and Delivery. Math. Probl. Eng. 1–21. https://doi.org/10.1155/2018/2571380.

Hassanzadeh, A., & Rasti-Barzoki, M. (2017). Minimizing total resource consumption and total tardiness penalty in a resource allocation supply chain scheduling and vehicle routing problem. Applied Soft Computing, 58, 307–323. https://doi.org/10.1016/j.asoc.2017.05.010.

Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press.

Kennedy, J., Eberhart, R. C., & Shi, Y. (2001). Swarm Intelligence, vol. 1. Kaufmann, San Francisco, p. 700-720.

Kumar, R. S., Kondapaneni, K., Dixit, V., Goswami, A., Thakur, L. S., & Tiwari, M. K. (2016). Multi-objective modeling of production and pollution routing problem with time window: A self-learning particle swarm optimization approach. Computers and Industrial Engineering, 99, 29–40. https://doi.org/10.1016/j.cie.2015.07.003.

Lin, C., Choy, K. L., Ho, G. T. S., Chung, S. H., & Lam, H. Y. (2014). Survey of Green Vehicle Routing Problem: Past and future trends. Expert Systems with Applications, 41, 1118-1138. https://doi.org/10.1016/j.eswa.2013.07.107.

Liu, X. H., Shan, M. Y., Zhang, R. L., & Zhang, L. H. (2018). Green Vehicle Routing Optimization Based on Carbon Emission and Multiobjective Hybrid Quantum Immune Algorithm. Math. Probl. Eng., 1-9. https://doi.org/10.1155/2018/8961505.

NEO. Networking and Emerging Optimization. Capacitated VRP Instances. In: < http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/ >. In: jun, 3, 2019.

Norouzi, N., Sadegh-Amalnick, M., & Tavakkoli-Moghaddam, R. (2017). Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption. Optimization Letters, 11, 121–134. https://doi.org/10.1007/s11590-015-0996-y.

Poterba, J. M., & Rotemberg, J. (2018). Money in the Utility Function: An Empirical Implementation. Creative Media Partners: LLC.

Psychas, I. D., Marinaki, M., Marinakis, Y., & Migdalas, A. (2017). Non-dominated sorting differential evolution algorithm for the minimization of route based fuel consumption multiobjective vehicle routing problems. Energy Syst, 8, 785–814. https://doi.org/10.1007/s12667-016-0209-5.

Rabbani, M., Saravi, N. A., & Farrokhi-Asl, H. (2017). Design of a forward/reverse logistics network with environmental considerations. Int. J. Supply Oper. Manag., 4, 115–132. https://doi.org/10.22034/2017.2.02.

Sawik, B., Faulin, J., & Pérez-Bernabeu, E. (2017). A Multicriteria Analysis for the Green VRP: A Case Discussion for the Distribution Problem of a Spanish Retailer. Transportation Research Procedia, 22, 305-313. https://doi.org/10.1016/j.trpro.2017.03.037.

Soleimani, H., Chaharlang, Y., & Ghaderi, H. (2018). Collection and distribution of returned-remanufactured products in a vehicle routing problem with pickup and delivery considering sustainable and green criteria. J. Clean. Prod., 172, 960-970. https://doi.org/10.1016/j.jclepro.2017.10.124.

Steiner, M. T. A., Datta, D., Steiner Neto, P. J., Scarpin, C. T., & Figueira, J. R. (2015). Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil. Omega, 52, 53-64. https://doi.org/10.1016/j.omega.2014.10.005.

Subramanian, A., Penna, P. H. V., Ochi, L. S., & Souza, M. J. F. (2013). Um algoritmo heurístico baseado em iterated local search para problemas de roteamento de veículos. In: Lopes, H. S., Rodrigues, L. C. A., Steiner, M. T. A. (eds.) Meta-Heurísticas em Pesquisa Operacional. Ed. Omnipax, Curitiba, Brazil.

Toro, E. M., Franco, J. F., Echeverri, M. G., & Guimarães, F. G. (2017). A multi-objective model for the green capacitated location-routing problem considering environmental impact. Computers and Industrial Engineering, 110, 114–125. https://doi.org/10.1016/j.cie.2017.05.013.

Validi, S., Bhattacharya, A., & Byrne, P. J. (2015). A solution method for a two-layer sustainable supply chain distribution model. Computers & Operations Research, 54, 204–217. https://doi.org/10.1016/j.cor.2014.06.015.

Wang, Y., Peng, S., Assogba, K., Liu, Y., Wang, H., Xu, M., & Wang, Y. (2018). Implementation of cooperation for recycling vehicle routing optimization in two-echelon reverse logistics networks. Sustain, 10(5), https://doi.org/10.3390/su10051358.

Wang, Z., Leng, L., Wang, S., Li, G., & Zhao, Y. (2020). A Hyperheuristic Approach for Location-Routing Problem of Cold Chain Logistics considering Fuel Consumption. Computational Intelligence and Neuroscience, 2020, 1-17. https://doi.org/10.1155/2020/8395754.