The probabilistic vehicle routing problem

It is quite surprising to find that the PVRP and the strategy of re-optimization are asymptotically equivalent in terms of performance.

Abstract

The probabilistic vehicle routing problem (PVRP) is a natural probabilistic variation of the classical vehicle routing problem (VRP), in which demands are probabilistic. The goal is to determine an a priori route of minimal expected total length, which corresponds to the expected total length of the route plus the expected value of the extra distance that might be required because demand on the route may occasionally exceed the capacity of the vehicle and force it to go back to the depot before continuing on its route. In this paper we analyze the PVRP using a variety of theoretical approaches. We find closedform expressions and algorithms to compute the expected length of an a priori route under various probabilistic assumptions. Based on these expressions we find upper and lower bounds for the PVRP and the VRP re-optimization strategy, in which we find the optimal route at every instance. We propose heuristics and analyze their worst-case performance. Moreover, we perform probabilistic analysis for the case that customer locations are random in the unit square and succeed in proving some sharp asymptotic theorems for the PVRP and the VRP re-optimization strategy, in which we find the optimal route at every instance. We further propose some asymptotically optimal algorithms. It is quite surprising to find that the PVRP and the strategy of re-optimization are asymptotically equivalent in terms of performance. Our results suggest that the PVRP is a strong and useful alternative to the strategy of re-optimization in capacitated routing problems. Key words:Probabilistic vehicle routing problem, re-optimization strategy, probabilistic analysis, worst-case analysis of heuristics. 2