Time Window Characteristics in a Heuristic Algorithm for a Full-Truck Vehicle Routing Heuristic Algorithm in An Intermodal Context
Main Article Content
Keywords
deterministic annealing, time windows, intermodal transport, concentration and specialization, metaheuristics
Abstract
Intermodal container terminals handle both the pickup and delivery of containers to and from customers, with these transport activities and terminal handling comprising a significant portion of intermodal transport costs. Efficient operations are therefore essential, particularly when time window constraints limit routing flexibility. This study presents a metaheuristic incorporating time windows to plan container pickups and deliveries. The proposed algorithm operates in three phases: initial solution construction using an insertion heuristic, improvement via local search, and further refinement through a deterministic annealing metaheuristic. The presence of time windows makes the planning more difficult, as the transport company has less flexibility in constructing the transport routes and, as a result, the distance travelled and/or the cost is increased. To assess how time window characteristics affect algorithm performance and
cost, the study introduces two temporal descriptors—concentration (the clustering of time windows during the day) and specialization (the dominance of short or long-time windows in specific periods). The results of the experimental runs of the algorithm are statistically analysed to identify under which conditions of concentration and specialization an effect on the cost can be identified. Experimental results reveal that increased concentration leads to a rise in both the number of routes (up to 35%) and total cost (around 2%). While concentration results in more routes, these routes remain relatively cost-efficient. Furthermore, a lack of specialization in concentrated time windows amplifies both the number of routes and the total cost. Finally, the length of time windows influences these effects, with shorter time windows having a reduced impact on concentration and specialization outcomes compared to longer ones.
References
[2] V. Pencheva, A. Asenov, A. Sladkowski, B. Ivanov, and I. Georgiev, “Current Issues of Multimodal and Intermodal Cargo Transportation,” Studies in Systems, Decision and Control, vol. 400, pp. 51–124, 2022, doi: 10.1007/978-3-030-87120-8_2.
[3] I. Makarova et al., “The Role of Multimodal Transportation in Ensuring Sustainable Territorial Development: Review of Risks and Prospects,” Sustainability (Switzerland), vol. 15, no. 7, Apr. 2023, doi: 10.3390/su15076309.
[4] C. Macharis, A. Caris, B. Jourquin, and E. Pekin, “A decision support framework for intermodal transport policy,” European Transport Research Review, vol. 3, no. 4, pp. 167–178, Dec. 2011, doi: 10.1007/s12544-011-0062-5.
[5] V. Paulauskas et al., “Optimizing Transportation between Sea Ports and Regions by Road Transport and Rail and Inland Waterway Transport Means Including ‘Last Mile’ Solutions,” Applied Sciences (Switzerland), vol. 12, no. 20, Oct. 2022, doi: 10.3390/app122010652.
[6] X. Yu, Y. Feng, C. He, and C. Liu, “Modeling and Optimization of Container Drayage Problem with Empty Container Constraints across Multiple Inland Depots,” Sustainability, vol. 16, no. 12, p. 5090, Jun. 2024, doi: 10.3390/su16125090.
[7] A. Escudero-Santana, J. Muñuzuri, P. Cortés, and L. Onieva, “The one container drayage problem with soft time windows,” Research in Transportation Economics, vol. 90, Dec. 2021, doi: 10.1016/j.retrec.2020.100884.
[8] S. Gbako, D. Paraskevadakis, J. Ren, J. Wang, and Z. Radmilovic, “A systematic literature review of technological developments and challenges for inland waterways freight transport in intermodal supply chain management,” Benchmarking: An International Journal, vol. 32, no. 1, pp. 398–431, 2024.
[9] A. Caris, C. Macharis, and G. K. Janssens, “Decision support in intermodal transport: A new research agenda,” Comput Ind, vol. 64, no. 2, pp. 105–112, Feb. 2013, doi: 10.1016/j.compind.2012.12.001.
[10] H. Heggen, Y. Molenbruch, A. Caris, and K. Braekers, “Intermodal container routing: Integrating Long-Haul routing and local drayage decisions,” Sustainability (Switzerland), vol. 11, no. 6, 2019, doi: 10.3390/su11061634.
[11] A. El Yaagoubi et al., “A logistic model for a French intermodal rail/road freight transportation system,” Transp Res E Logist Transp Rev, vol. 164, Aug. 2022, doi: 10.1016/j.tre.2022.102819.
[12] L. B. Reinhardt, D. Pisinger, S. Spoorendonk, and M. M. Sigurd, “Optimization of the drayage problem using exact methods,” INFOR, vol. 54, no. 1, pp. 33–51, 2016, doi: 10.1080/03155986.2016.1149919.
[13] R. Chen, Q. Meng, and P. Jia, “Container port drayage operations and management: Past and future,” Transp Res E Logist Transp Rev, vol. 159, Mar. 2022, doi: 10.1016/j.tre.2022.102633.
[14] A. Caris and G. K. Janssens, “A local search heuristic for the pre- and end-haulage of intermodal container terminals,” Comput Oper Res, vol. 36, no. 10, pp. 2763–2772, Oct. 2009, doi: 10.1016/j.cor.2008.12.007.
[15] M. Gronalt, R. F. Hartl, and M. Reimann, “New savings based algorithms for time constrained pickup and delivery of full truckloads,” Eur J Oper Res, vol. 151, no. 3, pp. 520–535, Dec. 2003, doi: 10.1016/S0377-2217(02)00650-1.
[16] B. Eksioglu, A. V. Vural, and A. Reisman, “The vehicle routing problem: A taxonomic review,” Comput Ind Eng, vol. 57, no. 4, pp. 1472–1483, Nov. 2009, doi: 10.1016/j.cie.2009.05.009.
[17] 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, Sep. 2016, doi: 10.1016/j.cie.2015.12.007.
[18] A. Annouch, K. Bouyahyaoui, and A. Bellabdaoui, “A literature review on the full truckload vehicle routing problems,” in Proceedings of the 3rd IEEE International Conference on Logistics Operations Management, 2016, pp. 1–6.
[19] K. Sar and P. Ghadimi, “A systematic literature review of the vehicle routing problem in reverse logistics operations,” Comput Ind Eng, vol. 177, Mar. 2023, doi: 10.1016/j.cie.2023.109011.
[20] N. Sluijk, A. M. Florio, J. Kinable, N. Dellaert, and T. Van Woensel, “Two-echelon vehicle routing problems: A literature review,” Eur J Oper Res, vol. 304, no. 3, pp. 865–886, Feb. 2023, doi: 10.1016/j.ejor.2022.02.022.
[21] W. Gu, C. Archetti, D. Cattaruzza, M. Ogier, F. Semet, and M. G. Speranza, “Vehicle routing problems with multiple commodities: A survey,” Eur J Oper Res, pp. 1–15, 2024, doi: 10.1016/j.ejor.2023.11.032ï.
[22] K. Ramaekers, A. Caris, S. Moons, and T. van Gils, “Using an integrated order picking-vehicle routing problem to study the impact of delivery time windows in e-commerce,” European Transport Research Review, vol. 10, no. 2, Jun. 2018, doi: 10.1186/s12544-018-0333-5.
[23] A. Caris and G. K. Janssens, “A deterministic annealing algorithm for the pre-and end-haulage of intermodal container terminals A deterministic annealing algorithm for the pre-and end-haulage,” Int. J. Computer Aided Engineering and Technology, vol. 2, no. 4, pp. 340–355, 2010.
[24] I. H. Osman, “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem,” Ann Oper Res, vol. 41, no. 4, pp. 421–451, Dec. 1993, doi: 10.1007/BF02023004.
[25] I. Kaku, Y. Xiao, and G. Xia, “The deterministic annealing algorithms for vehicle routing problems,” International Journal of Smart Engineering System Design, vol. 5, no. 4, pp. 327–339, Oct. 2003, doi: 10.1080/10255810390224080.
[26] C. D. Tarantilis, C. T. Kiranoudis, and V. S. Vassiliadis, “A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem,” Eur J Oper Res, vol. 152, no. 1, pp. 148–158, Jan. 2004, doi: 10.1016/S0377-2217(02)00669-0.
[27] O. Bräysy, W. Dullaert, G. Hasle, D. Mester, and M. Gendreau, “An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows,” Transportation Science, vol. 42, no. 3, pp. 371–386, 2008, doi: 10.1287/trsc.l070.0217.
[28] Y. Su, N. Dupin, and J. Puchinger, “A deterministic annealing local search for the electric autonomous dial-a-ride problem,” Eur J Oper Res, vol. 309, no. 3, pp. 1091–1111, Sep. 2023, doi: 10.1016/j.ejor.2023.02.012.
[29] K. Braekers, A. Caris, and G. K. Janssens, “Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots,” Transportation Research Part B: Methodological, vol. 67, pp. 166–186, 2014, doi: 10.1016/j.trb.2014.05.007.
[30] S. Brakman, H. Garretsen, and C. van Marrewijk, An Introduction to Geographical Economics. Cambridge University Press, 2001.
[31] M. L. Balinski and R. E. Quandt, “On an Integer Program for a Delivery Problem,” Oper Res, vol. 12, no. 2, pp. 300–304, 1964, [Online]. Available: https://about.jstor.org/terms
[32] F. H. Cullen, J. J. Jarvis, and D. H. Ratliff, “Set partitioning based heuristics for interactive routing,” Networks, vol. 11, no. 2, pp. 125–144, 1981.
[33] A. Ghezelsoflu, M. Di Francesco, A. Frangioni, and P. Zuddas, “A set-covering formulation for a drayage problem with single and double container loads,” Journal of Industrial Engineering International, vol. 14, no. 4, pp. 665–676, Dec. 2018, doi: 10.1007/s40092-018-0256-8.
[34] D. Cattaruzza, N. Absi, and D. Feillet, “Vehicle routing problems with multiple trips,” A Quarterly Journal of Operations Research, vol. 14, no. 3, pp. 223–259, 2016, doi: 10.1007/s10288-016-0306-2ï.
Article Sidebar
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright Ownership
- Authors who publish their articles in Jurnal Optimasi Sistem Industri (JOSI) retain full copyright of their work.
- JOSI does not require authors to transfer their copyright to the journal or its publisher, Universitas Andalas. The authors grant JOSI a license for first publication.
All articles published in Jurnal Optimasi Sistem Industri (JOSI) are licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) license.
This means that users are free to:
- Share — copy and redistribute the material in any medium or format.
- Adapt — remix, transform, and build upon the material.
Under the following terms:
- Attribution (BY): You must give appropriate credit to the author(s) and JOSI as the original source of publication (including the article title, author(s) names, journal name, volume, issue, page numbers, year, and DOI), provide a link to the CC BY-NC-SA 4.0 license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- NonCommercial (NC): You may not use the material for commercial purposes.
- ShareAlike (SA): If you remix, transform, or build upon the material, you must distribute your contributions under the same CC BY-NC-SA 4.0 license as the original.
A link to the full license text should also be provided: https://creativecommons.org/licenses/by-nc-sa/4.0/
Wisute Ongcunaruk, King Mongkut’s University of Technology North Bangkok
Wisute Ongcunaruk was born in Bangkok, Thailand. He received a B.E. (Hons) in Electrical Engineering, first class, King Mongkut's University of Technology North Bangkok. Since 1995, he has served as a lecturer in the Faculty of Engineering at the same university. Presently, he holds the position of assistant professor in the Department of Electrical and Computer Engineering within the Faculty of Engineering. His academic pursuits encompass Numerical Methods, Location, Machine Learning, Railway Signaling, and Simulation.
Pornthipa Ongkunaruk, Kasetsart University
Pornthipa Ongkunaruk holds an M.S. in Industrial Engineering from the Asian Institute of Technology and a Ph.D. in Industrial and Systems Engineering from Virginia Tech. She is currently the Director of the Center for Advanced Studies in Industrial Technology and an Associate Professor in the Department of Industrial Engineering, Faculty of Engineering, Kasetsart University. Her academic and research interests include Supply Chain and Logistics Management, Operations Research, and Simulation.
Gerrit K. Janssens , Hasselt University
Gerrit K. Janssens received an M.S. degree in Computer Science from the University of Ghent, and a Ph.D. in Computer Science from the Free University of Brussels. He was a Professor of Operations Management and Logistics at Hasselt University, Belgium. He is now an Emeritus Professor within the Research Group Logistics. He is the CEO (Delegate Administrator) of the Belgian Operations Research Society (ORBEL). He is the president of the European Scientific Simulation Society Eurosis.
