A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes
RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 5, pp. 1467-1494.

This paper studies a real-life container transportation problem with a wide planning horizon divided into multiple shifts. The trucks in this problem do not return to depot after every single shift but at the end of every two shifts. The mathematical model of the problem is first established, but it is unrealistic to solve this large scale problem with exact search methods. Thus, a Variable Neighbourhood Search algorithm with Reinforcement Learning (VNS-RLS) is thus developed. An urgency level-based insertion heuristic is proposed to construct the initial solution. Reinforcement learning is then used to guide the search in the local search improvement phase. Our study shows that the Sampling scheme in single solution-based algorithms does not significantly improve the solution quality but can greatly reduce the rate of infeasible solutions explored during the search. Compared to the exact search and the state-of-the-art algorithms, the proposed VNS-RLS produces promising results.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2019080
Classification : 90B06, 90B40, 90C27
Mots-clés : Periodic vehicle routing problem with time windows and open routes, adaptive operator selection, metaheuristics, variable neighbourhood search 
@article{RO_2020__54_5_1467_0,
     author = {Chen, Binhui and Qu, Rong and Bai, Ruibin and Laesanklang, Wasakorn},
     title = {A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1467--1494},
     publisher = {EDP-Sciences},
     volume = {54},
     number = {5},
     year = {2020},
     doi = {10.1051/ro/2019080},
     mrnumber = {4126312},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2019080/}
}
TY  - JOUR
AU  - Chen, Binhui
AU  - Qu, Rong
AU  - Bai, Ruibin
AU  - Laesanklang, Wasakorn
TI  - A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2020
SP  - 1467
EP  - 1494
VL  - 54
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2019080/
DO  - 10.1051/ro/2019080
LA  - en
ID  - RO_2020__54_5_1467_0
ER  - 
%0 Journal Article
%A Chen, Binhui
%A Qu, Rong
%A Bai, Ruibin
%A Laesanklang, Wasakorn
%T A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2020
%P 1467-1494
%V 54
%N 5
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2019080/
%R 10.1051/ro/2019080
%G en
%F RO_2020__54_5_1467_0
Chen, Binhui; Qu, Rong; Bai, Ruibin; Laesanklang, Wasakorn. A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 5, pp. 1467-1494. doi : 10.1051/ro/2019080. http://www.numdam.org/articles/10.1051/ro/2019080/

[1] R. Bai, N. Xue, J. Chen and G.W. Roberts, A set-covering model for a bidirectional multi-shift full truckload vehicle routing problem. Transp. Res. Part B: Methodol. 79 (2015) 134–148. | DOI

[2] B.M. Baker and M.A. Ayechew, A genetic algorithm for the vehicle routing problem. Comput. Oper. Res. 30 (2003) 787–800. | DOI | MR | Zbl

[3] J. Brandão, A tabu search algorithm for the open vehicle routing problem. Eur. J. Oper. Res. 157 (2004) 552–564. | DOI | MR | Zbl

[4] O. Bräysy and M. Gendreau, Metaheuristics for the vehicle routing problem with time windows. Report STF42 A1025 (2001).

[5] O. Bräysy and M. Gendreau, Vehicle routing problem with time windows, Part II: Metaheuristics. Transp. Sci. 39 (2005) 119–139. | DOI

[6] J. Brito, F.J. Martnez, J. Moreno and J.L. Verdegay, An aco hybrid metaheuristic for close–open vehicle routing problems with time windows and fuzzy constraints. Appl. Soft Comput. 32 (2015) 154–163. | DOI

[7] E.K. Burke, M. Gendreau, G. Ochoa and J.D. Walker, Adaptive iterated local search for cross-domain optimisation. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. ACM (2011) 1987–1994. | DOI

[8] J. Chen, R. Bai, R. Qu and G. Kendall, A task based approach for a real-world commodity routing problem. In: 2013 IEEE Workshop on Computational Intelligence in Production And Logistics Systems (CIPLS). IEEE (2013) 1–8.

[9] B. Chen, R. Qu, R. Bai and H. Ishibuchi, A variable neighbourhood search algorithm with compound neighbourhoods for VRPTW. In: Proceedings of the 5th International Conference on Operations Research and Enterprise Systems (ICORES 2016), Rome, Italy. SCITEPRESS (2016) 25–35. | DOI

