Operational Implications of Time Window Relaxation in Vehicle Routing  Problems

Saygılı, Ahmet; Kazan, Halim

doi:https://dx.doi.org/10.26650/ekoist.2024.41.1490601

Araştırma Makalesi

DOI :10.26650/ekoist.2024.41.1490601 IUP :10.26650/ekoist.2024.41.1490601 Tam Metin (PDF)

Operational Implications of Time Window Relaxation in Vehicle Routing Problems

The Vehicle Routing Problem with Time Windows (VRPTW) poses a significant challenge in logistics, requiring vehicles to meet the objective of minimising costs—such as distance travelled and total travel time—while adhering to specified delivery time constraints and vehicle capacities. This study investigates the implications of relaxing time window constraints by transitioning from VRPTWinstancestostandard Vehicle Routing Problem (VRP) instances. Our findings highlight notable differences between VRP and VRPTW configurations, particularly in total route length and consistency of route metrics. Removal of time window constraints generally resulted in shorter and more uniform route lengths, indicating operational benefits under certain conditions. However,ourcomparisonsalsorevealedsubstantialvariability inroutestructures across datasets, emphasising the cost implications of adhering to strict time windows. This study underscores the critical balance logistics firms must strike between operational efficiency and customer satisfaction when navigating the complexities of VRPTW. This research provides a foundation for future investigations into optimizing route planning under varying logistical constraints, with potential implications for enhanced f lexibility and reduced operational costs despite dynamic delivery requirements. We used a state-of-the-art heuristic solver to solve instances from standard benchmark datasets heavily used for VRPTW literature.

Anahtar Kelimeler: logistics, minimizing costs, delivery time constraints, operational efficiency, route planning

Referanslar

