Large neighborhood search for route and fleet optimization in frozen food distribution

Authors

  • Jonathan Andrepa Simbolon Industrial Engineering Department, Universitas Pembangunan Nasional Veteran Yogyakarta, Daerah Istimewa Yogyakarta, Indonesia
  • Trismi Ristyowati Industrial Engineering Department, Universitas Pembangunan Nasional Veteran Yogyakarta, Daerah Istimewa Yogyakarta, Indonesia
  • Apriani Soepardi Industrial Engineering Department, Universitas Pembangunan Nasional Veteran Yogyakarta, Daerah Istimewa Yogyakarta, Indonesia
  • Irwan Soejanto Industrial Engineering Department, Universitas Pembangunan Nasional Veteran Yogyakarta, Daerah Istimewa Yogyakarta, Indonesia
  • Yuli dwi Astanti Industrial Engineering Department, Universitas Pembangunan Nasional Veteran Yogyakarta, Daerah Istimewa Yogyakarta, Indonesia
  • Puryani Industrial Engineering Department, Universitas Pembangunan Nasional Veteran Yogyakarta, Daerah Istimewa Yogyakarta, Indonesia
  • Mochammad Chaeron Industrial Engineering Department, Universitas Pembangunan Nasional Veteran Yogyakarta, Daerah Istimewa Yogyakarta, Indonesia

DOI:

https://doi.org/10.31315/opsi.v18i2.15743

Keywords:

Vehicle routing problem , Time windows , Frozen foods , Large neighbourhood search algorithm, Priority customers

Abstract

This study develops an optimization model to enhance the distribution efficiency of a frozen food distributor. The company faces operational inefficiencies due to excessive fleet capacity and conventional route assignment methods, which increase travel distances and overall distribution costs. To address these challenges, an extended Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) model is proposed, which integrates heterogeneous fleet characteristics and prioritizes customer service constraints. The model is solved using the Large Neighborhood Search (LNS) metaheuristic to determine optimal routing and fleet allocation strategies. The optimized model achieves a 15.95% reduction in total travel distance and a 21.84% decrease in total distribution costs compared with the company’s current operations. The findings confirm the effectiveness of the LNS-based CVRPTW approach in improving logistics performance and provide practical insights for companies seeking to minimize distribution costs through strategic route planning and fleet management.

References

[1] V. M. Momanyi and M. Moronge, “Determinants of distribution management in manufacturing institutions in Nairobi County, Kenya,” Strategic Journal of Business & Change Management, vol. 4, no. 2, pp. 1–15, 2017. [Online]. Available: http://strategicjournals.com/index.php/journal/article/view/420/450.

[2] B. Celestino, I. V. Benavides-Peña, V. Garza-Amaya, and C. Garza-Madero, “Improving distribution efficiency to increase agility: An application to a Mexican company,” in Proc. 7th Int. Conf. Ind. Eng. Oper. Manag. (IEOM), 2017. [Online]. Available: https://index.ieomsociety.org/index.cfm/item/49581.

[3] A. Nawaz, M. R. R. Rana, and G. Mustafa, “An optimized solution to multi-constraint vehicle routing problem,” Innovative Computing Review, vol. 2, no. 2, Dec. 2022, https://doi.org/10.32350/icr.0202.04.

[4] R. Belka and M. Godlewski, “Vehicle routing optimization system with smart geopositioning updates,” Applied Sciences, vol. 11, no. 22, p. 10933, Nov. 2021, https://doi.org/10.3390/app112210933.

[5] K. Ait Mamoun, L. Hammadi, A. G. N. Novaes, A. El Ballouti, and E. S. de Cursi, “An optimisation solution of capacitated vehicle routing problem (CVRP),” in Proc. Int. Symp. Signal, Image, Video Commun. (ISIVC), 2022, pp. 1–5, 10.1109/ISIVC54825.2022.9800726.

[6] R. Moghdani, K. Salimifard, E. Demir, and A. Benyettou, “The green vehicle routing problem: A systematic literature review,” Journal of Cleaner Production, vol. 279, p. 123691, 2021, https://doi.org/10.1016/j.jclepro.2020.123691.

[7] L. Mora, X. Wu, and A. Panori, “Mind the gap: Developments in autonomous driving research and the sustainability challenge,” Journal of Cleaner Production, vol. 275, p. 124087, 2020, https://doi.org/10.1016/j.jclepro.2020.124087.

[8] A. Shahedi, I. Dadashpour, and M. Rezaei, “Barriers to the sustainable adoption of autonomous vehicles in developing countries: A multi-criteria decision-making approach,” Heliyon, vol. 9, no. 5, p. e15975, 2023, https://doi.org/10.1016/j.heliyon.2023.e15975.

[9] B. Sarasola and K. F. Doerner, “Adaptive large neighborhood search for the vehicle routing problem with synchronization constraints at the delivery location,” Networks, vol. 75, no. 1, pp. 64–85, 2020, https://doi.org/10.1002/net.21905.

[10] I. Mushtaq, M. Umer, M. A. Khan, and S. Kadry, “Customer prioritization integrated supply chain optimization model with outsourcing strategies,” Big Data, Apr. 2022, https://doi.org/10.1089/big.2021.02.

