Vehicle Routing with Space- and Time-Correlated Stochastic Travel Times: Evaluating the Objective Function

Abstract

We study how to model and handle correlated travel times in two-stage stochastic vehicle-routing problems. We allow these travel times to be correlated in time and space; that is, the travel time on one link in one period can be correlated to travel times on the same link in the next and previous periods as well as travel times on neighboring links (links sharing a node) in both the same and the following periods. Hence, we are handling a very high-dimensional dependent random vector. We discuss how such vehicle-routing problems should be modeled in time and space, how the random vector can be represented, and how scenarios (discretizations) can meaningfully be generated to be used in a stochastic program. We assume that the stochastic vehicle-routing problem is being solved by a search heuristic and focus on the objective function evaluation for any given solution. Numerical procedures are given and tested. As an example, our largest case has 142 nodes, 418 road links, and 60 time periods, leading to 25,080 dependent random variables. To achieve an objective function evaluation stability of 1%, we need only 15 scenarios for problem instances with 64 customer nodes and nine vehicles.