[10] B. Chen, R. Qu and H. Ishibuchi, Variable-depth adaptive large meighbourhood search algorithm for open periodic vehicle routing problem with time windows. In: Proceedings of the International Conference on Harbor, Maritime and Multimodal Logistic Modelling and Simulation (HMS 2017), Barcelona, Spain (2017) 25–34.

[11] G. Clarke and J.W. Wright, Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12 (1964) 568–581. | DOI

[12] J.-F. Cordeau, G. Laporte and A. Mercier, A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52 (2001) 928–936. | DOI | Zbl

[13] J.-F. Cordeau, G. Laporte and A. Mercier, Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows. J. Oper. Res. Soc. 55 (2004) 542–546. | DOI | Zbl

[14] J.-F. Cordeau, G. Laporte, M.W. Savelsbergh and D. Vigo, Vehicle routing. Handbooks Oper. Res. Manage. Sci. 14 (2007) 367–428. | DOI

[15] A. Danandeh, M. Ghazanfari, R. Tavakoli-Moghaddam and M. Alinaghian, A swift heuristic algorithm based on capacitated clustering for the open periodic vehicle routing problem. In: Proceedings of the 9th WSEAS International Conference on Artificial intelligence, Knowledge Engineering and Data Bases, World Scientific and Engineering Academy and Society (WSEAS), Stevens Point, Wisconsin, USA (2010) 208–214.

[16] G.B. Dantzig and J.H. Ramser, The truck dispatching problem. Manage. Sci. 6 (1959) 80–91. | DOI | MR | Zbl

[17] G. Dueck, New optimization heuristics: the great deluge algorithm and the record-to-record travel. J. Comput. Phys. 104 (1993) 86–92. | DOI | Zbl

[18] B. Eksioglu, A.V. Vural and A. Reisman, The vehicle routing problem: a taxonomic review. Comput. Ind. Eng. 57 (2009) 1472–1483. | DOI

[19] G. Eppen and L. Schrage, Centralized ordering policies in a multi-warehouse system with lead times and random demand. Multi-Level Prod./Inventory Control Syst.: Theory Pract. In Vol. 16. North-Holland (1981) 51–67. | Zbl

[20] Z. Fu, R. Eglese and L.Y. Li, A new tabu search heuristic for the open vehicle routing problem. J. Oper. Res. Soc. 56 (2005) 267–274. | DOI | Zbl

[21] H. Gehring and J. Homberger, A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Proceedings of EUROGEN99. Citeseer (1999) 57–64.

[22] M. Gendreau, J.-Y. Potvin, O. Bräumlaysy, G. Hasle and A. Løkketangen, Metaheuristics for the vehicle routing problem and its extensions: a categorized bibliography. In: The Vehicle Routing Problem: Latest Advances and New Challenges. Springer, Boston, MA (2008) 143–169. | MR | Zbl

[23] B.E. Gillett and L.R. Miller, A heuristic algorithm for the vehicle-dispatch problem. Oper. Res. 22 (1974) 340–349. | DOI | Zbl

[24] B. Golden, A. Assad, L. Levy and F. Gheysens, The fleet size and mix vehicle routing problem. Comput. Oper. Res. 11 (1984) 49–66. | DOI | Zbl

[25] B.L. Golden, S. Raghavan and E.A. Wasil, The Vehicle Routing Problem: Latest Advances and New Challenges. In: Vol. 43. Springer Science & Business Media (2008). | MR | Zbl

[26] L. Guiyun, An improved ant colony algorithm for open vehicle routing problem with time windows. In: Vol. 2 of 2009 International Conference on Information Management, Innovation Management and Industrial Engineering. IEEE (2009) 616–619. | DOI

[27] L. Guiyun, Research on open vehicle routing problem with time windows based on improved genetic algorithm. In: International Conference on Computational Intelligence and Software Engineering, 2009. CiSE 2009. IEEE (2009) 1–5.

[28] P. Hansen, N. Mladenović and J.A.M. Pérez, Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175 (2010) 367–407. | DOI | MR | Zbl

[29] V.C. Hemmelmayr, K.F. Doerner and R.F. Hartl, A variable neighborhood search heuristic for periodic routing problems. Eur. J. Oper. Res. 195 (2009) 791–802. | DOI | Zbl

[30] V.C. Hemmelmayr, J.-F. Cordeau and T.G. Crainic, An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Comput. Oper. Res. 39 (2012) 3215–3228. | DOI | MR | Zbl

