Particle Swarm Optimization Algorithm to Solve Vehicle Routing Problem with Fuel Consumption Minimization

  Author(s)
Baiq Nurul Izzah Farida Ramadhani (Universitas Muhammadiyah Malang - Indonesia)
Annisa Kesy Garside    (Universitas Muhammadiyah Malang - Indonesia)

 ) Corresponding Author
Copyright (c) 2021 Baiq Nurul Izzah Farida Ramadhani, Annisa Kesy Garside
  Abstract
The Conventional Vehicle Routing Problem (VRP) has the objective function of minimizing the total vehicles’ traveling distance. Since the fuel cost is a relatively high component of transportation costs, in this study, the objective function of VRP has been extended by considering fuel consumption minimization in the situation wherein the loading weight and traveling time are restricted. Based on these assumptions, we proposed to extend the route division procedure proposed by Kuo and Wang [4] such that when one of the restrictions can not be met the routing division continues to create a new sub-route to find an acceptable solution. To solve the formulated problem, the Particle Swarm Optimization (PSO) algorithm is proposed to optimize the vehicle routing plan. The proposed methodology is validated by solving the problem by taking a particular day data from a bottled drinking water distribution company. It was revealed that the saving of at best 13% can be obtained from the actual routes applied by the company.
  Keywords
Vehicle routing problem; loading weight; traveling time; fuel consumption; Particle Swarm Optimization
  Click to Read the Full Text
PDF
  References

[1] Y. Xiao, Q. Zhao, I. Kaku, and Y. Xu, "Development of a fuel consumption optimization model for the capacitated vehicle routing problem," Computers & Operations Research, vol. 39, no. 7, pp. 1419-1431, 2012. https://doi.org/10.1016/j.cor.2011.08.013.

[2] A. Montoya, C. Guéret, J. E. Mendoza, and J. G. Villegas, "A multi-space sampling heuristic for the green vehicle routing problem," Transportation Research, vol. 70, pp. 113-128, 2016. https://doi.org/10.1016/j.trc.2015.09.009.

[3] G. Poonthalir and R. Nadarajan, "A fuel efficient green vehicle routing problem with varying speed constraint (F-GVRP)," Expert Systems with Applications, vol. 100, pp. 131-144, 2018. https://doi.org/10.1016/j.eswa.2018.01.052.

[4] Y. Kuo and C.-C. Wang, "Optimizing the VRP by minimizing fuel consumption," Management of Environmental Quality: An International Journal, vol. 22, no. 4, pp. 440-450, 2011. https://doi.org/10.1108/14777831111136054.

[5] D. R. Gaur, A. Mudgal, and R. R. Singh, "Routing vehicles to minimize fuel consumption," Operations Research Letters, vol. 41, no. 6, pp. 576-580, 2013. https://doi.org/10.1016/j.orl.2013.07.007

[6] Z. Zhang, L. Wei, and A. Lim, "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints," Transportation Research Part B: Methodological, vol. 82, pp. 20-35, 2015. https://doi.org/10.1016/j.trb.2015.10.001.

[7] S. Erdoğan and E. Miller-Hooks, "A green vehicle routing problem," Transportation research part E: logistics and transportation review vol. 48, no. 1, pp. 100-114, 2012. https://doi.org/10.1016/j.tre.2011.08.001.

[8] C. Lin, "A vehicle routing problem with pickup and delivery time windows, and coordination of transportable resources," Computers & Operations Research vol. 38, no. 11, pp. 1596-1609, 2011. https://doi.org/10.1016/j.cor.2011.01.021.

[9] A. S. Tasan and M. Gen, "A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries," Computers & Industrial Engineering, vol. 62, no. 3, pp. 755-761, 2012. https://doi.org/10.1016/j.cie.2011.11.025.

[10] . B. Dantzig and J. H. Ramser, "The truck dispatching problem," Management science, vol. 6, no. 1, pp. 80-91, 1959. https://doi.org/10.1287/mnsc.6.1.80.

[11] K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, "The vehicle routing problem: State of the art classification and review," Computers & Industrial Engineering, vol. 99, pp. 300-313, 2016. https://doi.org/10.1016/j.cie.2015.12.007

[12] G. Desaulniers, The VRP with pickup and delivery. Groupe d'études et de recherche en analyse des décisions, 2000. https://doi.org/10.1016/j.eswa.2016.01.038

[13] M. Avci and S. Topaloglu, "A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery," Expert Systems with Applications, vol. 53, pp. 160-171, 2016. https://doi.org/10.1109/TLA.2018.8444393

[14] C. Lagos, G. Guerrero, E. Cabrera, A. Moltedo, F. Johnson, and F. Paredes, "An improved particle swarm optimization algorithm for the VRP with simultaneous pickup and delivery and time windows," IEEE Latin America Transactions, vol. 16, no. 6, pp. 1732-1740, 2018. https://doi.org/10.1109/TLA.2018.8444393.

