TY  - JOUR
T1  - Operational Implications of Time Window Relaxation in Vehicle Routing Problems
AU  - Saygılı, Ahmet Çağlar
AU  - Kazan, Halim
PY  - 2024
DA  - December
Y2  - 2024
DO  - 10.26650/ekoist.2024.41.1490601
JF  - EKOIST Journal of Econometrics and Statistics
PB  - Istanbul University
WT  - DergiPark
SN  - 2651-396X
SP  - 54
EP  - 81
IS  - 41
LA  - en
AB  - 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.
KW  - logistics
KW  - minimizing costs
KW  - delivery time constraints
KW  - operational efficiency
KW  - route planning
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - Kim, M., Park, J., & Park, J. (2022). Neuro cross exchange: Learning to cross exchange to solve realistic vehicle routing problems. google scholar
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - Mendoza, J., Hoskins, M., Gueret, C., Pillac, V., & Vigo, D. (2014). VRP-REP: A vehicle routing community repository. VeRoLog’14. google scholar
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - Şahin, M., & Aybek, E. (2020). Jamovi: An easy to use statistical software for the social scientists. International Journal of Assessment Tools in google scholar
CR  - Education, 6(4), 670-692. https://doi.org/10.21449/ijate.661803 google scholar
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - The Jamovi Project. (2024). Jamovi (version 2.5) [computer software]. https://www.jamovi.org google scholar
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
UR  - https://doi.org/10.26650/ekoist.2024.41.1490601
L1  - https://dergipark.org.tr/en/download/article-file/3958822
ER  -