Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers

Russell W. Bent () and Pascal Van Hentenryck ()
Additional contact information
Russell W. Bent: Department of Computer Science, Brown University, Box 1910, Providence, Rhode Island 02912
Pascal Van Hentenryck: Department of Computer Science, Brown University, Box 1910, Providence, Rhode Island 02912

Operations Research, 2004, vol. 52, issue 6, 977-987

Abstract: The multiple vehicle routing problem with time windows (VRPTW) is a hard and extensively studied combinatorial optimization problem. This paper considers a dynamic VRPTW with stochastic customers, where the goal is to maximize the number of serviced customers. It presents a multiple scenario approach (MSA) that continuously generates routing plans for scenarios including known and future requests. Decisions during execution use a distinguished plan chosen, at each decision, by a consensus function. The approach was evaluated on vehicle routing problems adapted from the Solomon benchmarks with a degree of dynamism varying between 30% and 80%. They indicate that MSA exhibits dramatic improvements over approaches not exploiting stochastic information, that the use of consensus function improves the quality of the solutions significantly, and that the benefits of MSA increase with the (effective) degree of dynamism.

Keywords: vehicle routing; stochastic model applications; sampling (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (114)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0124 (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:oropre:v:52:y:2004:i:6:p:977-987

Access Statistics for this article

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