Operational Implications of Time Window Relaxation in Vehicle Routing Problems

Abstract

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.

Keywords

• logistics
• minimizing costs
• delivery time constraints
• operational efficiency
• route planning

References

1. 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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

9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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
20. Kim, M., Park, J., & Park, J. (2022). Neuro cross exchange: Learning to cross exchange to solve realistic vehicle routing problems. google scholar
21. 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
22. 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
23. 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
24. 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
25. 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
26. 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
27. 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
28. 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
29. 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
30. 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
31. Mendoza, J., Hoskins, M., Gueret, C., Pillac, V., & Vigo, D. (2014). VRP-REP: A vehicle routing community repository. VeRoLog’14. google scholar
32. 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
33. 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
34. 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
35. 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
36. 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
37. 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
38. 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
39. 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
40. 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
41. Şahin, M., & Aybek, E. (2020). Jamovi: An easy to use statistical software for the social scientists. International Journal of Assessment Tools in google scholar
42. Education, 6(4), 670-692. https://doi.org/10.21449/ijate.661803 google scholar
43. 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
44. 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
45. 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
46. 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
47. The Jamovi Project. (2024). Jamovi (version 2.5) [computer software]. https://www.jamovi.org google scholar
48. Vidal, 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
49. Vidal, 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
50. Wang, 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
51. Yang, 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
52. Ye, 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
53. Zhang, 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