{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T14:39:47Z","timestamp":1777559987405,"version":"3.51.4"},"reference-count":48,"publisher":"SAGE Publications","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIC"],"published-print":{"date-parts":[[2021,2,15]]},"abstract":"<jats:p>Nested Rollout Policy Adaptation (NRPA) is a Monte Carlo search algorithm that learns a playout policy in order to solve a single player game. In this paper we apply NRPA to the vehicle routing problem. This problem is important for large companies that have to manage a fleet of vehicles on a daily basis. Real problems are often too large to be solved exactly. The algorithm is applied to standard problem of the literature and to the specific problems of EDF (Electricit\u00e9 De France, the main French electric utility company). These specific problems have peculiar constraints. NRPA gives better result than the algorithm previously used by EDF.<\/jats:p>","DOI":"10.3233\/aic-201577","type":"journal-article","created":{"date-parts":[[2020,12,22]],"date-time":"2020-12-22T14:54:43Z","timestamp":1608648883000},"page":"21-35","source":"Crossref","is-referenced-by-count":7,"title":["Policy adaptation for vehicle routing"],"prefix":"10.1177","volume":"34","author":[{"given":"Tristan","family":"Cazenave","sequence":"first","affiliation":[{"name":"LAMSADE, Universit\u00e9 Paris-Dauphine, PSL, CNRS, France. E-mail:\u00a0Tristan.Cazenave@dauphine.psl.eu"}]},{"given":"Jean-Yves","family":"Lucas","sequence":"additional","affiliation":[{"name":"OSIRIS department, EDF Lab Paris-Saclay, Electricit\u00e9 de France, France. E-mails:\u00a0jean-yves.lucas@edf.fr,\u00a0thomas.triboulet@edf.fr,\u00a0hyoseok.kim@ensiie.fr"}]},{"given":"Thomas","family":"Triboulet","sequence":"additional","affiliation":[{"name":"OSIRIS department, EDF Lab Paris-Saclay, Electricit\u00e9 de France, France. E-mails:\u00a0jean-yves.lucas@edf.fr,\u00a0thomas.triboulet@edf.fr,\u00a0hyoseok.kim@ensiie.fr"}]},{"given":"Hyoseok","family":"Kim","sequence":"additional","affiliation":[{"name":"OSIRIS department, EDF Lab Paris-Saclay, Electricit\u00e9 de France, France. E-mails:\u00a0jean-yves.lucas@edf.fr,\u00a0thomas.triboulet@edf.fr,\u00a0hyoseok.kim@ensiie.fr"}]}],"member":"179","reference":[{"key":"10.3233\/AIC-201577_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/LCN.2016.050"},{"issue":"7","key":"10.3233\/AIC-201577_ref2","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1002\/net.3230190702","article-title":"A set-partitioning-based algorithm for the vehicle routing problem","volume":"19","author":"Agrawal","year":"1989","journal-title":"Networks"},{"key":"10.3233\/AIC-201577_ref3","doi-asserted-by":"publisher","first-page":"2296","DOI":"10.1016\/j.eswa.2011.08.009","article-title":"Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls","volume":"30","author":"Anbuudayasankar","year":"2012","journal-title":"Expert Systems and Applications"},{"issue":"3","key":"10.3233\/AIC-201577_ref4","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1016\/j.ejor.2009.06.034","article-title":"An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles","volume":"202","author":"Azi","year":"2010","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"10.3233\/AIC-201577_ref5","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1017\/S0269888913000118","article-title":"A review on agent-based technology for traffic and transportation","volume":"29","author":"Bazzan","year":"2014","journal-title":"The Knowledge Engineering Review"},{"key":"10.3233\/AIC-201577_ref6","unstructured":"J. Berger, M. Barkaoui and O. Br\u00e4ysy, A parallel hybrid genetic algorithm for the vehicle routing problem with time windows, in: Working Paper, Defense Research Establishment Valcartier, Canada, 2001."},{"key":"10.3233\/AIC-201577_ref7","doi-asserted-by":"crossref","unstructured":"B. Bouzy, Monte-Carlo fork search for cooperative path-finding, in: Computer Games - Workshop on Computer Games, CGW 2013, Held in Conjunction with the 23rd International Conference on Artificial Intelligence, IJCAI 2013, Revised Selected Papers. Vol. 3, Beijing, China, 2013, pp. 1\u201315.","DOI":"10.1007\/978-3-319-05428-5_1"},{"key":"10.3233\/AIC-201577_ref8","doi-asserted-by":"crossref","unstructured":"B. Bouzy, Burnt pancake problem: New lower bounds on the diameter and new experimental optimality ratios, in: Proceedings of the Ninth Annual Symposium on Combinatorial Search, SOCS 2016, Tarrytown, NY, USA, July 6\u20138, 2016, 2016, pp. 119\u2013120.","DOI":"10.1609\/socs.v7i1.18398"},{"issue":"1","key":"10.3233\/AIC-201577_ref9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TCIAIG.2012.2186810","article-title":"A survey of Monte Carlo tree search methods","volume":"4","author":"Browne","year":"2012","journal-title":"IEEE Transactions on Computational Intelligence and AI in Games"},{"key":"10.3233\/AIC-201577_ref10","doi-asserted-by":"crossref","unstructured":"T. Cazenave, Nested Monte-Carlo search, in: IJCAI, C. Boutilier, ed., 2009, pp. 456\u2013461.","DOI":"10.1109\/IPDPS.2009.5161122"},{"key":"10.3233\/AIC-201577_ref11","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.tcs.2016.06.024","article-title":"Playout policy adaptation with move features","volume":"644","author":"Cazenave","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"10.3233\/AIC-201577_ref12","doi-asserted-by":"crossref","unstructured":"T. Cazenave and T. Fournier, Monte Carlo Inverse Folding, in: Monte Search at IJCAI, 2020.","DOI":"10.1007\/978-3-030-89453-5"},{"key":"10.3233\/AIC-201577_ref13","unstructured":"T. Cazenave and N. Jouandeau, On the parallelization of UCT, in: Computer Games Workshop, 2007."},{"key":"10.3233\/AIC-201577_ref14","unstructured":"T. Cazenave, J. Lucas, H. Kim, T. Triboulet and M. Carlo, Vehicle routing, in: Eleventh International Workshop on Agents in Traffic and Transportation Co-Located with the 24th European Conference on Artificial Intelligence (ECAI 2020), Santiago de Compostela, Spain, September 4, 2020, I. Dusparic, F. Kl\u00fcgl, M. Lujak and G. Vizzari, eds, CEUR Workshop Proceedings, Vol. 2701, CEUR-WS.org, 2020, pp. 1\u20138."},{"key":"10.3233\/AIC-201577_ref15","doi-asserted-by":"crossref","unstructured":"T. Cazenave, B. Negrevergne and F. Sikora, Monte Carlo Graph Coloring, in: Monte Search at IJCAI, 2020.","DOI":"10.1007\/978-3-030-89453-5"},{"key":"10.3233\/AIC-201577_ref16","doi-asserted-by":"crossref","unstructured":"T. Cazenave, A. Saffidine, M.J. Schofield and M. Thielscher, Nested Monte Carlo search for two-player games, in: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, Arizona, USA, February 12\u201317, 2016, 2016, pp. 687\u2013693.","DOI":"10.1609\/aaai.v30i1.10073"},{"key":"10.3233\/AIC-201577_ref17","doi-asserted-by":"crossref","unstructured":"T. Cazenave, J.-B. Sevestre and M. Toulemont, Stabilized nested rollout policy adaptation, in: Monte Search at IJCAI, 2020.","DOI":"10.1007\/978-3-030-89453-5_2"},{"key":"10.3233\/AIC-201577_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34413-8_4"},{"key":"10.3233\/AIC-201577_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87608-3_6"},{"issue":"1","key":"10.3233\/AIC-201577_ref20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02601637","article-title":"Simulated annealing metaheuristics for the vehicle routing problem with time windows","volume":"13","author":"Chiang","year":"1996","journal-title":"Annals of Operations Research"},{"key":"10.3233\/AIC-201577_ref21","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1287\/opre.12.1.171","article-title":"Scheduling of vehicles from a central depot to a number of delivery points","volume":"12","author":"Clarke","year":"1964","journal-title":"Operations Research"},{"issue":"2","key":"10.3233\/AIC-201577_ref22","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1002\/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G","article-title":"A tabu search heuristic for the periodic and multi-depot vehicle routing problems","volume":"30","author":"Cordeau","year":"1997","journal-title":"Networks"},{"key":"10.3233\/AIC-201577_ref23","unstructured":"L. Crociani, G. L\u00e4mmel, G. Vizzari and S. Bandini, Learning obervables of a multi-scale simulation system of urban traffic, in: ATT@ IJCAI, 2018, pp. 40\u201348."},{"issue":"1","key":"10.3233\/AIC-201577_ref24","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The truck dispatching problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Management Science"},{"issue":"2","key":"10.3233\/AIC-201577_ref25","first-page":"147","article-title":"Finding differential paths in arx ciphers through nested Monte-Carlo search","volume":"64","author":"Dwivedi","year":"2018","journal-title":"International Journal of electronics and telecommunications"},{"key":"10.3233\/AIC-201577_ref26","doi-asserted-by":"publisher","DOI":"10.1109\/SCIS.2013.6613251"},{"key":"10.3233\/AIC-201577_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21266-1_28"},{"key":"10.3233\/AIC-201577_ref28","doi-asserted-by":"crossref","unstructured":"S. Edelkamp, M. Gath and M. Rohde, Monte-Carlo tree search for 3D packing with object orientation, in: KI 2014: Advances in Artificial Intelligence, Springer International Publishing, 2014, pp. 285\u2013296.","DOI":"10.1007\/978-3-319-11206-0_28"},{"key":"10.3233\/AIC-201577_ref29","doi-asserted-by":"crossref","unstructured":"S. Edelkamp and C. Greulich, Solving physical traveling salesman problems with policy adaptation, in: Computational Intelligence and Games (CIG), 2014 IEEE Conference on, IEEE, 2014, pp. 1\u20138.","DOI":"10.1109\/CIG.2014.6932882"},{"key":"10.3233\/AIC-201577_ref30","unstructured":"S. Edelkamp and Z. Tang, Monte-Carlo tree search for the multiple sequence alignment problem, in: Eighth Annual Symposium on Combinatorial Search, 2015."},{"issue":"2","key":"10.3233\/AIC-201577_ref31","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/net.3230110205","article-title":"A generalized assignment heuristic for vehicle routing","volume":"11","author":"Fisher","year":"1981","journal-title":"Networks"},{"key":"10.3233\/AIC-201577_ref32","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2016.06.029","article-title":"Adaptive playouts for online learning of policies during Monte Carlo tree search","volume":"644","author":"Graf","year":"2016","journal-title":"Theor. Comput. Sci."},{"issue":"12","key":"10.3233\/AIC-201577_ref33","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/j.ejor.2010.02.037","article-title":"A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows","volume":"206","author":"Gutierrez-Jarpa","year":"2010","journal-title":"European Journal of Operational Research"},{"key":"10.3233\/AIC-201577_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19369-4_60"},{"key":"10.3233\/AIC-201577_ref35","doi-asserted-by":"publisher","first-page":"1693","DOI":"10.1016\/j.asoc.2013.01.007","article-title":"Particle swarm optimization for the vehicle routing problem with stochastic demands","volume":"13","author":"Marinakis","year":"2013","journal-title":"Applied Soft Computing"},{"issue":"4","key":"10.3233\/AIC-201577_ref36","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1109\/TCIAIG.2010.2088123","article-title":"Combining UCT and nested Monte Carlo search for single-player general game playing","volume":"2","author":"M\u00e9hat","year":"2010","journal-title":"IEEE Transactions on Computational Intelligence and AI in Games"},{"issue":"2","key":"10.3233\/AIC-201577_ref39","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1287\/ijoc.8.2.165","article-title":"The vehicule routing problem with time windows part II: Genetic search","volume":"8","author":"Potvin","year":"1996","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"10.3233\/AIC-201577_ref40","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1287\/ijoc.8.2.158","article-title":"The vehicule routing problem with time windows part I: Tabu search","volume":"8","author":"Potvin","year":"1996","journal-title":"INFORMS Journal on Computing"},{"key":"10.3233\/AIC-201577_ref41","doi-asserted-by":"crossref","unstructured":"S.M. Poulding and R. Feldt, Generating structured test data with specific properties using nested Monte-Carlo search, in: Genetic and Evolutionary Computation Conference, GECCO \u201914, Vancouver, BC, Canada, July 12\u201316, 2014, 2014, pp. 1279\u20131286.","DOI":"10.1145\/2576768.2598339"},{"key":"10.3233\/AIC-201577_ref42","doi-asserted-by":"crossref","unstructured":"S.M. Poulding and R. Feldt, Heuristic model checking using a Monte-Carlo tree search algorithm, in: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, July 11\u201315, 2015, 2015, pp. 1359\u20131366.","DOI":"10.1145\/2739480.2754767"},{"key":"10.3233\/AIC-201577_ref43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20520-0_51"},{"key":"10.3233\/AIC-201577_ref44","doi-asserted-by":"crossref","unstructured":"Y. Rochat and E.D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, in: Journal of Heuristics, Vol. 1, 1995, pp. 147\u2013167.","DOI":"10.1007\/BF02430370"},{"key":"10.3233\/AIC-201577_ref45","unstructured":"C.D. Rosin, Nested rollout policy adaptation for Monte Carlo tree search, in: IJCAI, 2011, pp. 649\u2013654."},{"key":"10.3233\/AIC-201577_ref46","unstructured":"Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, in: Operations Research, 1985."},{"key":"10.3233\/AIC-201577_ref47","doi-asserted-by":"publisher","DOI":"10.1007\/s10852-009-9113-5"},{"key":"10.3233\/AIC-201577_ref48","doi-asserted-by":"crossref","unstructured":"E. Taillard, P. Badeau, M. Gendreau, F. Geurtin and J.Y. Potvin, A tabu search heuristic for the vehicle routing problem with time windows, in: Transportation Science, Vol. 31, 1997, pp. 170\u2013186.","DOI":"10.1287\/trsc.31.2.170"},{"key":"10.3233\/AIC-201577_ref49","doi-asserted-by":"crossref","unstructured":"S.R. Tangiah, K.E. Nygard and P.L. Juell, GIDEON: A genetic algorithm system for vehicule routing with time window, in: IEEE CAIA 1991 \u2013 Proceedings of the 7th IEEE Conference on Artificial Intelligence Applications, 24\u201328 February 1991, Miami Beach, Florida, USA, 1991, pp. 322\u2013328.","DOI":"10.1109\/CAIA.1991.120888"},{"key":"10.3233\/AIC-201577_ref50","doi-asserted-by":"crossref","unstructured":"N. Yuichi and B. Olli, A powerful route minimization heuristic for the vehicle routing problem with time windows, in: Operations Research Letters, Vol. 37, 2009, pp. 333\u2013338.","DOI":"10.1016\/j.orl.2009.04.006"}],"container-title":["AI Communications"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/AIC-201577","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T18:27:57Z","timestamp":1777400877000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.medra.org\/servlet\/aliasResolver?alias=iospress&doi=10.3233\/AIC-201577"}},"subtitle":[],"editor":[{"given":"Marin","family":"Lujak","sequence":"additional","affiliation":[]},{"given":"Ivana","family":"Dusparic","sequence":"additional","affiliation":[]},{"given":"Franziska","family":"Kl\u00fcgl","sequence":"additional","affiliation":[]},{"given":"Giuseppe","family":"Vizzari","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,2,15]]},"references-count":48,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.3233\/aic-201577","relation":{},"ISSN":["1875-8452","0921-7126"],"issn-type":[{"value":"1875-8452","type":"electronic"},{"value":"0921-7126","type":"print"}],"subject":[],"published":{"date-parts":[[2021,2,15]]}}}