A Template-Based Hybrid Large Neighborhood Search for the Consistent Vehicle Routing Problem with Time-Dependent Travel Times
Hossein Nikdel
1
(
Alborz Campus, University of Tehran, Tehran, Iran
)
Mohammad Mahdi Nasiri
2
(
School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
)
S. Mohammad J. Mirzapour Al-e-Hashem
3
(
Department of Industrial Engineering and Management Systems, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran
)
کلید واژه: Consistent Vehicle Routing Problem, Template, Large Neighborhood Search, Variable Neighborhood Search, Time-Dependent Travel Times, Departure-Time Adjustment,
چکیده مقاله :
Customer satisfaction attracts increasing attention in competitive environments. The consistent vehicle routing problem (ConVRP), introduced in recent years, incorporates customer satisfaction into VRP. In ConVRP, vehicle routes must be designed for multiple periods, and each customer must be visited by the same driver at roughly the same time on each period. Previous ConVRP research models travel times as constant and based only on distance. This is unrealistic for urban areas, where travel times vary dynamically with factors like congestion and time of day. The time-dependent VRP (TDVRP) incorporates time-varying travel times. In this paper, the ConVRP is considered with time-dependent travel times to integrate the TDVRP and ConVRP models. A mixed-integer linear programming (MILP) model is proposed for the new problem, termed the consistent TDVRP (ConTDVRP). We extend the ConVRP benchmark instances from the literature by incorporating time-dependent travel times. The model is solved using a solver for small-scale instances. Since the new problem -an extension of the two aforementioned models- is NP-hard, we propose a template-based hybrid large neighborhood search (THLNS) algorithm that incorporates variable neighborhood search (VNS) to solve it. An iterative procedure is also presented to modify a heuristic departure-time adjustment in the literature to be used with time-dependent travel times. Computational experiments and sensitivity analysis are performed on new extended instances to evaluate the efficiency of the proposed algorithm. Three presented methods in ConVRP literature are adapted to solve ConTDVRP and the results of proposed approach compared with them for three time-dependent speed profiles on extended instances. The results demonstrate that the proposed method not only achieves consistent solutions with reduced computation time but also delivers solutions with 13.38%, 10.61%, and 35.67% lower average travel times compared to the three alternative methods. Departure-time adjustment also results in 17.48% lower average travel times and 5.91% better time consistency across all benchmark instances and speed profiles.
چکیده انگلیسی :
Customer satisfaction attracts increasing attention in competitive environments. The consistent vehicle routing problem (ConVRP), introduced in recent years, incorporates customer satisfaction into VRP. In ConVRP, vehicle routes must be designed for multiple periods, and each customer must be visited by the same driver at roughly the same time on each period. Previous ConVRP research models travel times as constant and based only on distance. This is unrealistic for urban areas, where travel times vary dynamically with factors like congestion and time of day. The time-dependent VRP (TDVRP) incorporates time-varying travel times. In this paper, the ConVRP is considered with time-dependent travel times to integrate the TDVRP and ConVRP models. A mixed-integer linear programming (MILP) model is proposed for the new problem, termed the consistent TDVRP (ConTDVRP). We extend the ConVRP benchmark instances from the literature by incorporating time-dependent travel times. The model is solved using a solver for small-scale instances. Since the new problem -an extension of the two aforementioned models- is NP-hard, we propose a template-based hybrid large neighborhood search (THLNS) algorithm that incorporates variable neighborhood search (VNS) to solve it. An iterative procedure is also presented to modify a heuristic departure-time adjustment in the literature to be used with time-dependent travel times. Computational experiments and sensitivity analysis are performed on new extended instances to evaluate the efficiency of the proposed algorithm. Three presented methods in ConVRP literature are adapted to solve ConTDVRP and the results of proposed approach compared with them for three time-dependent speed profiles on extended instances. The results demonstrate that the proposed method not only achieves consistent solutions with reduced computation time but also delivers solutions with 13.38%, 10.61%, and 35.67% lower average travel times compared to the three alternative methods. Departure-time adjustment also results in 17.48% lower average travel times and 5.91% better time consistency across all benchmark instances and speed profiles.
Adamo, T., Gendreau, M., Ghiani, G., & Guerriero, E. (2024). A review of recent advances in time-dependent vehicle routing. European Journal of Operational Research.
Ahn, B.-H., & Shin, J.-Y. (1991). Vehicle-routeing with time windows and time-varying congestion. Journal of the Operational Research Society, 42(5), 393-400.
Alinaghian, M., & Naderipour, M. (2016). A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption: A case study. Computers & Industrial Engineering, 99, 210-222.
Alvarez, A., Cordeau, J.-F., & Jans, R. (2024). The consistent vehicle routing problem with stochastic customers and demands. Transportation Research Part B: Methodological, 186, 102968.
Balseiro, S. R., Loiseau, I., & Ramonet, J. (2011). An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows. Computers & Operations Research, 38(6), 954-966.
Beasley, J. (1981). Adapting the savings algorithm for varying inter-customer travel times. Omega, 9(6), 658-659.
Braekers, K., & Kovacs, A. A. (2016). A multi-period dial-a-ride problem with driver consistency. Transportation Research Part B: Methodological, 94, 355-377.
Cai, L., Lv, W., Xiao, L., & Xu, Z. (2021). Total carbon emissions minimization in connected and automated vehicle routing problem with speed variables. Expert Systems with Applications, 165, 113910.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581.
Dabia, S., Ropke, S., Van Woensel, T., & De Kok, T. (2013). Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Science, 47(3), 380-396.
Donati, A. V., Montemanni, R., Casagrande, N., Rizzoli, A. E., & Gambardella, L. M. (2008). Time dependent vehicle routing problem with a multi ant colony system. European Journal of Operational Research, 185(3), 1174-1191.
Fan, H., Zhang, Y., Tian, P., Lv, Y., & Fan, H. (2021). Time-dependent multi-depot green vehicle routing problem with time windows considering temporal-spatial distance. Computers & Operations Research, 129, 105211.
Feillet, D., Garaix, T., Lehuédé, F., Péton, O., & Quadri, D. (2014). A new consistent vehicle routing problem for the transportation of people with disabilities. Networks, 63(3), 211-224.
Figliozzi, M. A. (2012). The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transportation Research Part E: Logistics and Transportation Review, 48(3), 616-636.
Fleischmann, B., Gietz, M., & Gnutzmann, S. (2004). Time-varying travel times in vehicle routing. Transportation Science, 38(2), 160-173.
Gendreau, M., Ghiani, G., & Guerriero, E. (2015). Time-dependent routing problems: A review. Computers & Operations Research, 64, 189-197.
Gmira, M., Gendreau, M., Lodi, A., & Potvin, J.-Y. (2021). Tabu search for the time-dependent vehicle routing problem with time windows on a road network. European Journal of Operational Research, 288(1), 129-140.
Goeke, D., Roberti, R., & Schneider, M. (2019). Exact and heuristic solution of the consistent vehicle-routing problem. Transportation Science, 53(4), 1023-1042.
Groër, C., Golden, B., & Wasil, E. (2009). The consistent vehicle routing problem. Manufacturing & service operations management, 11(4), 630-643.
Haghani, A., & Jung, S. (2005). A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 32(11), 2959-2986.
Hashimoto, H., Yagiura, M., & Ibaraki, T. (2008). An iterated local search algorithm for the time-dependent vehicle routing problem with time windows. Discrete Optimization, 5(2), 434-456.
Hill, A. V., & Benton, W. C. (1992). Modelling intra-city time-dependent travel speeds for vehicle scheduling problems. Journal of the Operational Research Society, 43(4), 343-351.
Huang, Y., Zhao, L., Van Woensel, T., & Gross, J.-P. (2017). Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B: Methodological, 95, 169-195.
Ichoua, S., Gendreau, M., & Potvin, J.-Y. (2003). Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 144(2), 379-396.
Jie, K.-W., Liu, S.-Y., & Sun, X.-J. (2022). A hybrid algorithm for time-dependent vehicle routing problem with soft time windows and stochastic factors. Engineering Applications of Artificial Intelligence, 109, 104606.
Jost, C., Jungwirth, A., Kolisch, R., & Schiffels, S. (2022). Consistent vehicle routing with pickup decisions-Insights from sport academy training transfers. European Journal of Operational Research, 298(1), 337-350.
Jung, S., & Haghani, A. (2001). Genetic algorithm for the time-dependent vehicle routing problem. Transportation Research Record, 1771(1), 164-171.
Kok, A. L., Hans, E. W., & Schutten, J. M. (2012). Vehicle routing under time-dependent travel times: the impact of congestion avoidance. Computers & Operations Research, 39(5), 910-918.
Kovacs, A. A., Golden, B. L., Hartl, R. F., & Parragh, S. N. (2014). Vehicle routing problems in which consistency considerations are important: A survey. Networks, 64(3), 192-213.
Kovacs, A. A., Golden, B. L., Hartl, R. F., & Parragh, S. N. (2015). The generalized consistent vehicle routing problem. Transportation Science, 49(4), 796-816.
Kovacs, A. A., Parragh, S. N., & Hartl, R. F. (2014). A template‐based adaptive large neighborhood search for the consistent vehicle routing problem. Networks, 63(1), 60-81.
Kovacs, A. A., Parragh, S. N., & Hartl, R. F. (2015). The multi-objective generalized consistent vehicle routing problem. European Journal of Operational Research, 247(2), 441-458.
Lian, K., Milburn, A. B., & Rardin, R. L. (2016). An improved multi-directional local search algorithm for the multi-objective consistent vehicle routing problem. Iie Transactions, 48(10), 975-992.
Liu, C., Kou, G., Zhou, X., Peng, Y., Sheng, H., & Alsaadi, F. E. (2020). Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach. Knowledge-Based Systems, 188, 104813.
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.
Lu, J., Chen, Y., Hao, J.-K., & He, R. (2020). The time-dependent electric vehicle routing problem: Model and solution. Expert Systems with Applications, 161, 113593.
Luo, Z., Qin, H., Che, C., & Lim, A. (2015). On service consistency in multi-period vehicle routing. European Journal of Operational Research, 243(3), 731-744.
Maden, W., Eglese, R., & Black, D. (2010). Vehicle routing and scheduling with time-varying data: A case study. Journal of the Operational Research Society, 61(3), 515-522.
Malandraki, C., & Daskin, M. S. (1992). Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation Science, 26(3), 185-200.
Manavizadeh, N., Farrokhi-Asl, H., & WT Lim, S. F. (2020). A New Mathematical Model for the Green Vehicle Routing Problem by Considering a Bi-Fuel Mixed Vehicle Fleet. Journal of Optimization in Industrial Engineering, 13(2), 165-183.
Mancini, S. (2017). A combined multistart random constructive heuristic and set partitioning based formulation for the vehicle routing problem with time dependent travel times. Computers & Operations Research, 88, 290-296.
Mancini, S., Gansterer, M., & Hartl, R. F. (2021). The collaborative consistent vehicle routing problem with workload balance. European Journal of Operational Research, 293(3), 955-965.
Nolz, P. C., Absi, N., Feillet, D., & Seragiotto, C. (2022). The consistent electric-Vehicle routing problem with backhauls and charging management. European Journal of Operational Research, 302(2), 700-716.
Pan, B., Zhang, Z., & Lim, A. (2021). Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research, 291(1), 218-231.
Rincon-Garcia, N., Waterson, B., Cherrett, T. J., & Salazar-Arrieta, F. (2020). A metaheuristic for the time-dependent vehicle routing problem considering driving hours regulations–An application in city logistics. Transportation Research Part A: Policy and Practice, 137, 429-446.
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455-472.
Shahrabi, F., Nasiri, M. M., & Al-e, S. M. J. M. (2024). Vehicle routing problem with cross-docking in a sustainable supply chain for perishable products. journal of Optimization in Industrial Engineering, 17(2), 259-278.
Sharafi, A., & Bashiri, M. (2016). Green vehicle routing problem with safety and social concerns. Journal of Optimization in Industrial Engineering, 10(21), 93-100.
Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. Paper presented at the International conference on principles and practice of constraint programming.
Smilowitz, K., Nowak, M., & Jiang, T. (2013). Workforce management in periodic delivery operations. Transportation Science, 47(2), 214-230.
Soler, D., Albiach, J., & Martínez, E. (2009). A way to optimally solve a time-dependent vehicle routing problem with time windows. Operations Research Letters, 37(1), 37-42.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
Soysal, M., & Çimen, M. (2017). A simulation based restricted dynamic programming approach for the green time dependent vehicle routing problem. Computers & Operations Research, 88, 297-305.
Stavropoulou, F. (2022). The consistent vehicle routing problem with heterogeneous fleet. Computers & Operations Research, 140, 105644.
Stavropoulou, F., Repoussis, P. P., & Tarantilis, C. D. (2019). The vehicle routing problem with profits and consistency constraints. European Journal of Operational Research, 274(1), 340-356.
Subramanyam, A., & Gounaris, C. E. (2016). A branch-and-cut framework for the consistent traveling salesman problem. European Journal of Operational Research, 248(2), 384-395.
Subramanyam, A., & Gounaris, C. E. (2018). A decomposition algorithm for the consistent traveling salesman problem with vehicle idling. Transportation Science, 52(2), 386-401.
Sun, P., Veelenturf, L. P., Dabia, S., & Van Woensel, T. (2018). The time-dependent capacitated profitable tour problem with time windows and precedence constraints. European Journal of Operational Research, 264(3), 1058-1073.
Sun, P., Veelenturf, L. P., Hewitt, M., & Van Woensel, T. (2018). The time-dependent pickup and delivery problem with time windows. Transportation Research Part B: Methodological, 116, 1-24.
Sungur, I., Ren, Y., Ordóñez, F., Dessouky, M., & Zhong, H. (2010). A model and algorithm for the courier delivery problem with uncertainty. Transportation Science, 44(2), 193-205.
Tarantilis, C. D., Stavropoulou, F., & Repoussis, P. P. (2012). A template-based tabu search algorithm for the consistent vehicle routing problem. Expert Systems with Applications, 39(4), 4233-4239.
Ticha, H. B., Absi, N., Feillet, D., & Quilliot, A. (2017). Empirical analysis for the VRPTW with a multigraph representation for the road network. Computers & Operations Research, 88, 103-116.
Ulmer, M., Nowak, M., Mattfeld, D., & Kaminski, B. (2020). Binary driver-customer familiarity in service routing. European Journal of Operational Research, 286(2), 477-493.
Ulsrud, K. P., Vandvik, A. H., Ormevik, A. B., Fagerholt, K., & Meisel, F. (2022). A time-dependent vessel routing problem with speed optimization. European Journal of Operational Research, 303(2), 891-907.
Voigt, S. (2025). A review and ranking of operators in adaptive large neighborhood search for vehicle routing problems. European Journal of Operational Research, 322(2), 357-375.
Xiong, H., Xu, Y., Yan, H., Guo, H., & Zhang, C. (2024). Optimizing electric vehicle routing under traffic congestion: A comprehensive energy consumption model considering drivetrain losses. Computers & Operations Research, 168, 106710.
Xu, Z., & Cai, Y. (2018). Variable neighborhood search for consistent vehicle routing problem. Expert Systems with Applications, 113, 66-76.
Yu, X.-P., Hu, Y.-S., & Wu, P. (2024). The consistent vehicle routing problem considering driver equity and flexible route consistency. Computers & Industrial Engineering, 187, 109803.
Zhang, R., Guo, J., & Wang, J. (2020). A time-dependent electric vehicle routing problem with congestion tolls. IEEE Transactions on Engineering Management, 69(4), 861-873.
Zhang, T., Chaovalitwongse, W. A., & Zhang, Y. (2014). Integrated ant colony and tabu search approach for time dependent vehicle routing problems with simultaneous pickup and delivery. Journal of Combinatorial Optimization, 28, 288-309.
Zhao, J., Poon, M., Tan, V. Y., & Zhang, Z. (2024). A hybrid genetic search and dynamic programming-based split algorithm for the multi-trip time-dependent vehicle routing problem. European Journal of Operational Research, 317(3), 921-935.
Zhen, L., Lv, W., Wang, K., Ma, C., & Xu, Z. (2020). Consistent vehicle routing problem with simultaneous distribution and collection. Journal of the Operational Research Society, 71(5), 813-830.
Zhou, G., Li, D., Bian, J., & Zhang, Y. (2024). Two-echelon time-dependent vehicle routing problem with simultaneous pickup and delivery and satellite synchronization. Computers & Operations Research, 167, 106600.