[31] G. Ioannou, M. Kritikos and G. Prastacos, A greedy look-ahead heuristic for the vehicle routing problem with time windows. J. Oper. Res. Soc. 52 (2001) 523–537. | DOI | Zbl

[32] Y. Jin, A comprehensive survey of fitness approximation in evolutionary computation. Soft Comput. Fusion Found. Methodol. App. 9 (2005) 3–12.

[33] N. Jozefowiez, F. Semet and E.-G. Talbi, Multi-objective vehicle routing problems. Eur. J. Oper. Res. 189 (2008) 293–309. | DOI | MR | Zbl

[34] T. Kaji and A. Ohuchi, A simulated annealing algorithm with the random compound move for the sequential partitioning problem of directed acyclic graphs. Eur. J. Oper. Res. 112 (1999) 147–157. | DOI | Zbl

[35] G. Laporte, M. Gendreau, J.-Y. Potvin and F. Semet, Classical and modern heuristics for the vehicle routing problem. Int. Trans. Oper. Res. 7 (2000) 285–300. | DOI | MR

[36] J.K. Lenstra and A. Kan, Complexity of vehicle routing and scheduling problems. Networks 11 (1981) 221–227. | DOI

[37] A.N. Letchford, J. Lysgaard and R.W. Eglese, A branch-and-cut algorithm for the capacitated open vehicle routing problem. J. Oper. Res. Soc. 58 (2007) 1642–1651. | DOI

[38] F. Li, B. Golden and E. Wasil, The open vehicle routing problem: algorithms, large-scale test problems, and computational results. Comput. Oper. Res. 34 (2007) 2918–2930. | DOI | Zbl

[39] S. Lin, Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44 (1965) 2245–2269. | DOI | MR | Zbl

[40] Q. Lin, Z. Liu, Q. Yan, Z. Du, C.A.C. Coello, Z. Liang, W. Wang and J. Chen, Adaptive composite operator selection and parameter control for multiobjective evolutionary algorithm. Inf. Sci. 339 (2016) 332–352. | DOI

[41] R. Liu and Z. Jiang, The close–open mixed vehicle routing problem. Eur. J. Oper. Res. 220 (2012) 349–360. | DOI | MR | Zbl

[42] T. Lourens, Using population-based incremental learning to optimize feasible distribution logistic solutions. Thesis, University of Stellenbosch, Stellenbosch (2005).

[43] G. Maps, Google maps. Accessed: 2018-05-11. https://www.google.co.uk/maps/@29.8715435,121.8372319,12z/data=!3m1!4b1!4m2!6m1!1s1IPQurvRAx3x96-V7XEUw6h9kmFs (2018).

[44] M. Mourgaya and F. Vanderbeck, Column generation based heuristic for tactical planning in multi-period vehicle routing. Eur. J. Oper. Res. 183 (2007) 1028–1041. | DOI | MR | Zbl

[45] I. Or, Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking. Xerox University Microfilms (1976).

[46] J. Park and B.-I. Kim, The school bus routing problem: a review. Eur. J. Oper. Res. 202 (2010) 311–319. | DOI | MR | Zbl

[47] A. Perwira Redi, M.F. Maghfiroh, V.F. Yu, An improved variable neighborhood search for the open vehicle routing problem with time windows. In: 2013 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE (2013) 1641–1645. | DOI

[48] S. Pirkwieser and G.R. Raidl, A variable neighborhood search for the periodic vehicle routing problem with time windows. In: Proceedings of the 9th EU/meeting on Metaheuristics for Logistics and Vehicle Routing, Troyes, France (2008) 23–24.

[49] D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems. Comput. Oper. Res. 34 (2007) 2403–2435. | DOI | MR | Zbl

[50] J.-Y. Potvin and J.-M. Rousseau, An exchange heuristic for routeing problems with time windows. J. Oper. Res. Soc. 46 (1995) 1433–1446. | DOI | Zbl

[51] J.-Y. Potvin, T. Kervahut, B.-L. Garcia and J.-M. Rousseau, The vehicle routing problem with time windows Part I: tabu search. INFORMS J. Comput. 8 (1996) 158–164. | DOI | Zbl

