SavedAdd your journal

Journals / Ekoist: Journal of Econometrics and Statistics / 2024 / Sayı: 41

Operational Implications of Time Window Relaxation in Vehicle Routing Problems

Ahmet Çağlar Saygılı(ISTANBUL UNIVERSITY, FACULTY OF ECONOMICS, DEPARTMENT OF BUSINESS, BUSINESS ADMINISTRATION PR.)0000-0003-0724-1395
Halim Kazan(ISTANBUL UNIVERSITY, FACULTY OF ECONOMICS, DEPARTMENT OF BUSINESS, BUSINESS ADMINISTRATION PR.)0000-0002-9234-6214
Pages
54–81
Publication Date
2024-12-26
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

We used a state-of-the-art heuristic solver to solve instances from standard benchmark datasets heavily used for VRPTW literature.

📌 3 Key Takeaways

🎯
Objective & Hypothesis: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.
📊
Key Findings & Data:This study investigates the implications of relaxing time window constraints by transitioning from VRPTWinstancestostandard Vehicle Routing Problem (VRP) instances.
💡
Conclusion & Impact:We used a state-of-the-art heuristic solver to solve instances from standard benchmark datasets heavily used for VRPTW literature.
🔬Design:Araştırma Makalesi
📍Scope:Comprehensive Sample
⚙️Variables:logistics · minimizing costs · delivery time constraints

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.

🔖

Cite This Article

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

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (54)

  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
  54. 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