Accorsi, L. (2022, April). Innovative hybrid approaches for vehicle routing problems [Doctoral dissertation, Alma Mater Studiorum Universita di Bologna]. https://doi.org/10.48676/unibo/amsdottorato/10048 google scholar
Alfredo Tang Montane, F., & Galvao, R. D. (2006). A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33(3), 595-619. https://doi.org/https://doi.org/10.1016/j.cor.2004.07.009 google scholar
Bard, J. F., Kontoravdis, G., & Yu, G. (2002). A branch-and-cut procedure for the vehicle routing problem with time windows. Transportation Science, 36(2), 250-269. https://doi.org/10.1287/trsc.36.2.250.565 google scholar
Beling, P., Cybula, P., Jaszkiewicz, A., Pelka, P., Rogalski, M., & Sielski, P. (2022). Deep infeasibility exploration method for vehicle routing problems. In L. Perez Caceres & S. Verel (Eds.), Evolutionary computation in combinatorial optimization (pp. 62-78). Springer International Publishing. https://doi.org/10.1007/978-3-031-04148-8_5 google scholar
Bezanson, J., Edelman, A., Karpinski, S., & Shah, V. B. (2017). Julia: A fresh approach to numerical computing. SIAM Review, 59(1), 65-98. https://doi.org/10.1137/141000671 google scholar
Bouchet-Valat, M., & Kaminski, B. (2023). Dataframes.jl: Flexible and fast tabular data in julia. Journal of Statistical Software, 107 (4), 1-32. https://doi.org/10.18637/jss.v107.i04 google scholar
Braysy, O., & Gendreau, M. (2002). Tabu search heuristics for the vehicle routing problem with time windows. Top, 10(2), 211-237. https://doi.org/10.1007/BF02579017 google scholar
Braysy, O., & Gendreau, M. (2005a). Vehicle routing problem with time windows, part i: Route construction and local search algorithms. Transportation science, 39(1), 104-118. https://doi.org/10.1287/trsc.1030.0056 google scholar
Braysy, O., & Gendreau, M. (2005b). Vehicle routing problem with time windows, part ii: Meta-heuristics. Transportation Science, 39(1), 119-139. https://doi.org/10.1287/trsc.1030.0057 google scholar
Cavaliere, F., Bendotti, E., & Fischetti, M. (2022). An integrated local-search/set-partitioning refinement heuristic for the capacitated vehicle routing problem. Mathematical Programming Computation, 14(4), 749-779. https://doi.org/10.1007/s12532-022-00224-2 google scholar
Christ, S., Schwabeneder, D., Rackauckas, C., Borregaard, M. K., & Breloff, T. (2023). Plots.jl - a user extendable plotting api for the julia programming language. https://doi.org/10.5334/jors.431 google scholar
Cordeau, J.-F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8), 928-936. https://doi.org/10.1057/palgrave.jors.2601163 google scholar
Deflorio, F., Gonzalez-Feliu, J., Perboli, G., & Tadei, R. (2012). The influence of time windows on the costs of urban freight distribution services in city logistics applications. European Journal of Transport and Infrastructure Research, 12(3). https://doi.org/10.18757/ejtir.2012.12.3.2965 google scholar
Desaulniers, G., Madsen, O. B., & Ropke, S. (2014). Chapter 5: The vehicle routing problem with time windows. In Vehicle routing (pp. 119-159). https://doi.Org/10.1137/1.9781611973594.ch5 google scholar
Figliozzi, M. A. (2010). An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows [Applications of Advanced Technologies in Transportation: Selected papers from the 10th AATT Conference]. Transportation Research Part C: Emerging Technologies, 18(5), 668-679. https://doi.org/10.1016/j.trc.2009.08.005 google scholar
Helsgaun, K. (2000). An effective implementation of the lin-kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130. https://doi.org/10.1016/S0377-2217(99)00284-2 google scholar
Helsgaun, K. (2017). An extension of the lin-kernighan-helsgaun tsp solver forconstrained traveling salesman and vehicle routing problems (tech. rep.). Department of Computer Science. Roskilde University. http://akira.ruc.dk/~keld/research/LKHZLKH-3_REPORT.pdf google scholar
Homberger, J., & Gehring, H. (1999). Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR: Information Systems and Operational Research, 37 (3), 297-318. google scholar
Hottung, A., Kwon, Y.-D., & Tierney, K. (2022). Efficient active search for combinatorial optimization problems. International Conference on Learning Representations. https://openreview.net/forum?id=nO5caZwFwYu google scholar
Kim, M., Park, J., & Park, J. (2022). Neuro cross exchange: Learning to cross exchange to solve realistic vehicle routing problems. google scholar
Köhler, C., Ehmke, J. F., Campbell, A. M., & Cleophas, C. (2023). Evaluating pricing strategies for premium delivery time windows. EURO Journal on Transportation and Logistics, 12, 100108. https://doi.org/10.1016/j.ejtl.2023.100108 google scholar
Kool, W., Juninck, J. O., Roos, E., Cornelissen, K., Agterberg, P., van Hoorn, J., & Visser, T. (2022). Hybrid genetic search for the vehicle routing problem with time windows: A high-performance implementation. 12th DIMACS Implementation Challenge Workshop. google scholar
Labadie, N., Prins, C., & Prodhon, C. (2016). Simple heuristics and local search procedures. In Metaheuristics for vehicle routing problems (pp. 15-37). John Wiley & Sons, Ltd. https://doi.org/10.1002/9781119136767.ch2 google scholar
Laporte, G., Ropke, S., & Vidal, T. (2014). Chapter 4: Heuristics for the vehicle routing problem. In Vehicle routing (pp. 87-116). https://doi.org/10.1137/1.9781611973594.ch4 google scholar
Leuschner, R., Charvet, F., & Rogers, D. S. (2013). A meta-analysis of logistics customer service. Journal of Supply Chain Management, 49(1), 47-63. https://doi.org/10.1111/jscm.12000 google scholar
Li, S., Yan, Z., & Wu, C. (2021). Learning to delegate for large-scale vehicle routing. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, & J. W. Vaughan (Eds.), Advances in neural information processing systems (pp. 26198-26211, Vol. 34). Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2021/file/dc9fa5f217a1e57b8a6adeb065560b38-Paper.pdf google scholar
Liu, R., Xie, X., Augusto, V., & Rodriguez, C. (2013). Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. European Journal of Operational Research, 230(3), 475-486. https://doi.org/https://doi.org/10.1016/j.ejor.2013.04.044 google scholar
Liu, Y., Roberto, B., Zhou, J., Yu, Y., Zhang, Y., & Sun, W. (2023). Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows. European Journal of Operational Research, 310(1), 133-155. https://doi.org/https://doi.org/10.1016/j.ejor.2023.02.028 google scholar
Löwens, C., Ashraf, I., Gembus, A., Cuizon, G., Falkner, J. K., & Schmidt-Thieme, L. (2022). Solving the traveling salesperson problem with precedence constraints by deep reinforcement learning. In R. Bergmann, L. Malburg, S. C. Rodermund, & I. J. Timm (Eds.), Ki 2022: Advances in artificial intelligence (pp. 160-172). Springer International Publishing. https://doi.org/10.1007/978-3-031-15791-2_14 google scholar
Meira, L. A., Martins, P. S., Menzori, M., & Zeni, G. A. (2020). Chapter 8 - how to assess your smart delivery system?: Benchmarks for rich vehicle routing problems. In J. Nalepa (Ed.), Smart delivery systems (pp. 227-247). Elsevier. https://doi.org/https://doi.org/10.1016/B978-0-12-815715-2.00007-5 google scholar
Mendoza, J., Hoskins, M., Gueret, C., Pillac, V., & Vigo, D. (2014). VRP-REP: A vehicle routing community repository. VeRoLog’14. google scholar
Muniasamy, R. P., Singh, S., Nasre, R., & Narayanaswamy, N. (2023). Effective parallelization of the vehicle routing problem. Proceedings of the Genetic and Evolutionary Computation Conference, 1036-1044. https://doi.org/10.1145/3583131.3590458 google scholar
Nazif, H., & Lee, L. (2010). Optimized crossover genetic algorithm for vehicle routing problem with time windows. American Journal of Applied Sciences, 7, 95-101. https://doi.org/10.3844/ajassp.2010.95.101 google scholar
Osorio-Mora, A., Escobar, J. W., & Toth, P. (2023). An iterated local search algorithm for latency vehicle routing problems with multiple depots. Computers & Operations Research, 158, 106293. https://doi.org/10.1016/j.cor.2023.106293 google scholar
Page M J, McKenzie J E, Bossuyt P M, Boutron I, Hoffmann T C, Mulrow C D et al. The PRISMA 2020 statement: an updated guideline for reporting systematic reviews BMJ 2021; 372 :n71 https://doi.org/10.1136/bmj.n71 google scholar
Pan, X., Jin, Y., Ding, Y., Feng, M., Zhao, L., Song, L., & Bian, J. (2023). H-tsp: Hierarchically solving the large-scale traveling salesman problem. Proceedings of the AAAI Conference on Artificial Intelligence, 37 (8), 9345-9353. https://doi.org/10.1609/aaai.v37i8.26120 google scholar
Pecin, D., Contardo, C., Desaulniers, G., & Uchoa, E. (2017). New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS Journal on Computing, 29(3), 489-502. https://doi.org/10.1287/ijoc.2016.0744 google scholar
Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & operations research, 34(8), 2403-2435. https://doi.org/10.1016/j.cor.2005.09.012 google scholar
Prodhon, C., & Prins, C. (2016). Metaheuristics for vehicle routing problems. In P. Siarry (Ed.), Metaheuristics (pp. 407-437). Springer International Publishing. https://doi.org/10.1007/978-3-319-45403-0_15 google scholar
R Core Team. (2024). R: A language and environment for statistical computing. R Foundation for Statistical Computing. Vienna, Austria. https://www. R-project.org google scholar
Şahin, M., & Aybek, E. (2020). Jamovi: An easy to use statistical software for the social scientists. International Journal of Assessment Tools in google scholar
Education, 6(4), 670-692. https://doi.org/10.21449/ijate.661803 google scholar
Salari, N., Liu, S., & Shen, Z.-J. M. (2022). Real-time delivery time forecasting and promising in online retailing: When will your package arrive? Manufacturing & Service Operations Management, 24(3), 1421-1436. https://doi.org/10.1287/msom.2022.1081 google scholar
Schaumann, S. K., Bergmann, F. M., Wagner, S. M., & Winkenbach, M. (2023). Route efficiency implications of time windows and vehicle capac-ities in first- and last-mile logistics. European Journal of Operational Research, 311(1), 88-111. https://doi.org/10.1016/j.ejor.2023.04.018 google scholar
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265. https://doi.org/10.1287/opre.35.2.254 google scholar
Sun, Z., & Yang, Y. (2023). Difusco: Graph-based diffusion solvers for combinatorial optimization. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, & S. Levine (Eds.), Advances in neural information processing systems (pp. 3706-3731, Vol. 36). Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2023/file/0ba520d93c3df592c83a611961314c98-Paper-Conference.pdf google scholar
The Jamovi Project. (2024). Jamovi (version 2.5) [computer software]. https://www.jamovi.org google scholar
V idal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). A hybrid genetic algorithm with adaptive diversity manage-ment for a large class of vehicle routing problems with time-windows. Computers & Operations Research, 40(1), 475-489. https://doi.org/https://doi.org/10.1016/j.cor.2012.07.018 google scholar
V idal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3), 658-673. https://doi.org/https://doi.org/10.1016/j.ejor.2013.09.045 google scholar
W ang, C., Zhao, F., Mu, D., Sutherland, J.W. (2013). Simulated Annealing for a Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows. In: Prabhu, V., Taisch, M., Kiritsis, D. (eds) Advances in Production Management Systems. Sustainable Production and Service Supply Chains. APMS 2013. IFIP Advances in Information and Communication Technology, vol 415. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41263-9_21 google scholar
Y ang, R., & Fan, C. (2024). A hierarchical framework for solving the constrained multiple depot traveling salesman problem. IEEE Robotics and Automation Letters, 1-8. https://doi.org/10.1109/LRA.2024.3389817 google scholar
Y e, H., Wang, J., Cao, Z., Liang, H., & Li, Y. (2023). Deepaco: Neural-enhanced ant systems for combinatorial optimization. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, & S. Levine (Eds.), Advances in neural information processing systems (pp. 43706-43728, Vol. 36). Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2023/file/883105b282fe15275991b411e6b200c5-Paper-Conference.pdf google scholar
Z hang, Y., Zhang, D., Wang, L., He, Z., Hu, H. (2020). Balancing Exploration and Exploitation in the Memetic Algorithm via a Switching Mechanism for the Large-Scale VRPTW. In: Nah, Y., Cui, B., Lee, SW., Yu, J.X., Moon, YS., Whang, S.E. (eds) Database Systems for Advanced Applications. DASFAA 2020. Lecture Notes in Computer google scholar