[15] T. Zhang, W. A. Chaovalitwongse, and Y. Zhang, "Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries," Computers & Operations Research, vol. 39, no. 10, pp. 2277-2290, 2012. https://doi.org/10.1016/j.cor.2011.11.021.

[16] M. Akhtar, M. Hannan, R. Begum, H. Basri, and E. Scavino, "Backtracking search algorithm in CVRP models for efficient solid waste collection and route optimization," Waste Management, vol. 61, pp. 117-128, 2017. https://doi.org/10.1016/j.wasman.2017.01.022.

[17] J. Oyola and A. Løkketangen, "GRASP-ASP: An algorithm for the CVRP with route balancing," Journal of Heuristics, vol. 20, no. 4, pp. 361-382, 2014. https://doi.org/10.1007/s10732-014-9251-4.

[18] Y. Kao and M. Chen, "Solving the CVRP problem using a hybrid PSO approach," in Computational Intelligence: Springer, 2013, pp. 59-67. https://doi.org/10.1007/978-3-642-35638-4_5.

[19] E. G. C. Franco, J. A. H. Aguilar, A. Ochoa-Zezzatti, and J. C. P. Gallegos, "Comparison between instances to solve the CVRP," International Journal of Combinatorial Optimization Problems and Informatics, vol. 9, no. 2, pp. 41-54, 2018.

[20] G. Laporte and F. Semet, "Classical heuristics for the capacitated VRP," in The vehicle routing problem: SIAM, 2002, pp. 109-128. https://doi.org/10.1137/1.9780898718515.ch5.

[21] A. M. Benjamin and J. Beasley, "Metaheuristics with disposal facility positioning for the waste collection VRP with time windows," Optimization Letters, vol. 7, no. 7, pp. 1433-1449, 2013. https://doi.org/10.1007/s11590-012-0549-6.

[22] A. Garcia-Najera and J. A. Bullinaria, "An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows," Computers & Operations Research, vol. 38, no. 1, pp. 287-300, 2011. https://doi.org/10.1016/j.cor.2010.05.004.

[23] S. R. Balseiro, I. Loiseau, and J. Ramonet, "An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows," Computers & Operations Research, vol. 38, no. 6, pp. 954-966, 2011. https://doi.org/10.1016/j.cor.2010.10.011.

[24] K. Buhrkal, A. Larsen, and S. Ropke, "The waste collection vehicle routing problem with time windows in a city logistics context," Procedia-Social and Behavioral Sciences, vol. 39, pp. 241-254, 2012. https://doi.org/10.1016/j.sbspro.2012.03.105.

[25] B. Yu and Z. Z. Yang, "An ant colony optimization model: The period vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review vol. 47, no. 2, pp. 166-181, 2011. https://doi.org/10.1016/j.tre.2010.09.010.

[26] US Department of Energy.(2008). Fuel economy guide. Available: www.fueleconomy.gov. [Accessed : Dec 28, 2020]

[27] R. Eglese and T. Bekta¸ s, "Chapter 15: Green vehicle routing," in Vehicle Routing: Problems, Methods, and Applications, Second Edition: SIAM, 2014, pp. 437-458. https://doi.org/10.1137/1.9781611973594.ch15.

[28] Y. Kuo, "Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem," Computers & Industrial Engineering, vol. 59, no. 1, pp. 157-165, 2010. https://doi.org/10.1016/j.cie.2010.03.012.

[29] A. L. Kok, E. W. Hans, and J. M. Schutten, "Vehicle routing under time-dependent travel times: the impact of congestion avoidance," Computers & operations research, vol. 39, no. 5, pp. 910-918, 2012. https://doi.org/10.1016/j.cor.2011.05.027.

[30] Z. Duan, S. Sun, S. Sun, and W. Li, "Stochastic time-dependent vehicle routing problem: Mathematical models and ant colony algorithm," Advances in Mechanical Engineering, vol. 7, no. 11, p. 1687814015618631, 2015. https://doi.org/10.1177/1687814015618631.

[31] J. Qian and R. Eglese, "Fuel emissions optimization in vehicle routing problems with time-varying speeds," European Journal of Operational Research, vol. 248, no. 3, pp. 840-848, 2016. https://doi.org/10.1016/j.ejor.2015.09.009.

[32] N. Norouzi, M. Sadegh-Amalnick, and R. Tavakkoli-Moghaddam, "Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption," Optimization Letters, vol. 11, no. 1, pp. 121-134, 2017. https://doi.org/10.1007/s11590-015-0996-y.

[33] A. Montoya, C. Guéret, J. E. Mendoza, and J. G. Villegas, "The electric vehicle routing problem with nonlinear charging function," Transportation Research Part B: Methodological, vol. 103, pp. 87-110, 2017. https://doi.org/10.1016/j.trb.2017.02.004.

