 |
Winning Approach for the EURO-NeurIPS 2022 Dynamic Vehicle Routing Competition
1 : Centre dÉnseignement et de Recherche en Mathématiques et Calcul Scientifique
Ecole des Ponts ParisTech, Ecole des Ponts ParisTech : VincentLeclere
2 : Technische Universität München = Technical University of Munich
The EURO meets NeurIPS 2022 Vehicle Routing Competition (see https://euro-neurips-vrp-2022.challenges.ortec.com/) focuses on the usual static Capacitated Vehicle Routing Problem with Time Windows (VRPTW), as well as a dynamic variant which is the focus of this paper.
The objective of the dynamic VRPTW is to build routes for a fleet of capacitated vehicles, in order to serve all customer requests within their given time windows. The objective is to minimize the total travel time. However, requests are not known in advance: they arrive continuously during the day. Every hour, the decision maker chooses which requests to dispatch and builds routes to serve them. Each request must be served before the end of its time window. A request whose time window allows serving it during the next hour can be postponed. Once a route has been built, it cannot be modified.
The static VRPTW has been extensively studied in the literature, including exact approaches, as well as heuristic ones. This can be seen in the results of the challenge: the objective of the algorithm proposed by the 5th team on the static problem is 0.04% worse than the best solution found. The question of building an efficient heuristic for the dynamic problem remains far more open: the policy proposed by the 5th team is 4% worse than the best proposed.
Our main contribution is a policy for the dynamic VRPTW. It relies on a Deep Learning pipeline with a prize collecting VRPTW combinatorial optimization layer. It ranked first of the competition. This pipeline requires a subroutine for solving the prize collecting VRPTW, for which we introduce the prize collecting hybrid genetic search, a variant of the hybrid genetic search adapted for the prize collecting VRPTW. As a side contribution, we implemented an extension of the InferOpt.jl Julia library with a generic support for generalized combinatorial optimization oracles, and in particular for training our pipeline.
The static VRPTW has been extensively studied in the literature, including exact approaches, as well as heuristic ones. This can be seen in the results of the challenge: the objective of the algorithm proposed by the 5th team on the static problem is 0.04% worse than the best solution found. The question of building an efficient heuristic for the dynamic problem remains far more open: the policy proposed by the 5th team is 4% worse than the best proposed.
Our main contribution is a policy for the dynamic VRPTW. It relies on a Deep Learning pipeline with a prize collecting VRPTW combinatorial optimization layer. It ranked first of the competition. This pipeline requires a subroutine for solving the prize collecting VRPTW, for which we introduce the prize collecting hybrid genetic search, a variant of the hybrid genetic search adapted for the prize collecting VRPTW. As a side contribution, we implemented an extension of the InferOpt.jl Julia library with a generic support for generalized combinatorial optimization oracles, and in particular for training our pipeline.
