Policy adaptation for vehicle routing

Issue title: Agents in Traffic and Transportation (ATT 2020)

Guest editors: Marin Lujak, Ivana Dusparic, Franziska Klügl and Giuseppe Vizzari

Article type: Research Article

Authors: Cazenave, Tristan^{a; *} | Lucas, Jean-Yves^b | Triboulet, Thomas^b | Kim, Hyoseok^b

Affiliations: [a] LAMSADE, Université Paris-Dauphine, PSL, CNRS, France. E-mail: [email protected] | [b] OSIRIS department, EDF Lab Paris-Saclay, Electricité de France, France. E-mails: [email protected], [email protected], [email protected]

Correspondence: [*] Corresponding author. E-mail: [email protected].

Abstract: 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é 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.

Keywords: Vehicle Routing Problems, Capacitated Vehicle Routing with Time Windows, Nested Rollout Policy Adaptation

DOI: 10.3233/AIC-201577

Journal: AI Communications, vol. 34, no. 1, pp. 21-35, 2021