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

Baiq Nurul Izzah Farida Ramadhani; Annisa Kesy Garside

doi:10.25077/josi.v20.n1.p1-10.2021

Baiq Nurul Izzah Farida Ramadhani

Universitas Muhammadiyah Malang

Annisa Kesy Garside

Universitas Muhammadiyah Malang

Keywords

Vehicle routing problem, loading weight, traveling time, fuel consumption, Particle Swarm Optimization

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.

Downloads

Download data is not yet available.

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.

PDF

Published

May 18, 2021

https://doi.org/10.25077/josi.v20.n1.p1-10.2021

How to Cite

[1]

B. N. I. F. Ramadhani and A. K. Garside, “Particle Swarm Optimization Algorithm to Solve Vehicle Routing Problem with Fuel Consumption Minimization”, J. Optimasi Sist. Ind., vol. 20, no. 1, pp. 1–10, May 2021.

Issue

Vol. 20 No. 1 (2021): Published in May 2021

Section

Articles

Authors' Retention of Copyright

Authors retain the copyright of their original work published in Jurnal Optimasi Sistem Industri (JOSI). By submitting their manuscript to the journal, authors grant Jurnal Optimasi Sistem Industri (JOSI) a non-exclusive license to publish the work under the CC BY-NC-SA 4.0 International License. This means that others are permitted to:

Share and adapt the work for non-commercial purposes, provided proper attribution is given to the original authors and source.
Create derivative works based on the original article, as long as the new work is non-commercial and under the same CC BY-NC-SA 4.0 International License.

Non-Commercial Usage

The CC BY-NC-SA 4.0 International License restricts commercial use of the published work and its derivatives. Commercial use includes generating revenue, financial gain, or any form of commercial exploitation. This limitation aims to preserve the scholarly and educational nature of the content.

ShareAlike Requirement

If you remix, adapt, or build upon the work, you must distribute your contributions under the same CC BY-NC-SA 4.0 International License as the original work. This "ShareAlike" requirement ensures that any new works based on the original content adhere to the same non-commercial, share-alike principles.

Usage, Attribution, and Citations

Authors and readers are allowed to:

Share and distribute the published article in any medium or format.
Adapt, remix, transform, and build upon the article for non-commercial purposes.
Provide appropriate attribution to the original authors and the journal.

When using content from Jurnal Optimasi Sistem Industri (JOSI), proper attribution must be provided through citation of the original source and authors.

Copyright Infringement and Ethical Considerations

If you believe that any material published in Jurnal Optimasi Sistem Industri (JOSI) infringes upon your copyright or the copyright of someone you represent, please contact the editorial team promptly. The journal is committed to addressing copyright concerns in accordance with established ethical guidelines set forth by the Committee on Publication Ethics (COPE).

For any questions or inquiries related to copyright and licensing, please contact the editorial team at editor_josi[at]eng.unand.ac.id.