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

Authors

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

Keywords:

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

Abstract

The purpose of this work is to present a methodology to provide a solution to a Bi-objective Green Vehicle Routing Problem (BGVRP). The methodology, illustrated using a case study (newspaper distribution problem) and instances from the literature, was divided into three stages: Stage 1, data treatment; Stage 2, metaheuristic approaches (hybrid or non-hybrid), used comparatively, and, Stage 3, analysis of the results, with a comparison of the algorithms. An optimization of 19.9% was achieved for Objective Function 1 (OF1; minimization of CO2 emissions) and consequently the same percentage for the minimization of total distance, and 87.5% for Objective Function 2 (OF2; minimization of the difference in demand). Metaheuristic approaches hybrid achieved superior results for case study and instances. In this way, the procedure presented here can brings benefits to society as it considers environmental issues and also balancing work between the routes, ensuring savings and satisfaction for the users.

Downloads

Download data is not yet available.

Author Biographies

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.

References

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.