Optimizing Container Repositioning Using a Sequential Insertion Algorithm for Pickup-Delivery Routing in Export-Import Operations

Ary Arvianto; Dihan Chofifah Cahyani; Dhimas Wachid Nur Saputra

doi:10.12928/si.v23i1.349

Authors

Ary Arvianto Industrial Engineering Department, Diponegoro University, Semarang, 50275, Indonesia https://orcid.org/0000-0001-8717-4959
Dihan Chofifah Cahyani Industrial Engineering Department, Diponegoro University, Semarang, 50275, Indonesia
Dhimas Wachid Nur Saputra Industrial Engineering Department, Diponegoro University, Semarang, 50275, Indonesia https://orcid.org/0009-0006-9439-7214

DOI:

https://doi.org/10.12928/si.v23i1.349

Keywords:

Supply chain, Distribution, Sequential insertion, Vehicle routing problem, Container repositioning

Abstract

The increasing number of empty containers significantly causes to traffic congestion and rising operational costs, thereby necessitating the development of an optimized routing model to enhance fleet utilization and minimize transportation expenses. This study focuses on optimizing container repositioning for pick-up and delivery operations using a heuristic approach derived from the Vehicle Routing Problem with Pick-Up and Delivery and Time Windows (VRPPD-TW). The proposed model employs a sequential insertion algorithm grounded in a mathematical framework and implemented in Python. Its accuracy is validated through manual calculations that correspond with the algorithmic steps. The objective is to minimize vehicle usage within the defined time constraints. This empirical study involves six nodes: a garage, two depots, two external container depots, and a port terminal, which handle the daily relocation of 44 containers for export-import activities. The model successfully reduces the number of trips from 37 to 6, demonstrating substantial optimization. The results show that the sequential insertion algorithm effectively solves the VRPPD-TW by enhancing solution space exploration, balancing workloads, and adapting to dynamic constraints. Managerial implications include a 75% reduction in fleet requirements and increased logistical efficiency. This research contributes a practical approach with the potential to lower operational costs and mitigate congestion by improving fleet utilization. However, the model has notable limitations, such as the exclusion of dynamic truck queuing times at each node and unresolved issues related to computational scalability.

References

Alfandari, L., Davidovic, T., Furini, F., Ljubic, I., Maras, V., & Martin, S. (2019). Tighter MIP models for Barge Container Ship Routing. Omega, 82, 38–54. https://doi.org/10.1016/j.omega.2017.12.002

Armbrust, P., Maier, K., & Truden, C. (2022). Sweep Algorithms for the Vehicle Routing Problem with Time Windows (pp. 135–144). https://doi.org/10.1007/978-3-031-22039-5_11

Arvianto, A., Perkasa, D. S., Budiawan, W., Laksosno, P. W., & Saptadi, S. (2015). Vehicle routing problem modelling to minimize a number of Vehicle by considering heterogenous fleet vehicle. Proceedings of the Joint International Conference on Electric Vehicular Technology and Industrial, Mechanical, Electrical and Chemical Engineering (ICEVT & IMECE), 380–388. https://doi.org/10.1109/ICEVTIMECE.2015.7496701

Bawono, A. T., Rumambi, F. J., & Rante, J. Z. (2019). Pengaruh Integrasi Logistik dan Kinerja Rantai Pasok Terhadap Kecepatan Distribusi Barang dan Dampaknya Pada Pertumbuhan Perusahaan PT. Yicheng Logistics. Jurnal Manajemen Dan Bisnis, 5(2), 15–24. https://repository.ibmasmi.ac.id/assets/files/content/f_0434_20220826100359.pdf

Deng, A., Mao, C., & Zhou, Y. (2009). Optimizing Research of an Improved Simulated Annealing Algorithm to Soft Time Windows Vehicle Routing Problem with Pick-up and Delivery. Systems Engineering - Theory & Practice, 29(5), 186–192. https://doi.org/10.1016/S1874-8651(10)60049-X

Desrosiers, J., Dumas, Y., & Soumis, F. (1986). A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time Windows. American Journal of Mathematical and Management Sciences, 6(3–4), 301–325. https://doi.org/10.1080/01966324.1986.10737198

Euchi, J., & Sadok, A. (2021). Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones. Physical Communication, 44, 101236. https://doi.org/10.1016/j.phycom.2020.101236

Fazi, S., Fransoo, J. C., Van Woensel, T., & Dong, J.-X. (2020). A variant of the split vehicle routing problem with simultaneous deliveries and pickups for inland container shipping in dry-port based systems. Transportation Research Part E: Logistics and Transportation Review, 142, 102057. https://doi.org/10.1016/j.tre.2020.102057

Febriyanti, D. E., Primadasa, R., & Bhakti Sutono, S. (2022). Determination of Distribution Routes Using the Saving Matrix Method to Minimize Shipping Costs at Pt. Sukun Transport Logistics. Spektrum Industri, 20(1), 79–90. https://doi.org/10.12928/si.v20i1.18

Hasibuan, A., Banjarnahor, A. R., Sahir, S. H., Cahya, H. N., Nur, N. K., Purba, B., SN, A., Prasetio, A., Ardiana, D. P. Y., Purba, S., & Mardia. (2021). Manajemen Logistik dan Supply Chain Management (1st ed.).