[52] A. Rahimi-Vahed, T. Gabriel Crainic, M. Gendreau and W. Rei, Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm. Comput. Oper. Res. 53 (2015) 9–23. | DOI | MR | Zbl

[53] P.P. Repoussis, C.D. Tarantilis andG. Ioannou, The open vehicle routing problem with time windows. J. Oper. Res. Soc. 58 (2007) 355–367. | DOI | Zbl

[54] S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp. Sci. 40 (2006) 455–472. | DOI

[55] S. Ropke and D. Pisinger, A unified heuristic for a large class of vehicle routing problems with backhauls. Eur. J. Oper. Res. 171 (2006) 750–775. | DOI | MR | Zbl

[56] M.W. Savelsbergh, The vehicle routing problem with time windows: minimizing route duration. ORSA J. Comput. 4 (1992) 146–154. | DOI | Zbl

[57] K. Schopka and H. Kopfer, An Adaptive Large Neighborhood Search for the Reverse Open Vehicle Routing Problem with Time Windows. Springer (2016) 243–257.

[58] J.E. Smith and T.C. Fogarty, Operator and parameter adaptation in genetic algorithms. Soft Comput. 1 (1997) 81–87. | DOI

[59] M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35 (1987) 254–265. | DOI | MR | Zbl

[60] J.A. Soria Alcaraz, G. Ochoa, M. Carpio and H. Puga, Evolvability metrics in adaptive operator selection. In: Proceedings of the 2014 Conference on Genetic and Evolutionary Computation. ACM (2014) 1327–1334. | DOI

[61] É. Taillard, P. Badeau, M. Gendreau, F. Guertin and J.-Y. Potvin, A tabu search heuristic for the vehicle routing problem with soft time windows. Transp. Sci. 31 (1997) 170–186. | DOI | Zbl

[62] C.D. Tarantilis, G. Ioannou, C.T. Kiranoudis and G.P. Prastacos, A threshold accepting approach to the open vehicle routing problem. RAIRO: OR 38 (2004) 345–360. | DOI | Numdam | MR | Zbl

[63] C.D. Tarantilis, G. Ioannou, C.T. Kiranoudis and G.P. Prastacos, Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm. J. Oper. Res. Soc. 56 (2005) 588–596. | DOI | Zbl

[64] M. Thathachar and P.S. Sastry, Varieties of learning automata: an overview. IEEE Trans. Syst. Man Cybern. Part B: Cybern. 32 (2002) 711–722. | DOI

[65] P.M. Thompson and J.B. Orlin, The theory of cyclic transfers (1989).

[66] D. Thierens, An adaptive pursuit strategy for allocating operator probabilities. In: Proceedings of the 7th Annual Conference on Genetic and evolutionary Computation. ACM (2005) 1539–1546.

[67] P. Toth and D. Vigo, The Vehicle Routing Problem. SIAM (2001). | MR

[68] N. Veerapen, J. Maturana and F. Saubion, An exploration-exploitation compromise-based adaptive operator selection for local search. In: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation. ACM (2012) 1277–1284.

[69] T. Vidal, T.G. Crainic, M. Gendreau and C. Prins, A unified solution framework for multi-attribute vehicle routing problems. Eur. J. Oper. Res. 234 (2014) 658–673. | DOI | MR | Zbl

[70] D. Vigo, A heuristic algorithm for the asymmetric capacitated vehicle routing problem. Eur. J. Oper. Res. 89 (1996) 108–126. | DOI | Zbl

[71] X. Wang and A.C. Regan, Local truckload pickup and delivery with hard time window constraints. Transp. Res. Part B: Methodol. 36 (2002) 97–112. | DOI

[72] N. Wieberneit, Service network design for freight transportation: a review. OR Spect. 30 (2008) 77–112. | DOI | MR | Zbl

[73] B. Yu and Z.Z. Yang, An ant colony optimization model: the period vehicle routing problem with time windows. Transp. Res. Part E: Logistics Transp. Rev. 47 (2011) 166–181. | DOI

[74] E.E. Zachariadis and C.T. Kiranoudis, An open vehicle routing problem metaheuristic for examining wide solution neighborhoods. Comput. Oper. Res. 37 (2010) 712–723. | DOI | Zbl

[75] R. Zhang, W.Y. Yun and H. Kopfer, Heuristic-based truck scheduling for inland container transportation. OR Spect. 32 (2010) 787–808. | DOI | Zbl

Cité par Sources :