no. 4
A model for the time dependent vehicle routing problem with time windows under traffic conditions with intelligent travel times
RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2203-2222

A new mixed-integer nonlinear programming model is presented for the time-dependent vehicle routing problem with time windows and intelligent travel times. The aim is to minimize fixed and variable costs, with the assumption that the travel time between any two nodes depends on traffic conditions and is considered to be a function of vehicle departure time. Depending on working hours, the route between any two nodes has a unique traffic parameter. We consider each working day to be divided into several equal and large intervals, termed as a time interval of traffic. Here, allowing for long distances between some of the nodes, travel time may take more than one time interval of traffic, resulting in resetting the time interval of traffic at the start of each large interval. This repetition of time interval of traffics has been used in modeling and calculating travel time. A tabu search optimization algorithm is devised for solving large problems. Also, after linearization, a number of random instances are generated and solved by the CPLEX solver of GAMS to assess the effectiveness of our proposed algorithm. Results indicate that the initial travel time is estimated appropriately and updated properly in accordance with to the repeating traffic conditions.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021098
Classification : 90Cxx
Keywords: Vehicle routing problem, time windows, traffic condition, time-dependent 
@article{RO_2021__55_4_2203_0,
     author = {Khanchehzarrin, Saeed and Shahmizad, Maral and Mahdavi, Iraj and Mahdavi-Amiri, Nezam and Ghasemi, Peiman},
     title = {A model for the time dependent vehicle routing problem with time windows under traffic conditions with intelligent travel times},
     journal = {RAIRO. Operations Research},
     pages = {2203--2222},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {4},
     doi = {10.1051/ro/2021098},
     mrnumber = {4292302},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021098/}
}
TY  - JOUR
AU  - Khanchehzarrin, Saeed
AU  - Shahmizad, Maral
AU  - Mahdavi, Iraj
AU  - Mahdavi-Amiri, Nezam
AU  - Ghasemi, Peiman
TI  - A model for the time dependent vehicle routing problem with time windows under traffic conditions with intelligent travel times
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 2203
EP  - 2222
VL  - 55
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021098/
DO  - 10.1051/ro/2021098
LA  - en
ID  - RO_2021__55_4_2203_0
ER  - 
%0 Journal Article
%A Khanchehzarrin, Saeed
%A Shahmizad, Maral
%A Mahdavi, Iraj
%A Mahdavi-Amiri, Nezam
%A Ghasemi, Peiman
%T A model for the time dependent vehicle routing problem with time windows under traffic conditions with intelligent travel times
%J RAIRO. Operations Research
%D 2021
%P 2203-2222
%V 55
%N 4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021098/
%R 10.1051/ro/2021098
%G en
%F RO_2021__55_4_2203_0
Khanchehzarrin, Saeed; Shahmizad, Maral; Mahdavi, Iraj; Mahdavi-Amiri, Nezam; Ghasemi, Peiman. A model for the time dependent vehicle routing problem with time windows under traffic conditions with intelligent travel times. RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2203-2222. doi: 10.1051/ro/2021098

[1] B. Afshar-Nadjafi and A. Afshar-Nadjafi, A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. J. King Saud Univ.-Eng. Sci. 29 (2017) 29–34.

[2] E. Avraham and T. Raviv, The data-driven time-dependent traveling salesperson problem. Transp. Res. Part B: Methodol. 134 (2020) 25–40. | DOI

[3] H. B. Ban, An efficient two-phase metaheuristic algorithm for The Time Dependent Traveling Salesman Problem. RAIRO:OR 53 (2019) 917–935. | MR | Zbl | Numdam | DOI

[4] J. E. Beasley, Adapting the savings algorithm for varying inter-customer travel times. Omega 9 (1981) 658–659. | DOI

[5] A. V. Donati, R. Montemanni, N. Casagrande, A. E. Rizzoli and L. M. Gambardella, Time dependent vehicle routing problem with a multi ant colony system. Eur. J Oper. Res. 185 (2008) 1174–1191. | MR | Zbl | DOI

[6] M. A. Figliozzi, The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transp. Res. Part E: Logistics Transp. Rev. 48 (2012) 616–636. | DOI

[7] M. Gmira, M. Gendreau, A. Lodi and J. Y. Potvin, Tabu search for the time-dependent vehicle routing problem with time windows on a road network. Eur. J. Oper. Res. 288 (2021) 129–140. | MR | DOI

[8] Y. Huang, L. Zhao, T. Van Woensel and J. P. Gross, Time-dependent vehicle routing problem with path flexibility. Transp. Res. Part B: Methodol. 95 (2017) 169–195. | DOI

[9] A. Karoonsoontawong, P. Punyim, W. Nueangnitnaraporn and V. Ratanavaraha, Multi-trip time-dependent vehicle routing problem with soft time windows and overtime constraints. Networks Spatial Econ. (2020) 1–50.

