Models and Algorithms for Stochastic and Robust Vehicle Routing with Deadlines

Yossiri Adulyasak () and Patrick Jaillet ()
Additional contact information
Yossiri Adulyasak: HEC Montréal, Montréal, Québec H3T 2A7, Canada
Patrick Jaillet: Department of Electrical Engineering and Computer Science, Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Transportation Science, 2016, vol. 50, issue 2, 608-626

Abstract: We consider the vehicle routing problem with deadlines under travel time uncertainty in the contexts of stochastic and robust optimization. The problem is defined on a directed graph where a fleet of vehicles is required to visit a given set of nodes and deadlines are imposed at a subset of nodes. In the stochastic vehicle routing problem with deadlines (SVRP-D), the probability distribution of the travel times is assumed to be known and the problem is solved to minimize the sum of probability of deadline violations. In the robust vehicle routing problem with deadlines (RVRP-D), however, the exact probability distribution is unknown but it belongs to a certain family of distributions. The objective of the problem is to optimize a performance measure, called lateness index, which represents the risk of violating the deadlines. Although novel mathematical frameworks have been proposed to solve these problems, the size of the problem that those approaches can handle is relatively small. Our focus in this paper is the computational aspects of the two solution schemes. We introduce formulations that can be applied for the problems with multiple capacitated vehicles and discuss the extensions to the cases of incorporating service times and soft time windows. Furthermore, we develop an algorithm based on a branch-and-cut framework to solve the problems. The experiments show that these approaches provide substantial improvements in computational efficiency compared to the approaches in the literature. Finally, we provide a computational comparison to evaluate the solution quality of the SVRP-D and the RVRP-D. The results show that the RVRP-D produces solutions that are very competitive to those obtained by the SVRP-D with a large number of scenarios, whereas much less sensitive to the distributional uncertainty.

Keywords: vehicle routing; travel time uncertainty; stochastic programming; robust optimization; branch-and-cut (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (18)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0581 (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:ortrsc:v:50:y:2016:i:2:p:608-626

Access Statistics for this article

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