ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Publications Copernicus
Articles | Volume V-4-2021
ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci., V-4-2021, 61–68, 2021
ISPRS Ann. Photogramm. Remote Sens. Spatial Inf. Sci., V-4-2021, 61–68, 2021

  17 Jun 2021

17 Jun 2021


A. Le Guilcher1, S. Martel1, M. Brasebin1,2, and Y. Méneroux1 A. Le Guilcher et al.
  • 1LASTIG, Univ Gustave Eiffel, ENSG, IGN, F-94160 Saint-Mande, France
  • 2AGATE-Agence Alpine des Territoires, Chambéry, France

Keywords: Vehicle Routing, Stochastic Optimization, Uncertainty, Meta-heuristics, Disaster Preparedness

Abstract. In this paper, we describe a framework to find a good quality waste collection tour after a flood, without having to solve a complicated optimization problem from scratch in limited time. We model the computation of a waste collection tour as a capacitated routing problem, on the vertices or on the edges of a graph, with uncertain waste quantities and uncertain road availability. Multiple models have been conceived to manage uncertainty in routing problems, and we build on the ideas of discretizing the uncertain parameters and computing master solutions that can be adapted to propose an original method to compute efficient solutions. We first introduce our model for the progressive removal of the uncertainty, then outline our method to compute solutions: our method first considers a low-dimensional set of random variables that govern the behaviour of the problem parameters, discretizes these variables and computes a solution for each discrete point before the flood, and then uses these solutions as a basis to build operational solutions when there are enough information about the parameters of the routing problem. We then give computational tools to implement this method. We give a framework to compute the basis of solutions in an efficient way, by computing all the solutions simultaneously and sharing information (that can lead to good quality solutions) between the different problems based on how close their parameters are, and we also describe how real solutions can be derived from this basis. Our main contributions are our model for the progressive removal of uncertainty, our multi-step method to compute efficient solutions, and our intrusive framework to compute solutions on the discrete grid of parameters.