(Faculty of Industrial Engineering, Universitas Pembangunan Nasional Veteran Yogyakarta, Indonesia)(2) Raden Achmad Chairdino Leuveano
(Faculty of Industrial Engineering, Universitas Pembangunan Nasional Veteran Yogyakarta, Indonesia)(3) Salwa Hanim Abdul-Rashid
(Faculty of Engineering, Universiti Malaya, Malaysia)(4) Andreas Mahendro Kuncoro
(Faculty of Industrial Engineering, Universitas Pembangunan Nasional Veteran Yogyakarta, Indonesia)(5) Yuli Liestyana
(Faculty of Economics and Business, Universitas Pembangunan Nasional Veteran Yogyakarta, Indonesia)*corresponding author
AbstractThis paper aims to develop an optimized solution for the Vehicle Routing Problem (VRP), tailored explicitly for Liquid Petroleum Gas (LPG) distribution, with a focus on minimizing transportation costs and enhancing delivery reliability. The critical role of LPG as an essential public infrastructure commodity, widely utilized for cooking and heating, makes its efficient and reliable distribution a significant logistical challenge due to the strict adherence to delivery time windows, heterogeneous fleets, multi-trip scenarios, and intricate loading and unloading requirements. To address these complexities, this study proposes a novel hybrid Particle Swarm Optimization and Genetic Algorithm (HPSOGA) that uniquely integrates multi-trip routing, time windows, and heterogeneous vehicle fleet management into a single optimization framework. The dual-phase optimization strategy leverages the exploratory capability of PSO and the solution-refining power of GA, resulting in high-quality, feasible solutions. Validation against real-world data involving VRP instances with 88 and 40 stations demonstrates the model’s practical impact, achieving reductions of up to 4.56% in transportation costs compared to existing operational routes. This research makes a significant contribution to interdisciplinary domains, including logistics optimization, sustainability, and energy distribution, by offering a robust and scalable model that comprehensively addresses complex, real-world VRP constraints.
KeywordsVehicle Routing Problem; HPSOGA Algorithm; Vehicle Allocation; Route optimization; Transport costs
|
DOIhttps://doi.org/10.26555/ijain.v11i3.1837 |
Article metricsAbstract views : 928 | PDF views : 68 |
Cite |
Full Text Download
|
References
[1] H. M. Asih, R. A. C. Leuveano, A. Rahman, and M. Faishal, “Traveling Salesman Problem with Prioritization for Perishable Products in Yogyakarta, Indonesia,” J. Adv. Manuf. Technol., vol. 16, no. 3, pp. 15–27, 2022. [Online]. Available at: https://jamt.utem.edu.my/jamt/article/view/6405.
[2] P. Toth and D. Vigo, “Vehicle Routing,” Soc. Ind. Appl. Math. Math. Optim. Soc., vol. 1, no. 3, pp. 1–459, Nov. 2014, doi: 10.1137/1.9781611973594.
[3] A. Rijal, M. Bijvank, and R. de Koster, “Dynamics between warehouse operations and vehicle routing,” Prod. Oper. Manag., vol. 32, no. 11, pp. 3575–3593, 2023, doi: 10.1111/poms.14051.
[4] S. Tan and W. Yeh, “The Vehicle Routing Problem: State-of-the-Art Classification and Review,” Appl. Sci., vol. 11, no. 21, pp. 1–28, 2021, doi: 10.3390/app112110295.
[5] M. Asghari and S. M. J. Mirzapour Al-e-hashem, “Green vehicle routing problem: A state-of-the-art review,” Int. J. Prod. Econ., vol. 231, p. 107899, 2021, doi: 10.1016/j.ijpe.2020.107899.
[6] S. Elatar, K. Abouelmehdi, and M. E. Riffi, “The vehicle routing problem in the last decade: Variants, taxonomy and metaheuristics,” Procedia Comput. Sci., vol. 220, pp. 398–404, 2023, doi: 10.1016/j.procs.2023.03.051.
[7] K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse, “The vehicle routing problem: State of the art classification and review,” Comput. Ind. Eng., vol. 99, pp. 300–313, 2016, doi: 10.1016/j.cie.2015.12.007.
[8] M. Emadikhiav, D. Bergman, and R. Day, “Consistent Routing and Scheduling with Simultaneous Pickups and Deliveries,” Prod. Oper. Manag., vol. 29, no. 8, pp. 1937–1955, 2020, doi: 10.1111/poms.13200.
[9] O. Jabali, T. Van Woensel, and A. G. De Kok, “Analysis of travel times and CO2 emissions in time-dependent vehicle routing,” Prod. Oper. Manag., vol. 21, no. 6, pp. 1060–1074, 2012, doi: 10.1111/j.1937-5956.2012.01338.x.
[10] R. Elshaer and H. Awad, “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants,” Comput. Ind. Eng., vol. 140, no. December 2019, p. 106242, 2020, doi: 10.1016/j.cie.2019.106242.
[11] F. Nangoy, “Indonesia targets additional liquefied petroleum gas output, regulator says,” Routers, 2024. [Online]. Available at: https://www.reuters.com/business/energy/indonesia-targets-additional-liquefied-petroleum-gas-output-regulator-says-2024-10-29/.
[12] Ministry of Energy and Mineral Resources of the Republic of Indonesia, “Handbook Of Energy & Economic Statistics Of Indonesia 2023,” pp. 1 - 118, Jakarta, 2023. [Online]. Available at: https://esdm.go.id/assets/media/content/content-handbook-of-energy-and-economic-statistics-of-indonesia-2023.pdf.
[13] Institute for Essential Services Reform (IESR), “Indonesia Energy Transition Outlook 2025,” pp. 1 - 114, 2024. [Online]. Available at: https://iesr.or.id/wp-content/uploads/2024/12/Indonesia-Energy-Transition-Outlook-2025-Digital-Version.pdf.
[14] S. Xu, J. Zong, L. Liu, W. Yang, and L. Xu, “An extended PSO algorithm for cold-chain vehicle routing problem with independent loading and minimum fuel volume,” Int. J. Ind. Eng. Comput., vol. 15, pp. 1–12, 2024, doi: 10.5267/j.ijiec.2024.2.001.
[15] Q. Wu et al., “A neighborhood comprehensive learning particle swarm optimization for the vehicle routing problem with time windows,” Swarm Evol. Comput., vol. 84, p. 101425, 2024, doi: 10.1016/j.swevo.2023.101425.
[16] S. F. Ghannadpour and A. Zarrabi, “Multi-objective heterogeneous vehicle routing and scheduling problem with energy minimizing,” Swarm Evol. Comput., vol. 44, pp. 728–747, 2019, doi: 10.1016/j.swevo.2018.08.012.
[17] V. S. Nguyen, Q. D. Pham, T. H. Nguyen, and Q. T. Bui, “Modeling and solving a multi-trip multi-distribution center vehicle routing problem with lower-bound capacity constraints,” Comput. Ind. Eng., vol. 172, p. 108597, 2022, doi: 10.1016/j.cie.2022.108597.
[18] X. Wei, Z. Xiao, and Y. Wang, “Solving the Vehicle Routing Problem with Time Windows Using Modified Rat Swarm Optimization Algorithm Based on Large Neighborhood Search,” Mathematics, vol. 12, no. 1702, pp. 1–33, 2024, doi: 10.3390/math12111702.
[19] B. H. Ojeda Rios and E. C. Xavier, “Metaheuristic approaches for the stochastic capacitated multi-depot vehicle routing problem with pickup and delivery,” Expert Syst. Appl., vol. 290, no. November 2024, p. 128258, 2025, doi: 10.1016/j.eswa.2025.128258.
[20] Y. J. Pak and K. H. Mun, “A practical vehicle routing problem in small and medium cities for fuel consumption minimization,” Clean. Logist. Supply Chain, vol. 12, no. April, p. 100164, 2024, doi: 10.1016/j.clscn.2024.100164.
[21] H. Mukti, R. Achmad, C. Leuveano, and D. Arief, “Genetic algorithm to optimize green vehicle routing and allocation planning for perishable products,” Int. J. Adv. Intell. Informatics, vol. 11, no. 2, pp. 175–191, 2025, doi: 10.26555/ijain.v11i2.1784.
[22] J. Zhang and Y. Li, “Vehicle routing problem for cold-chain drug distribution with epidemic spread situation,” Expert Syst. Appl., vol. 262, no. April 2024, p. 125186, 2024, doi: 10.1016/j.eswa.2024.125186.
[23] C. Blum and A. Roli, “Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison,” ACM Comput. Surv., vol. 35, no. 3, pp. 268–308, 2003, doi: 10.1145/937503.937505.
[24] C. Blum, J. Puchinger, G. R. Raidl, and A. Roli, “Hybrid metaheuristics in combinatorial optimization: A survey,” Appl. Soft Comput. J., vol. 11, no. 6, pp. 4135–4151, 2011, doi: 10.1016/j.asoc.2011.02.032.
[25] T. M. Shami, A. A. El-Saleh, M. Alswaitti, Q. Al-Tashi, M. A. Summakieh, and S. Mirjalili, “Particle Swarm Optimization: A Comprehensive Survey,” IEEE Access, vol. 10, pp. 10031–10061, 2022, doi: 10.1109/ACCESS.2022.3142859.
[26] H. M. Pandey, A. Chaudhary, and D. Mehrotra, “A comparative review of approaches to prevent premature convergence in GA,” Appl. Soft Comput. J., vol. 24, pp. 1047–1077, 2014, doi: 10.1016/j.asoc.2014.08.025.
[27] R. A. C. Leuveano, H. M. Asih, M. I. Ridho, and D. A. Darmawan, “Balancing Inventory Management : Genetic Algorithm Optimization for A Novel Dynamic Lot Sizing Model in Perishable Product Manufacturing,” J. Robot. Control, vol. 4, no. 6, pp. 878–895, 2023, doi: 10.18196/jrc.v4i6.20667.
[28] H. M. Asih, R. A. C. Leuveano, and D. A. Dharmawan, “Optimizing lot sizing model for perishable bread products using genetic algorithm,” J. Sist. dan Manaj. Ind., vol. 7, no. 2, pp. 139–154, 2023, doi: 10.30656/jsmi.v7i2.7172.
[29] N. Indrianti, R. A. C. Leuveano, S. H. Abdul-Rashid, and M. I. Ridho, “Green Vehicle Routing Problem Optimization for LPG Distribution: Genetic Algorithms for Complex Constraints and Emission Reduction,” Sustainability, vol. 17, no. 3, pp. 1–25, 2025, doi: 10.3390/su17031144.
[30] P. Victer Paul, A. Ramalingam, R. Baskaran, P. Dhavachelvan, K. Vivekanandan, and R. Subramanian, “A new population seeding technique for permutation-coded Genetic Algorithm: Service transfer approach,” J. Comput. Sci., vol. 5, no. 2, pp. 277–297, 2014, doi: 10.1016/j.jocs.2013.05.009.
[31] M. N. Haddad et al., “Large neighborhood-based metaheuristic and branch-and-price for the pickup and delivery problem with split loads,” Eur. J. Oper. Res., vol. 270, no. 3, pp. 1014–1027, 2018, doi: 10.1016/j.ejor.2018.04.017.
[32] S. Zhou, D. Zhang, B. Ji, S. Zhou, S. Li, and L. Zhou, “A MILP model and heuristic method for the time-dependent electric vehicle routing and scheduling problem with time windows,” J. Clean. Prod., vol. 434, p. 140188, 2024, doi: 10.1016/j.jclepro.2023.140188.
[33] W. Liu, J. Qiu, J. Deng, N. Zheng, X. Chang, and Y. Liu, “Variable neighbourhood search embedded perturbation mechanism for multi-depot vehicle routing problem with simultaneous delivery & pickup, and time limit,” Comput. Ind. Eng., vol. 189, p. 109942, 2024, doi: 10.1016/j.cie.2024.109942.
[34] S. Salhi and G. Nagy, “A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling,” J. Oper. Res. Soc., vol. 50, no. 10, pp. 1034–1042, 1999, doi: 10.1057/palgrave.jors.2600808.
[35] L. Wang, J. Kinable, and T. van Woensel, “The fuel replenishment problem: A split-delivery multi-compartment vehicle routing problem with multiple trips,” Comput. Oper. Res., vol. 118, p. 104904, 2020, doi: 10.1016/j.cor.2020.104904.
[36] A. K. Agrawal, S. Yadav, A. A. Gupta, and S. Pandey, “A genetic algorithm model for optimizing vehicle routing problems with perishable products under time-window and quality requirements,” Decis. Anal. J., vol. 5, no. September, p. 100139, 2022, doi: 10.1016/j.dajour.2022.100139.
[37] L. Qiang and X. Jiuping, “A Study on Vehicle Routing Problem in the Delivery of Fresh Agricultural Products under Random Fuzzy Environment,” Int. J. Inf. Manag. Sci., vol. 4, no. 19, pp. 673–690, 2008. [Online]. Available at: https://pascal-francis.inist.fr/vibad/.
[38] F. Menares, E. Montero, G. Paredes-Belmar, and A. Bronfman, “A bi-objective time-dependent vehicle routing problem with delivery failure probabilities,” Comput. Ind. Eng., vol. 185, p. 109601, 2023, doi: 10.1016/j.cie.2023.109601.
[39] Z. H. Ahmed and M. Yousefikhoshbakht, “An improved tabu search algorithm for solving heterogeneous fixed fleet open vehicle routing problem with time windows,” Alexandria Eng. J., vol. 64, pp. 349–363, 2023, doi: 10.1016/j.aej.2022.09.008.
[40] J. Lehmann and M. Winkenbach, “A matheuristic for the Two-Echelon Multi-Trip Vehicle Routing Problem with mixed pickup and delivery demand and time windows,” Transp. Res. Part C Emerg. Technol., vol. 160, p. 104522, 2024, doi: 10.1016/j.trc.2024.104522.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571 (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
andri.pranolo.id@ieee.org (publication issues)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0