The main objective of this paper is to propose a new hybrid algorithm for
solving the Bi objective green vehicle routing problem (BGVRP) from the
BicriterionAnt metaheuristic. The methodology used is subdivided as follows: first, we introduce data from the GVRP or
instances from the literature. Second, we use the first cluster route
second technique using the k-means algorithm,
then we apply the BicriterionAntAPE (BicriterionAnt Adjacent Pairwise Exchange) algorithm to each cluster obtained. And finally, we
make a comparative analysis of the results obtained by the case study as well
as instances from the literature with some existing metaheuristics NSGA, SPEA,
BicriterionAnt in order to see the performance of the new hybrid algorithm. The
results show that the routes which minimize the total distance traveled by the
vehicles are different from those which minimize the CO2 pollution, which can be understood by the fact that the objectives are conflicting. In
this study, we also find that the optimal route reduces product CO2 by almost 7.2%
compared to the worst route.
References
[1]
Ressources naturelles Canada. Guide de consommation de carburant 2016. https://www.mcan.gc.ca/energie/efficacite/transports/voirures-camions-legers/achats/7488
[2]
Sheu, J.-B., Chou, Y.-H. and Hu, C.-C. (2005) An Integrated Logistics Operational Model for Green Supply Chain Management. Transportation Research Part E: Logistics and Transportation Review, 41, 287-313. https://doi.org/10.1016/j.tre.2004.07.001
[3]
Moutaoukil, A., et al. (2015) Minimisation des émissions de CO2 dans les circuits de distribution avec flotte hétérogène.
[4]
Rezaei, N., et al. (2019) A Green Vehicle Routing Problem with Time Windows Considering the Heterogeneous Fleet of Vehicles: Two Metaheuristic Algorithms. European Journal of Industrial Engineering, 13, 507-535.
[5]
Ferreira, J.C. and Arns Steiner, M.T. (2021) A Bi-Objective Green Vehicle Routing Problem: A New Hybrid Optimization Algorithm Applied to a Newspaper Distribution. Journal of Geographic Information System, No. 4, 410-433. https://doi.org/10.4236/jgis.2021.134023
[6]
Dutta, J., et al. (2021) A Hybrid Multi-Objective Evolutionary Algorithm for Open Green Vehicle Routing Problem through Cluster Primary-Route Secondary Approach. International Journal of Management Science and Engineering Management, 17, 132-146. https://doi.org/10.1080/17509653.2021.2000901
[7]
Zhalechian, M., Tavakkoli-Moghaddam, R., Zahiri, B. and Mohammadi, M. (2016) Sustainable Design of a Closed-Loop Location-Routing-Inventory Supply Chain Network under Mixed Uncertainty. Transportation Research Part E: Logistics and Transportation Review, 89, 182-214. https://doi.org/10.1016/j.tre.2016.02.011
[8]
Solomon, M.M. (1987) Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35, 254-265. https://doi.org/10.1287/opre.35.2.254
[9]
Bodin, L. and Golden, B. (1981) Classification in Vehicle Routing and Scheduling. Networks, 11, 97-108. https://doi.org/10.1002/net.3230110204
[10]
Baker, B.M. and Ayechew (2003) A Genetic Algorithm for the Vehicle Routing Problem. Computers OR, 30, 787-80. https://doi.org/10.1016/S0305-0548(02)00051-5
[11]
Dorigo, M. and Stuetzle, T. (2009) Ant Colony Optimization: Overview and Recent Advances. IRIDIA Technical Report Series, Technical Report, No. TR/IRIDIA/2009-013, 34 p.
[12]
Dorigo, M. (1992) Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Dipartimento di Elettronica, Politecnico di Milano. (In Italian)
[13]
Dorigo, M., Maniezzo, V. and Colorni, A. (1996) The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 29-41. https://doi.org/10.1109/3477.484436
[14]
Dorigo, M. and Gambardella, L.M. (1997) Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1, 53-66. https://doi.org/10.1109/4235.585892
[15]
Iredi, S., Merkle, D. and Middendorf, M. (2001) Bi-Criterion Optimization with Multi Colony Ant Algorithms. 1st International Conference on Evolutionary Multi-Criterion Optimization (EMO’01), Vol. 1993, 359-372. https://doi.org/10.1007/3-540-44719-9_25
[16]
Zhang, S., Lee, C.K.M., Choy, K.L., Ho, W. and Ip, W.H. (2014) Design and Development of a Hybrid Artificial Bee Colony Algorithm for the Environmental Vehicle Routing Problem. Transportation Research Part D: Transport and Environment, 31, 85-99. https://doi.org/10.1016/j.trd.2014.05.015
[17]
Dantzig, G.B. and Ramser, J.H. (1959) The Truck Dispatching Problem. Management Science, 6, 80-91. https://doi.org/10.1287/mnsc.6.1.80
[18]
Reimann, M. (2007) Analysing Risk Orientation in a Stochastic VRP. European Journal of Industrial Engineering, 1, 111-130. https://doi.org/10.1504/EJIE.2007.014105
[19]
Gansterer, M. and Hartl, R.F. (2018) Collaborative Vehicle Routing: A Survey. European Journal of Operational Research, 268, 1-12. https://doi.org/10.1016/j.ejor.2017.10.023
[20]
Moons, S., Ramaekers, K., Caris, A. and Arda, Y. (2017) Integrating Production Scheduling and Vehicle Routing Decisions at the Operational Decision Level: A Review and Discussion. Computers Industrial Engineering, 104, 224-245. https://doi.org/10.1016/j.cie.2016.12.010
[21]
Demir, E., Bektaş, T. and Laporte, G. (2014) A Review of Recent Research on Green Road Freight Transportation. European Journal of Operational Research, 237, 775-793. https://doi.org/10.1016/j.ejor.2013.12.033
[22]
Sariklis, D. and Powell, S. (2000) A Heuristic Method for the Open Vehicle Routing Problem. The Journal of the Operational Research Society, 51, 564-573. https://doi.org/10.1057/palgrave.jors.2600924
[23]
Dutta, J., Barma, P., Kar, S. and De, T. (2019) A Modified Kruskal’s Algorithm to Improve Genetic Search for Open Vehicle Routing Problem. International Journal of Business Analytics, 6, 55-57. https://doi.org/10.4018/IJBAN.2019010104
[24]
Gutierrez, A., Dieulle, L., Labadie, N. and Velasco, N. (2018) A Multi-Population Algorithm to Solve the VRP with Stochastic Service and Travel Times. Computers Industrial Engineering, 125, 144-156. https://doi.org/10.1016/j.cie.2018.07.042
[25]
Eshtehadi, R., Fathian, M. and Demir, E. (2017) Robust Solutions to the Pollution-Routing Problem with Demand and Travel Time Uncertainty. Transportation Research Part D: Transport and Environment, 51, 351-363. https://doi.org/10.1016/j.trd.2017.01.003
[26]
Kopfer, H. (2013) Emissions Minimization Vehicle Routing Problem in Dependence of Different Vehicle Classes. Springer, Berlin. https://doi.org/10.1007/978-3-642-35966-8_4
[27]
Yang, B., Hu, Z.-H., Wei, C., Li, S.-Q., Zhao, L. and Jia, S. (2015) Routing with Time-Windows for Multiple Environmental Vehicle Types. Computers Industrial Engineering, 89, 150-161. https://doi.org/10.1016/j.cie.2015.02.001
[28]
Masmoudi, M.A., Hosny, M., Demir, E. and Cheikhrouhou, N. (2018) A Study on the Heterogeneous Fleet of Alternative Fuel Vehicles: Reducing CO2 Emissions by Means of Biodiesel Fuel. Transportation Research Part D: Transport and Environment, 63, 137-155. https://doi.org/10.1016/j.trd.2018.04.025
[29]
Durillo, J.-J., Nebro, A-J., Luna, F., Dorronsoro and Alba, B.E. (2011) jMetal: A Java Framework for Multi-Objective Optimization. Advances in Engineering Software, 42, 760-771. https://doi.org/10.1016/j.advengsoft.2011.05.014
[30]
Deb, K. and Gupta, H. (2005) Searching for Robust Pareto-Optimal Solutions in Multi-Objective Optimization. International Conference on Evolutionary Multi-Criterion Optimization, Vol. 3410, 150-164. https://doi.org/10.1007/978-3-540-31880-4_11
[31]
Marler, R.-T. and Arora, J.-S. (2004) Survey of Multi-Objective Optimization Methods for Engineering. Structural and Multidisciplinary Optimization, 26, 369-395. https://doi.org/10.1007/s00158-003-0368-6
[32]
Dorigo, M., Birattari, M. and Stützle, T. (2006) Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique. IEEE Computational Intelligence Magazine, 1, 28-39. https://doi.org/10.1109/CI-M.2006.248054
[33]
Garcia-Martinez, C., Cordón, O. and Herrera, F. (2007) A Taxonomy and an Empirical Analysis of Multiple Objective Ant Colony Optimization Algorithms for the Bi-Criteria TSP. European Journal of Operational Research, 180, 116-148. https://doi.org/10.1016/j.ejor.2006.03.041
[34]
Angus, D. and Woodward, C. (2009) Multiple Objective Ant Colony Optimisation. Swarm Intelligence, 3, 69-85. https://doi.org/10.1007/s11721-008-0022-4
[35]
Romero, C.E.M. and Manzanares, E.M. (1999) MOAQ an Ant-Q Algorithm for Multiple Objective Optimization Problems. Genetic and Evolutionary Computing Conference (GECCO), Vol. 1, 894-901.
[36]
Guntsch, M. and Middendorf, M. (2003) Solving Multi-Criteria Optimization Problems with Population-Based ACO. Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization (EMO), Vol. 2632, 464-478. https://doi.org/10.1007/3-540-36970-8_33
[37]
Lopez-Ibanez, M., Paquete, L. and Stützle, T. (2004) On the Design of ACO for the Biobjective Quadratic Assignment Problem. 4th International Workshop on Ant Algorithms and Swarm Intelligence, Vol. 3172, 214-225. https://doi.org/10.1007/978-3-540-28646-2_19
[38]
Jancovici, M. (2007) Temis-Bilan carbone. Guide des facteurs d’émissions-Calcul des facteurs d’émissions et sources bibliographiques utilisées. Monographie. ADEME France, Paris.
[39]
Zitzler, E., Deb, K. and Thiele, L. (2000) Comparison of Multiobjective Evolutionary Algorithms. Empirical Result. Evolutionary Computation, 8, 173-195. https://doi.org/10.1162/106365600568202
[40]
Van Veldhuizen, D.A. (1999) Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations. PhD Thesis, Department of Electrical and Computer Engineering, Graduate School of Engineering, Air Force Institute of Technology, Wright-Patterson AFB.
