Soft Time-Window Constraints in Crystal-Ice Distribution: A Cheapest-Insertion VRPTW Case Study with Non-Refrigerated Vehicles
DOI:
https://doi.org/10.61194/sijl.v4i3.1106Keywords:
crystal ice distribution, perishable product, vehicle routing problem with time windows, cheapest insertion heuristic, soft time window, lateness penaltyAbstract
Perishable product distribution requires efficient route planning because delivery duration, route sequence, and transportation conditions directly affect product quality, service reliability, and operational performance. This study evaluates hard and penalty-based soft time-window routing for crystal-ice distribution in a small-scale enterprise distribution system comprising one depot, 60 scheduled customers, and two non-refrigerated vehicles. A quantitative computational case-study approach was applied using the Vehicle Routing Problem with Time Windows (VRPTW) and the Cheapest Insertion Heuristic (CIH). Soft time-window performance was evaluated using lateness penalties of λ = 0.1, 0.5, 1, 2, and 5 km/min. The hard time-window solution produced a fleet distance of 86.87 km and zero lateness. At λ = 0.1, the soft model reduced the fleet distance to 85.29 km but generated 8.95 minutes of total lateness across two customers. Increasing the penalty to λ = 0.5 eliminated all lateness and produced the same 86.87-km route as the hard model. Compared with the observed company baseline, the selected zero-lateness route reduced fleet distance from 99.84 to 86.87 km (12.99%) and route exposure duration from approximately 1,200 to 1,043.59 minutes (13.03%). Model-estimated product loss decreased from an observed baseline of 580 kg to 507.95 kg, corresponding to an estimated reduction of 72.05 kg (12.42%). These findings show that soft time-window penalties can reveal the trade-off between marginal distance savings and service punctuality.
References
Agrawal, A. K., Yadav, S., Gupta, A. A., & Pandey, S. (2022). A genetic algorithm model for optimizing vehicle routing problems with perishable products under time-window and quality requirements. Decision Analytics Journal, 5, 100139. https://doi.org/10.1016/j.dajour.2022.100139 DOI: https://doi.org/10.1016/j.dajour.2022.100139
Andrianto, D. T., Zulkarnain, A., & Yuliantini. (2025). Transportation Resilience under Climate Change: Infrastructure, Policy, Technology, and Social Dimensions. Logistica : Journal of Logistic and Transportation, 3(1), 1–13. https://doi.org/10.61978/LOGISTICA.V3I1.1067 DOI: https://doi.org/10.61978/logistica.v3i1.1067
Babaee Tirkolaee, E., Goli, A., Bakhsi, M., & Mahdavi, I. (2017). A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control & Optimization, 7(4), 417–433. https://doi.org/10.3934/naco.2017026 DOI: https://doi.org/10.3934/naco.2017026
Bomboi, F., Buchheim, C., & Pruente, J. (2022). On the stochastic vehicle routing problem with time windows, correlated travel times, and time dependency. 4OR, 20(2), 217–239. https://doi.org/10.1007/s10288-021-00476-z DOI: https://doi.org/10.1007/s10288-021-00476-z
Chen, Y., Lan, H., Wang, C., & Jia, X. (2023). An integrated distribution scheduling and route planning of food cold chain with demand surge. Complex & Intelligent Systems, 9(1), 475–491. https://doi.org/10.1007/s40747-022-00811-9 DOI: https://doi.org/10.1007/s40747-022-00811-9
Chen, Y.-Y., Chen, T.-L., Chiu, C.-C., & Wu, Y.-J. (2023). A multi-trip vehicle routing problem considering time windows and limited duration under a heterogeneous fleet and parking constraints in cold supply chain logistics. Transportation Planning and Technology, 46(3), 335–358. https://doi.org/10.1080/03081060.2023.2188215 DOI: https://doi.org/10.1080/03081060.2023.2188215
Deng, F., Qin, H., Li, J., & Cheng, C. (2023). The Pickup and Delivery Problem with Time Windows and Incompatibility Constraints in Cold Chain Transportation. Transportation Science, 57(2), 444–462. https://doi.org/10.1287/trsc.2022.1167 DOI: https://doi.org/10.1287/trsc.2022.1167
Dewi, N. K. (2026). Integrated Hub-and-Spoke Network Optimization for Inter-Island Freight Distribution in Eastern Indonesia: A Mixed-Method Logistics Framework. Logistica : Journal of Logistic and Transportation, 4(1), 1–21. https://doi.org/10.61978/LOGISTICA.V4I1.1735 DOI: https://doi.org/10.61978/logistica.v4i1.1735
Estrada‐Moreno, A., Fikar, C., Juan, A. A., & Hirsch, P. (2019). A biased‐randomized algorithm for redistribution of perishable food inventories in supermarket chains. International Transactions in Operational Research, 26(6), 2077–2095. https://doi.org/10.1111/itor.12668 DOI: https://doi.org/10.1111/itor.12668
Figliozzi, M. A. (2010). An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows. Transportation Research Part C: Emerging Technologies, 18(5), 668–679. https://doi.org/10.1016/j.trc.2009.08.005 DOI: https://doi.org/10.1016/j.trc.2009.08.005
Giuffrida, N., Fajardo-Calderin, J., Masegosa, A. D., Werner, F., Steudter, M., & Pilla, F. (2022). Optimization and Machine Learning Applied to Last-Mile Logistics: A Review. Sustainability, 14(9), 5329. https://doi.org/10.3390/su14095329 DOI: https://doi.org/10.3390/su14095329
He, M., Yang, M., Fu, W., Wu, X., & Izui, K. (2024). Optimization of Electric Vehicle Routes Considering Multi-Temperature Co-Distribution in Cold Chain Logistics with Soft Time Windows. World Electric Vehicle Journal, 15(3), 80. https://doi.org/10.3390/wevj15030080 DOI: https://doi.org/10.3390/wevj15030080
Hsu, C.-I., Hung, S.-F., & Li, H.-C. (2007). Vehicle routing problem with time-windows for perishable food delivery. Journal of Food Engineering, 80(2), 465–475. https://doi.org/10.1016/j.jfoodeng.2006.05.029 DOI: https://doi.org/10.1016/j.jfoodeng.2006.05.029
Lespay, H., & Suchan, K. (2021). A case study of consistent vehicle routing problem with time windows. International Transactions in Operational Research, 28(3), 1135–1163. https://doi.org/10.1111/itor.12885 DOI: https://doi.org/10.1111/itor.12885
Liang, X., Chen, H., Wang, N., & Zhang, M. (2024). Bi-Objective Vehicle Routing for Perishable Products Delivery With Consideration of Customers’ Priorities and Customized Delivery Time Windows. IEEE Transactions on Intelligent Transportation Systems, 25(11), 16881–16896. https://doi.org/10.1109/TITS.2024.3421949 DOI: https://doi.org/10.1109/TITS.2024.3421949
Liang, Y., Liu, F., Lim, A., & Zhang, D. (2020). An integrated route, temperature and humidity planning problem for the distribution of perishable products. Computers & Industrial Engineering, 147, 106623. https://doi.org/10.1016/j.cie.2020.106623 DOI: https://doi.org/10.1016/j.cie.2020.106623
Liu, X., Chen, Y.-L., Por, L. Y., & Ku, C. S. (2023). A Systematic Literature Review of Vehicle Routing Problems with Time Windows. Sustainability, 15(15), 12004. https://doi.org/10.3390/su151512004 DOI: https://doi.org/10.3390/su151512004
Liu, Y., Tao, F., & Zhu, R. (2025). Vehicle-routing problem for low-carbon cold chain logistics based on the idea of cost–benefit. Complex & Intelligent Systems, 11(2), 157. https://doi.org/10.1007/s40747-024-01756-x DOI: https://doi.org/10.1007/s40747-024-01756-x
Liu, Z., Zuo, X., Zhou, M., Guan, W., & Al-Turki, Y. (2023). Electric Vehicle Routing Problem With Variable Vehicle Speed and Soft Time Windows for Perishable Product Delivery. IEEE Transactions on Intelligent Transportation Systems, 24(6), 6178–6190. https://doi.org/10.1109/TITS.2023.3249403 DOI: https://doi.org/10.1109/TITS.2023.3249403
Ma, Z.-J., Wu, Y., & Dai, Y. (2017). A combined order selection and time-dependent vehicle routing problem with time widows for perishable product delivery. Computers & Industrial Engineering, 114, 101–113. https://doi.org/10.1016/j.cie.2017.10.010 DOI: https://doi.org/10.1016/j.cie.2017.10.010
Marjan, Y., & Faisal, A. (2025). Strategic Approaches to Carbon Footprint Reduction in Logistics Operations. Logistica : Journal of Logistic and Transportation, 3(2), 69–82. https://doi.org/10.61978/LOGISTICA.V3I2.1073 DOI: https://doi.org/10.61978/logistica.v3i2.1073
Nasrudin, M. F. (2026). Implementation of Sustainable Urban Transportation Policies: A Multiple-Case Study of Indonesian Municipalities. Logistica : Journal of Logistic and Transportation, 4(1), 22–40. https://doi.org/10.61978/LOGISTICA.V4I1.1736 DOI: https://doi.org/10.61978/logistica.v4i1.1736
Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 1–11. https://doi.org/10.1016/j.ejor.2012.08.015 DOI: https://doi.org/10.1016/j.ejor.2012.08.015
Qin, G., Tao, F., & Li, L. (2019). A Vehicle Routing Optimization Problem for Cold Chain Logistics Considering Customer Satisfaction and Carbon Emissions. International Journal of Environmental Research and Public Health, 16(4), 576. https://doi.org/10.3390/ijerph16040576 DOI: https://doi.org/10.3390/ijerph16040576
Rosenkrantz, D. J., Stearns, R. E., & Lewis, I. P. M. (1977). An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM Journal on Computing, 6(3), 563–581. https://doi.org/10.1137/0206041 DOI: https://doi.org/10.1137/0206041
Song, M., Li, J., Han, Y., Han, Y., Liu, L., & Sun, Q. (2020). Metaheuristics for solving the vehicle routing problem with the time windows and energy consumption in cold chain logistics. Applied Soft Computing, 95, 106561. https://doi.org/10.1016/j.asoc.2020.106561 DOI: https://doi.org/10.1016/j.asoc.2020.106561
Thammasang, S., & Arunyanart, S. (2024). Efficient Route Optimization for Ice Distribution: Enhanced VRPTW with Customer Retention Strategies. Engineering, Technology & Applied Science Research, 14(5), 16346–16356. https://doi.org/10.48084/etasr.8239 DOI: https://doi.org/10.48084/etasr.8239
Tirkolaee, E. B., Hadian, S., Weber, G., & Mahdavi, I. (2020). A robust green traffic‐based routing problem for perishable products distribution. Computational Intelligence, 36(1), 80–101. https://doi.org/10.1111/coin.12240 DOI: https://doi.org/10.1111/coin.12240
Toth, P., & Vigo, D. (2014). Vehicle routing: Problems, methods, and applications (2nd ed.) (P. Toth & D. Vigo, Eds.). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973594 DOI: https://doi.org/10.1137/1.9781611973594
Utama, D. M., Dewi, S. K., Wahid, A., & Santoso, I. (2020). The vehicle routing problem for perishable goods: A systematic review. Cogent Engineering, 7(1). https://doi.org/10.1080/23311916.2020.1816148 DOI: https://doi.org/10.1080/23311916.2020.1816148
Wang, X. P., Wang, M., Ruan, J. H., & Li, Y. (2018). Multi-objective optimization for delivering perishable products with mixed time windows. Advances in Production Engineering & Management, 13(3), 321–332. https://doi.org/10.14743/apem2018.3.293 DOI: https://doi.org/10.14743/apem2018.3.293
Wasil, M., Wijayanti, D., & Pahrudin, C. (2025). User Centered Governance and Digital Integration for Inclusive Public Transport: Insights from Palu City. Logistica : Journal of Logistic and Transportation, 3(1), 27–37. https://doi.org/10.61978/LOGISTICA.V3I1.690 DOI: https://doi.org/10.61978/logistica.v3i1.690
Zhang, Y., Zhang, Z., Lim, A., & Sim, M. (2021). Robust Data-Driven Vehicle Routing with Time Windows. Operations Research, 69(2), 469–485. https://doi.org/10.1287/opre.2020.2043 DOI: https://doi.org/10.1287/opre.2020.2043
Zhao, P., Liu, F., Guo, Y., Duan, X., & Zhang, Y. (2021). Bi-Objective Optimization for Vehicle Routing Problems with a Mixed Fleet of Conventional and Electric Vehicles and Soft Time Windows. Journal of Advanced Transportation, 2021, 1–11. https://doi.org/10.1155/2021/9086229 DOI: https://doi.org/10.1155/2021/9086229
Zulvia, F. E., Kuo, R. J., & Nugroho, D. Y. (2020). A many-objective gradient evolution algorithm for solving a green vehicle routing problem with time windows and time dependency for perishable products. Journal of Cleaner Production, 242, 118428. https://doi.org/10.1016/j.jclepro.2019.118428 DOI: https://doi.org/10.1016/j.jclepro.2019.118428
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Rayyan Riansyah, Bryan Estavan Imanuel Sitanggang, Mia Juliana
This work is licensed under a Creative Commons Attribution 4.0 International License.