[11] L. Marla, J. Shin, and S. Deshpande, “Strategic service logistics games with customer-induced competition,” SSRN Electronic Journal, Feb. 2021, http://dx.doi.org/10.2139/ssrn.3205999.

[12] S. Mancini, “The hybrid vehicle routing problem,” Transportation Research Part C: Emerging Technologies, vol. 78, pp. 1–12, May 2017, https://doi.org/10.1016/j.trc.2017.02.004.

[13] L. Zheng, Z. He, and W. Liang, “VRP problem solving based on adaptive dynamic search ant colony algorithm,” Journal of Physics: Conference Series, vol. 1487, no. 1, p. 012030, Mar. 2020, https://iopscience.iop.org/article/10.1088/1742-6596/1487/1/012030/pdf.

[14] J. Kim and K.-H. Kim, “Optimizing large-scale fleet management on a road network using multi-agent deep reinforcement learning with graph neural network,” in Proc. IEEE Int. Conf. Intelligent Transportation Systems (ITSC), 2021, pp. 990–995, https://arxiv.org/pdf/2011.06175.

[15] S. Samsuddin, M. S. Othman, and L. M. Yusuf, “A review of single and population-based metaheuristic algorithms solving multi depot vehicle routing problem,” International Journal of Software Engineering and Computer Systems, vol. 4, no. 2, pp. 80–93, Aug. 2018, https://doi.org/10.15282/ijsecs.4.2.2018.6.0050.

[16] M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research, vol. 35, no. 2, pp. 254–265, 1987, https://doi.org/10.1287/opre.35.2.254

[17] 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.

[18] C. R. Gatica, S. M. Molina, and G. Leguizamón, “VNS variant approach metaheuristics for parallel machines scheduling problem,” in Computer Science – CACIC 2022, P. Pesado, Ed., Communications in Computer and Information Science, vol. 1778. Cham, Switzerland: Springer, 2023, pp. 3–18, https://doi.org/10.1007/978-3-031-34147-2_1.

[19] F. Kocatürk, G. Tütüncü, and S. Salhi, “The multi-depot heterogeneous VRP with backhauls: Formulation and a hybrid VNS with GRAMPS meta-heuristic approach,” Annals of Operations Research, vol. 307, pp. 277–302, Jun. 2021, doi: 10.1007/s10479-021-04137-6.

[20] Ç. Koç, T. Bektaş, O. Jabali, and G. Laporte, “The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm,” European Journal of Operational Research, vol. 248, no. 1, pp. 33–51, 2016, https://eprints.soton.ac.uk/378590/1/Paper3_EJORRevision.pdf.

[21] D. Jiang, Z. Tian, Z. He, G. Tu, and R. Huang, “A framework for designing genetic operators automatically based on gene expression programming and differential evolution,” Natural Computing, vol. 20, no. 3, pp. 395–411, Jan. 2021, https://doi.org/10.1007/s11047-020-09830-2 .

[22] Y. Trakulsunti, J. Antony, R. Jayaraman, and G. L. Tortorella, “The application of operational excellence methodologies in logistics: A systematic review and directions for future research,” Total Quality Management & Business Excellence, vol. 34, no. 5–6, pp. 538–557, May 2022, https://doi.org/10.1080/14783363.2022.2071695.

[23] R. K. Goel and S. R. Bansal, “Hybrid algorithms for rich vehicle routing problems: A survey,” in Smart Delivery Systems: Solving Complex Vehicle Routing Problems, J. Nalepa, Ed. Elsevier, 2020, pp. 157–184, https://doi.org/10.1016/B978-0-12-815715-2.00011-7.

[24] W. P. Adi and L. Kusniawati, “Optimasi rute pengiriman bahan baku CKD part dengan pendekatan capacitated vehicle routing problem (CVRP) di PT XYZ,” Industrial Engineering Online Journal, vol. 12, no. 4, pp. 1–14, 2023, https://ejournal3.undip.ac.id/index.php/ieoj/article/view/40931/29736.

[25] A. N. Fadjriani, M. Sofitra, and D. Wijayanto, “Perencanaan rute dan jadwal distribusi periodik multiproduk menggunakan metode large neighborhood search,” INTEGRATE: Industrial Engineering and Management System, vol. 7, no. 1, pp. 211–220, 2023, https://jurnal.untan.ac.id/index.php/jtinUNTAN/article/view/66967/75676597795.

[26] G. Erdogan, “An open source spreadsheet solver for vehicle routing problems,” Computers & Operations Research, vol. 84, pp. 62–72, 2017, https://doi.org/10.1016/j.cor.2017.02.022.

Downloads

Published

2025-12-30

Issue

Vol. 18 No. 2 (2025): OPSI - December 2025

Section

Article

License

Authors who publish articles in this journal agree to the following conditions:

  1. Copyright remains with the author and gives the Opsi journal the right as a priority to publish its articles with Creative Commons Attribution 4.0 International license. Which allows articles to be shared with acknowledgement of the author of the article and this journal as the place of publication.
  2. Authors can distribute their articles on a non-exclusive basis (e.g. in university repositories or books) with notification or acknowledgement of publication in Opsi journals.
  3. Authors are allowed to post their work online (e.g. on a personal website or in a university repository) before and after the submission process (see The Effect of Open Access)
 

Lisensi Creative Commons

This work is Licensed Under a Creative Commons Attribution 4.0 International license.

Most read articles by the same author(s)