Multi-objective green mixed vehicle routing problem under rough environment
Abstract
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
Keyword : green VRP, multi-objective VRP, evolutionary methods, NSGA-II, VIKOR, sustainability
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
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.