Joubert, J., & Claasen, S. (2006). A sequential insertion heuristic for the initial solution to a constrained vehicle routing problem. ORiON, 22(1). https://doi.org/10.5784/22-1-36

Kurniawan, I. S., Susanty, S., & Adianto, H. (2014). Usulan Rute Pendistribusian Air Mineral Dalam Kemasan Menggunakan Metode Nearest Neighbour dan Clarke & Wright Savings (Studi Kasus di PT. X Bandung). Reka Integra, Jurnal Online Institut Teknologi Nasional, 1(4), 125–136. https://www.academia.edu/118943447/Usulan_Rute_Pendistribusian_Air_Mineral_Dalam_Kemasan_Menggunakan_Metode_Nearest_Neighbour_dan_Clarke_and_Wright_Savings_Studi_Kasus_di_PT_X_Bandung_

Kusumastuti, D., & Sugiama, A. G. (2017). Manajemen Logistik Organisasi Publik (2nd Ed.) (2nd ed.). Universitas Terbuka.

Lai, M., Paola, A., Co-Advisor, Z., & Battarra, M. (2013). Models and algorithms for the empty container repositioning and its integration with routing problems. https://iris.unica.it/retrieve/e2f56ed8-3aef-3eaf-e053-3a05fe0a5d97/Lai_PhD_Thesis.pdf

Lau, H. C., & Liang, Z. (2002). Pickup and Delivery with Time Windows: Algorithms and Test Case Generation. International Journal on Artificial Intelligence Tools, 11(03), 455–472. https://doi.org/10.1142/S0218213002000988

Meng, L., Ge, H., Wang, X., Yan, W., & Han, C. (2023). Optimization of ship routing and allocation in a container transport network considering port congestion: A variational inequality model. Ocean & Coastal Management, 244, 106798. https://doi.org/10.1016/j.ocecoaman.2023.106798

Nono, V., Sofitra, M., & Wijayanto, D. (2020). Penyelesaian Capacitated Vehicle Routing Problem Dengan Menggunakan Algoritma Sweep Untuk Penentuan Rute Distribusi Untuk Depo Pt. Abc Kubu Raya. Jurnal Teknik Industri Universitas Tanjungpura, 4(2), 232–238. https://industri.teknik.untan.ac.id/jurnal

Prasetyo, W., & Tamyiz, M. (2017). Vehicle Routing Problem Dengan Aplikasi Metode Nearest Neighbor. Journal of Research and Technology, 3(2). https://doi.org/10.55732/jrt.v3i2.263

Saragih, N. I., & Turnip, P. (2024). Tabu Search Algorithm for Solving a Location-Routing-Inventory Problem. Spektrum Industri, 22(2), 155–162. https://doi.org/10.12928/si.v22i2.234

Sitek, P., Wikarek, J., Rutczynska-Wdowiak, K., Bocewicz, G., & Banaszak, Z. (2021). Optimization of capacitated vehicle routing problem with alternative delivery, pick-up and time windows: A modified hybrid approach. Neurocomputing, 423, 670–678. https://doi.org/10.1016/j.neucom.2020.02.126

Suryani, S., Kuncoro, K. R., & Fathimahhayati, L. D. (2018). Perbandingan Penerapan Metode Nearest Neighbour Dan Insertion Untuk Penentuan Rute Distribusi Optimal Produk Roti Pada Ukm Hasan Bakery Samarinda. PROFISIENSI: The Journal of the Industrial Engineering Study Program, 6(1), 41–49. https://www.journal.unrika.ac.id/index.php/jurnalprofisiensi/article/view/1456

Toth, P., & Vigo, D. (2015). Vehicle Routing: Problems, Methods, and Applications, Second Edition (2nd ed.). Society for Industrial and Applied Mathematics (SIAM).

Vidovic, M., Radivojevic, G., & Rakovic, B. (2011). Vehicle routing in containers pickup up and delivery processes. Procedia - Social and Behavioral Sciences, 20, 335–343. https://doi.org/10.1016/j.sbspro.2011.08.039

Wang, S. (2014). A novel hybrid-link-based container routing model. Transportation Research Part E: Logistics and Transportation Review, 61, 165–175. https://doi.org/10.1016/j.tre.2013.11.006

Widyawati, N., Merciana, D., & Kalangi, M. H. E. (2020). Moda Transportasi Darat Dan Kualitas Layanan Jasa Terhadap Kelancaran Arus Container Di Depo. Jurnal Baruna Horizon, 3(2), 230–241. https://doi.org/10.52310/jbhorizon.v3i2.43

Wulandari, C. B. K. (2020). Penentuan Rute Distribusi Menggunakan Metode Nearest Neighbors dan Metode Branch and Bound Untuk Meminimumkan Biaya Distribusi di PT. X. Jurnal Optimasi Teknik Industri (JOTI), 2(1), 7. https://doi.org/10.30998/joti.v2i1.3848

Zhang, R., Huang, C., & Wang, J. (2020). A novel mathematical model and a large neighborhood search algorithm for container drayage operations with multi-resource constraints. Computers & Industrial Engineering, 139, 106143. https://doi.org/10.1016/j.cie.2019.106143