To main content

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.
Read publication

Category

Academic article

Client

  • Research Council of Norway (RCN) / 280536

Language

English

Author(s)

Affiliation

  • Sichuan University
  • Norwegian School of Economics
  • SINTEF Industry / Sustainable Energy Technology

Date

27.06.2019

Year

2019

Published in

INFORMS journal on computing

ISSN

1091-9856

Volume

31

Issue

4

Page(s)

654 - 670

View this publication at Cristin