[34] M. Tavakoli and A. Sami, "Particle Swarm Optimization in Solving Capacitated Vehicle Routing Problem," Bulletin of Electrical Engineering and Informatics, vol. 2, no. 4, pp. 252-257, 2013. https://doi.org/10.12928/eei.v2i4.190.

[35] F. P. Goksal, I. Karaoglan, and F. Altiparmak, "A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery," Computers & Industrial Engineering, vol. 65, no. 1, pp. 39-53, 2013. https://doi.org/10.1016/j.cie.2012.01.005.

[36] T. J. Ai and V. Kachitvichyanukul, "A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery," Computers & Operations Research, vol. 36, no. 5, pp. 1693-1702, 2009. https://doi.org/10.1016/j.cor.2008.04.003.

[37] T. J. Ai and V. Kachitvichyanukul, "Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem," Computers & Industrial Engineering, vol. 56, no. 1, pp. 380-387, 2009. https://doi.org/10.1016/j.cie.2008.06.012.

[38] Y. Marinakis, G.-R. Iordanidou, and M. Marinaki, "Particle swarm optimization for the vehicle routing problem with stochastic demands," Applied Soft Computing, vol. 13, no. 4, pp. 1693-1704, 2013. https://doi.org/10.1016/j.asoc.2013.01.007.

[39] S. MirHassani and N. Abolghasemi, "A particle swarm optimization algorithm for open vehicle routing problem," Expert Systems with Applications, vol. 38, no. 9, pp. 11547-11551, 2011. https://doi.org/10.1016/j.eswa.2011.03.032.

[40] M. Hannan, M. Akhtar, R. Begum, H. Basri, A. Hussain, and E. Scavino, "Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm," Waste management, vol. 71, pp. 31-41, 2018. https://doi.org/10.1016/j.wasman.2017.10.019.

[41] Y. W. Zhao, B. Wu, W. Wang, Y. L. Ma, W. Wang, and H. Sun, "Particle swarm optimization for vehicle routing problem with time windows," in Materials Science Forum, 2004, vol. 471, pp. 801-805: Trans Tech Publ. https://doi.org/10.4028/www.scientific.net/MSF.471-472.801.

[42] D. Wang, D. Tan, and L. J. S. C. Liu, "Particle swarm optimization algorithm: an overview," vol. 22, no. 2, pp. 387-408, 2018. https://doi.org/10.1007/s00500-016-2474-6.

[43] Q. Bai, "Analysis of particle swarm optimization algorithm," Computer and information science, vol. 3, no. 1, p. 180, 2010. https://doi.org/10.5539/cis.v3n1p180.

[44] Y. Marinakis and M. Marinaki, "A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem," Computers & Operations Research vol. 37, no. 3, pp. 432-442, 2010. https://doi.org/10.1016/j.cor.2009.03.004.

[45] US Department of Energy.(2021). Fuel economy guide. Available: www.fueleconomy.gov . [Accessed : Dec 28, 2020]

[46] R. Eberhart and J. Kennedy, "Particle swarm optimization," in Proceedings of the IEEE international conference on neural networks, 1995, vol. 4, pp. 1942-1948: Citeseer.

[47] A. Ratnaweera, S. K. Halgamuge, and H. C. Watson, "Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients," IEEE Transactions on evolutionary computation, vol. 8, no. 3, pp. 240-255, 2004. https://doi.org/10.1109/TEVC.2004.826071

[48] B. Santosa and P. Willy, Metoda Metaheuristik konsep dan implementasi. Surabaya: Guna Widya, 2011.

[49] Y. Shi and R. C. Eberhart, "Parameter selection in particle swarm optimization," in International conference on evolutionary programming, 1998, pp. 591-600: Springer. https://doi.org/10.1007/BFb0040810.

[50] M. Abdel-Basset, G. Manogaran, D. El-Shahat, and S. Mirjalili, "A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem," Future Generation Computer Systems, vol. 85, pp. 129-145, 2018. https://doi.org/10.1016/j.future.2018.03.020.

[51] M. I. Menhas, L. Wang, M. Fei, and H. Pan, "Comparative performance analysis of various binary coded PSO algorithms in multivariable PID controller design," Expert systems with applications, vol. 39, no. 4, pp. 4390-4401, 2012. https://doi.org/10.1016/j.eswa.2011.09.152

[52] S. Venkatesan, D. Logendran, and D. Chandramohan, "Optimization of capacitated vehicle routing problem using PSO," International Journal of Engineering Science and Technology vol. 3, no. 10, pp. 7469-7477, 2011.

StatisticsArticle Metrics

This article has been read : 125 times
PDF file viewed/downloaded : 66 times

This article can be traced from





Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.