Atıflar

Biçimlendirilmiş bir atıfı kopyalayıp yapıştırın veya seçtiğiniz biçimde dışa aktarmak için seçeneklerden birini kullanın

DIŞA AKTAR

APA

Saygılı, A.Ç., & Kazan, H. (2024). Operational Implications of Time Window Relaxation in Vehicle Routing Problems. EKOIST Journal of Econometrics and Statistics, 0(41), 54-81. https://doi.org/10.26650/ekoist.2024.41.1490601

AMA

Saygılı A Ç, Kazan H. Operational Implications of Time Window Relaxation in Vehicle Routing Problems. EKOIST Journal of Econometrics and Statistics. 2024;0(41):54-81. https://doi.org/10.26650/ekoist.2024.41.1490601

ABNT

Saygılı, A.Ç.; Kazan, H. Operational Implications of Time Window Relaxation in Vehicle Routing Problems. EKOIST Journal of Econometrics and Statistics, [Publisher Location], v. 0, n. 41, p. 54-81, 2024.

Chicago: Author-Date Style

Saygılı, Ahmet Çağlar, and Halim Kazan. 2024. “Operational Implications of Time Window Relaxation in Vehicle Routing Problems.” EKOIST Journal of Econometrics and Statistics 0, no. 41: 54-81. https://doi.org/10.26650/ekoist.2024.41.1490601