[10] M. Keskin, G. Laporte and B. Çatay, Electric vehicle routing problem with time-dependent waiting times at recharging stations. Comput. Oper. Res. 107 (2019) 77–94. | MR | DOI

[11] A. L. Kok, E. W. Hans and J. M. Schutten, Vehicle routing under time-dependent travel times: the impact of congestion avoidance. Comput. Oper. Res. 39 (2012) 910–918. | Zbl | DOI

[12] S. Kritzinger, K. F. Doerner, R. F. Hartl, G. Ÿ. Kiechle, H. Stadler and S. S. Manohar, Using traffic information for time-dependent vehicle routing. Proc.-Soc. Behav. Sci. 39 (2012) 217–229. | DOI

[13] D. S. Lai, O. C. Demirag and J. M. Leung, A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transp. Res. Part E: Logistics Transp. Rev. 86 (2016) 32–52. | DOI

[14] G. Lera-Romero, J. J. Miranda Bront and F. J. Soulignac, Linear edge costs and labeling algorithms: the case of the time-dependent vehicle routing problem with time windows. Networks 76 (2020) 24–53. | MR | DOI

[15] C. Liu, G. Kou, X. Zhou, Y. Peng, H. Sheng and F. E. Alsaadi, Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach. Knowl.-Based Syst. 188 (2020) 104813. | DOI

[16] S. Mancini, A combined multistart random constructive heuristic and set partitioning based formulation for the vehicle routing problem with time dependent travel times. Comput. Oper. Res. 88 (2017) 290–296. | MR | DOI

[17] M. Mourgaya and F. Vanderbeck, The periodic vehicle routing problem: classification and heuristic. RAIRO:OR 40 (2006) 169–194. | Zbl | Numdam | DOI

[18] P. K. Nguyen, T. G. Crainic and M. Toulouse, A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows. Eur. J. Oper. Res. 231 (2013) 43–56. | MR | DOI

[19] M. Okude and E. Taniguchi, Hierarchical traffic network for heuristic approximation method of vehicle routing problems. Proc.-Soc. Behav. Sci. 125 (2014) 262–274. | DOI

[20] J. Respen, N. Zufferey and J.-Y. Potvin, Impact of vehicle tracking on a routing problem with dynamic travel times. RAIRO:OR 53 (2019) 401–414. | MR | DOI

[21] N. R. Sabar, A. Bhaskar, E. Chung, A. Turky and A. Song, A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion. Swarm Evol. Comput. 44 (2019) 1018–1027. | DOI

[22] M. Setak, M. Habibi, H. Karimi and M. Abedzadeh, A time-dependent vehicle routing problem in multigraph with FIFO property. J. Manuf. Syst. 35 (2015) 37–45. | DOI

[23] H. Seyyedhasani and J. S. Dvorak, Using the Vehicle Routing Problem to reduce field completion times with multiple machines. Comput. Electron. Agric. 134 (2017) 142–150. | DOI

[24] M. Soysal and M. Çimen, A simulation based restricted dynamic programming approach for the green time dependent vehicle routing problem. Comput. Oper. Res. 88 (2017) 297–305. | MR | DOI

[25] R. Spliet, S. Dabia and T. Van Woensel, The time window assignment vehicle routing problem with time-dependent travel times. Transp. Sci. 52 (2018) 261–276. | DOI

[26] J. Sun and H. X. Liu, Stochastic eco-routing in a signalized traffic network. Transp. Res. Part C: Emerging Technol. 59 (2015) 32–47. | DOI

[27] Y. Sun, D. Wang, M. Lang and X. Zhou, Solving the time-dependent multi-trip vehicle routing problem with time windows and an improved travel speed model by a hybrid solution algorithm. Cluster Comput. 22 (2019) 15459–15470. | DOI

[28] C. Verbeeck, P. Vansteenwegen and E. H. Aghezzaf, Solving the stochastic time-dependent orienteering problem with time windows. Eur. J. Oper. Res. 255 (2016) 699–718. | MR | DOI

[29] J. F. Victoria, H. M. Afsar and Ch Prins, Column generation-based heuristic for the vehicle routing problem with time-dependent demand. IFAC Conf. Manuf. Modell. Manage. Control 49 (2016) 526–531.

[30] Z. Xu, A. Elomri, S. Pokharel and F. Mutlu, A model for capacitated green vehicle routing problem with the time-varying vehicle speed and soft time windows. Comput. Ind. Eng. 137 (2019) 106011. | DOI

[31] R. Zhang, J. Guo and J. Wang, A Time-dependent electric vehicle routing problem with congestion tolls. IEEE Trans. Eng. Manage. (2020).

[32] J. Zheng, A vehicle routing problem model with multiple fuzzy windows based on time-varying traffic flow. IEEE Access 8 (2020) 39439–39444. | DOI

Cité par Sources :