Multi-objective green mixed vehicle routing problem under rough environment
DOI: https://doi.org/10.3846/transport.2021.14464Abstract
This paper proposes a multi-objective Green Vehicle Routing Problem (G-VRP) considering two types of vehicles likely company-owned vehicle and third-party logistics in the imprecise environment. Focusing only on one objective, especially the distance in the VRP is not always right in the sustainability point of view. Here we present a bi-objective model for the G-VRP that can address the issue of the emission of GreenHouse Gases (GHGs). We also consider the demand as a rough variable. This paper uses the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) to solve the proposed model. Finally, it uses Multicriteria Optimization and Compromise Solution (abbreviation in Serbian – VIKOR) method to determine the best alternative from the Pareto front.
First published online 25 February 2021
Keywords:
green VRP, multi-objective VRP, evolutionary methods, NSGA-II, VIKOR, sustainabilityHow to Cite
Share
License
Copyright (c) 2021 The Author(s). Published by Vilnius Gediminas Technical University.
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Augerat, P.; Belenguer, J. M.; Benavent, E.; Corberan, A.; Naddef, D.; Rinaldi, G. 1995. Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem. Technical Report No INPG-RR-949-M. 33 p. Available from Internet: https://www.osti.gov/etdeweb/biblio/289002
Barma, P. 2018. ZIP Archive: Rough Data. Available from Internet: https://drive.google.com/file/d/1W8pJvibW3v3mXrpz_9u0qjmvd_yLWecQ/view
Braekers, K.; Ramaekers, K.; Van Nieuwenhuyse, I. 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
Dantzig, G. B.; Ramser, J. H. 1959. The truck dispatching problem, Management Science 6(1): 80–91. https://doi.org/10.1287/mnsc.6.1.80
Deb, K.; Pratap, A.; Agarwal, 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
Demir, E.; Bektaş, T.; Laporte, G. 2014. The bi-objective pollutionrouting problem, European Journal of Operational Research 232(3): 464–478. https://doi.org/10.1016/j.ejor.2013.08.002
Ekblom, J. 2019. Air Pollution Caused 400,000 Premature European Deaths in 2016: EU Agency. Reuters. Available from Internet: https://www.reuters.com/article/us-eu-pollution/air-pollution-caused-400000-premature-european-deathsin-2016-eu-agency-idUSKBN1WV0V5
EPA. 2019a. Greenhouse Gas Emissions: Global Greenhouse Gas Emissions Data. US Environmental Protection Agency (EPA). Available from Internet: https://www.epa.gov/ghgemissions/global-greenhouse-gas-emissions-data
EPA. 2019b. Greenhouse Gas Emissions: Sources of Greenhouse Gas Emissions. US Environmental Protection Agency (EPA). Available from Internet: https://www.epa.gov/ghgemissions/sources-greenhouse-gas-emissions
Erdoğan, S.; Miller-Hooks, E. 2012. A green vehicle routing problem, Transportation Research Part E: Logistics and Transportation Review 48(1): 100–114. https://doi.org/10.1016/j.tre.2011.08.001
Gambardella, L. M.; Taillard, E.; Agazzi, G. 1999. MACSVRPTW: a multiple ant colony system for vehicle routing problems with time windows, in D. Corne, M. Dorigo, F. Glover (Eds.). New Ideas in Optimization, 63–76.
Granada, M.; Toro, E. M.; Gallego, R. 2019. An MIP formulation for the open location‐routing problem considering the topological characteristic of the solution‐paths, Networks: an International Journal 74(4): 374–388. https://doi.org/10.1002/net.21912
Granada-Echeverri, M.; Toro, E. M.; Santa, J. J. 2019. A mixed integer linear programming formulation for the vehicle routing problem with backhauls, International Journal of Industrial Engineering Computations 10(2): 295–308. https://doi.org/10.5267/j.ijiec.2018.6.003
Huang, J.; Jin, L.; Zhang, C. 2017. Mathematical modeling and a hybrid NSGA-II algorithm for process planning problem considering machining cost and carbon emission, Sustainability 9(10): 1769. https://doi.org/10.3390/su9101769
Jabir, E.; Panicker, V. V.; Sridharan, R. 2015. Multi-objective optimization model for a green vehicle routing problem, Procedia – Social and Behavioral Sciences 189: 33–39. https://doi.org/10.1016/j.sbspro.2015.03.189
Jozefowiez, N.; Semet, F.; Talbi, E.-G. 2009. An evolutionary algorithm for the vehicle routing problem with route balancing, European Journal of Operational Research 195(3): 761–769. https://doi.org/10.1016/j.ejor.2007.06.065
Jozefowiez, N.; Semet, F.; Talbi, E.-G. 2008. Multi-objective vehicle routing problems, European Journal of Operational Research 189(2): 293–309. https://doi.org/10.1016/j.ejor.2007.05.055
Kancharla, S. R.; Ramadurai, G. 2018. Incorporating driving cycle based fuel consumption estimation in green vehicle routing problems, Sustainable Cities and Society 40: 214–221. https://doi.org/10.1016/j.scs.2018.04.016
Knowles, J.; Corne, D. 1999. The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimisation, in Proceedings of the 1999 Congress on Evolutionary Computation – CEC99, 6–9 July 1999, Washington, DC, US, 98–105. https://doi.org/10.1109/CEC.1999.781913
Kundu, P.; Kar, M. B.; Kar, S.; Pal, T.; Maiti, M. 2017. A solid transportation model with product blending and parameters as rough variables, Soft Computing 21(9): 2297–2306. https://doi.org/10.1007/s00500-015-1941-9
Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. R.; Shmoys, D. B. 1985. The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization. Wiley. 476 p.
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(4): 1118–1138. https://doi.org/10.1016/j.eswa.2013.07.107
Liu, R.; Jiang, Z. 2012. The close–open mixed vehicle routing problem, European Journal of Operational Research 220(2): 349–360. https://doi.org/10.1016/j.ejor.2012.01.061
Mardani, A.; Zavadskas, E. K.; Govindan, K.; Senin, A. A.; Jusoh, A. 2016. VIKOR technique: a systematic review of the state of the art literature on methodologies and applications, Sustainability 8(1): 37. https://doi.org/10.3390/su8010037
Matl, P.; Hartl, R. F.; Vidal, T. 2018. Workload equity in vehicle routing problems: a survey and analysis, Transportation Science 52(2): 239–260. https://doi.org/10.1287/trsc.2017.0744
Matl, P.; Hartl, R. F.; Vidal, T. 2019a. Leveraging single‐objective heuristics to solve bi‐objective problems: heuristic box splitting and its application to vehicle routing, Networks: an International Journal 73(4): 382–400. https://doi.org/10.1002/net.21876
Matl, P.; Hartl, R. F.; Vidal, T. 2019b. Workload equity in vehicle routing: the impact of alternative workload resources, Computers & Operations Research 110: 116–129. https://doi.org/10.1016/j.cor.2019.05.016
Mohammed, M. A.; Abd Ghani, M. K.; 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. https://doi.org/10.1016/j.jocs.2017.04.012
Molina, J. C.; Eguia, I.; Racero, J.; Guerrero, F. 2014. Multi-objective vehicle routing problem with cost and emission functions, Procedia – Social and Behavioral Sciences 160: 254–263. https://doi.org/10.1016/j.sbspro.2014.12.137
Montoya, A.; Gueret, C.; Mendoza, J. E.; Villegas, J. G. 2016. A multi-space sampling heuristic for the green vehicle routing problem, Transportation Research Part C: Emerging Technologies 70: 113–128. https://doi.org/10.1016/j.trc.2015.09.009
Murata, T.; Itai, R. 2007. Local search in two-fold EMO algorithm to enhance solution similarity for multi-objective vehicle routing problems, Lecture Notes in Computer Science 4403: 201–215. https://doi.org/10.1007/978-3-540-70928-2_18
Murata, T.; Itai, R. 2005. Multi-objective vehicle routing problems using two-fold EMO algorithms to enhance solution similarity on non-dominated solutions, Lecture Notes in Computer Science 3410: 885–896. https://doi.org/10.1007/978-3-540-31880-4_61
NEO. 2013. Capacitated VRP Instances. Networking and Emerging Optimization (NEO), Malaga, Spain. Available from Internet: https://neo.lcc.uma.es/vrp/vrp-instances/capacitatedvrp-instances
Ombuki, B.; Ross, B. J.; Hanshar, F. 2006. Multi-objective genetic algorithms for vehicle routing problem with time windows, Applied Intelligence 24(1): 17–30. https://doi.org/10.1007/s10489-006-6926-z
Pacheco, J.; Marti, R. 2006. Tabu search for a multi-objective routing problem, Journal of the Operational Research Society 57(1): 29–37. https://doi.org/10.1057/palgrave.jors.2601917
Poonthalir, G.; Nadarajan, R. 2018. A fuel efficient green vehicle routing problem with varying speed constraint (F-GVRP), Expert Systems with Applications 100: 131–144. https://doi.org/10.1016/j.eswa.2018.01.052
Qian, J.; Eglese, R. 2014. Finding least fuel emission paths in a network with time‐varying speeds, Networks: an International Journal 63(1): 96–106. https://doi.org/10.1002/net.21524
Qian, J.; Eglese, R. 2016. Fuel emissions optimization in vehicle routing problems with time-varying speeds, European Journal of Operational Research 248(3): 840–848. https://doi.org/10.1016/j.ejor.2015.09.009
Ralphs, T. 2003. Vehicle Routing Data Sets. Lehigh University, Bethlehem, PA, US. Available from Internet: https://www.coin-or.org/SYMPHONY/branchandcut/VRP/data/index.htm.old
Ribeiro, R.; Lourenco, H. R. D. 2001. A Multi-Objective Model for a Multi-Period Distribution Management Problem. Social Science Research Network (SSRN). 22 p. https://doi.org/10.2139/ssrn.273419
Schrijver, A. 2002. On the history of combinatorial optimization (till 1960), Handbooks in Operations Research and Management Science 12: 1–68. https://doi.org/10.1016/S0927-0507(05)12001-5
Siu, W. S. H.; Chan, C.-K.; Chan, H. C. B. 2012. Green cargo routing using genetic algorithms, in International MultiConference of Engineers and Computer Scientists, IMECS 2012, 14–16 March 2012, Kowloon, Hong Kong, 1: 170–175.
Tan, K. C.; Chew, Y. H.; Lee, L. H. 2006. A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows, Computational Optimization and Applications 34(1): 115–151. https://doi.org/10.1007/s10589-005-3070-3
Toro, E. M.; Franco, J. F.; Granada-Echeverri, M.; Guimaraes, F. G. 2017a. A multi-objective model for the green capacitated location-routing problem considering environmental impact, Computers & Industrial Engineering 110: 114–125. https://doi.org/10.1016/j.cie.2017.05.013
Toro, E. M.; Franco, J. F.; Granada-Echeverri, M.; Guimaraes, F. G.; Rendon, R. A. G. 2017b. Green open location-routing problem considering economic and environmental costs, International Journal of Industrial Engineering Computations 8(2): 203–216. https://doi.org/10.5267/j.ijiec.2016.10.001
Turkson, R. F.; Yan, F.; Ali, M. K. A.; Liu, B.; Hu, J. 2016. Modeling and multi-objective optimization of engine performance and hydrocarbon emissions via the use of a computer aided engineering code and the NSGA-II genetic algorithm, Sustainability 8(1): 72. https://doi.org/10.3390/su8010072
VRP-REP. 2018. Datasets. Vehicle Routing Problem Repository (VRP-REP). Available from Internet: http://www.vrp-rep.org/datasets.html
Wen, L.; Eglese, R. 2016. Minimizing CO2e emissions by setting a road toll, Transportation Research Part D: Transport and Environment 44: 1–13. https://doi.org/10.1016/j.trd.2015.12.019
Xiao, Y.; Zhao, Q.; Kaku, I.; Xu, Y. 2012. Development of a fuel consumption optimization model for the capacitated vehicle routing problem, Computers & Operations Research 39(7): 1419–1431. https://doi.org/10.1016/j.cor.2011.08.013
Zhou, J.; Wang, C.; Zhu, J. 2016. Multi-objective optimization of a spring diaphragm clutch on an automobile based on the non-dominated sorting genetic algorithm (NSGA-II), Mathematical and Computational Applications 21(4): 47. https://doi.org/10.3390/mca21040047
Zitzler, E.; Laumanns, M.; Thiele, L. 2001. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report 103. Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Switzerland. 21 p.
View article in other formats
CrossMark check
Published
Issue
Section
Copyright
Copyright (c) 2021 The Author(s). Published by Vilnius Gediminas Technical University.
License
This work is licensed under a Creative Commons Attribution 4.0 International License.