Chicago: Humanities Style

Saygılı, Ahmet Çağlar, and Halim Kazan. “Operational Implications of Time Window Relaxation in Vehicle Routing Problems.” EKOIST Journal of Econometrics and Statistics 0, no. 41 (Mar. 2025): 54-81. https://doi.org/10.26650/ekoist.2024.41.1490601

Harvard: Australian Style

Saygılı, AÇ & Kazan, H 2024, 'Operational Implications of Time Window Relaxation in Vehicle Routing Problems', EKOIST Journal of Econometrics and Statistics, vol. 0, no. 41, pp. 54-81, viewed 10 Mar. 2025, https://doi.org/10.26650/ekoist.2024.41.1490601

Harvard: Author-Date Style

Saygılı, A.Ç. and Kazan, H. (2024) ‘Operational Implications of Time Window Relaxation in Vehicle Routing Problems’, EKOIST Journal of Econometrics and Statistics, 0(41), pp. 54-81. https://doi.org/10.26650/ekoist.2024.41.1490601 (10 Mar. 2025).

MLA

Saygılı, Ahmet Çağlar, and Halim Kazan. “Operational Implications of Time Window Relaxation in Vehicle Routing Problems.” EKOIST Journal of Econometrics and Statistics, vol. 0, no. 41, 2024, pp. 54-81. [Database Container], https://doi.org/10.26650/ekoist.2024.41.1490601

Vancouver

Saygılı AÇ, Kazan H. Operational Implications of Time Window Relaxation in Vehicle Routing Problems. EKOIST Journal of Econometrics and Statistics [Internet]. 10 Mar. 2025 [cited 10 Mar. 2025];0(41):54-81. Available from: https://doi.org/10.26650/ekoist.2024.41.1490601 doi: 10.26650/ekoist.2024.41.1490601

ISNAD

Saygılı, AhmetÇağlar - Kazan, Halim. “Operational Implications of Time Window Relaxation in Vehicle Routing Problems”. EKOIST Journal of Econometrics and Statistics 0/41 (Mar. 2025): 54-81. https://doi.org/10.26650/ekoist.2024.41.1490601

Sayı 412024, S. 54-81

ZAMAN ÇİZELGESİ

Gönderim	07.06.2024
Kabul	19.07.2024
Çevrimiçi Yayınlanma	06.09.2024

LİSANS

Attribution-NonCommercial (CC BY-NC)

This license lets others remix, tweak, and build upon your work non-commercially, and although their new works must also acknowledge you and be non-commercial, they don’t have to license their derivative works on the same terms.

EKOIST Journal of Econometrics and Statistics