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

Zhaoxia Guo (), Stein Wallace and Michal Kaut ()
Additional contact information
Zhaoxia Guo: Business School, Sichuan University, Chengdu 610065, China
Michal Kaut: SINTEF Technology and Society, 7031 Trondheim, Norway

INFORMS Journal on Computing, 2019, vol. 31, issue 4, 654-670

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.

Keywords: stochastic vehicle routing; correlated travel times; correlated random variables; scenario generation; objective function evaluation (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0906 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:4:p:654-670

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().