This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Bent, R. W. Articles by Van Hentenryck, P. Search for Related Content

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

Department of Computer Science, Brown University, Box 1910, Providence, Rhode Island 02912
Department of Computer Science, Brown University, Box 1910, Providence, Rhode Island 02912
rbent{at}cs.brown.edu
pvh{at}cs.brown.edu

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.

Subject classifications: vehicle routing; stochastic model applications; sampling.
History: Received July 2002; revision received September 2002; revision received July 2003; accepted July 2003.

This article has been cited by other articles:

				D. Espinoza, R. Garcia, M. Goycoolea, G. L. Nemhauser, and M. W. P. Savelsbergh Per-Seat, On-Demand Air Transportation Part I: Problem Description and an Integer Multicommodity Flow Model Transportation Science, August 1, 2008; 42(3): 263 - 278. [Abstract] [PDF]

				M. A. Figliozzi, H. S. Mahmassani, and P. Jaillet Pricing in Dynamic Vehicle Routing Problems Transportation Science, August 1, 2007; 41(3): 302 - 318. [Abstract] [PDF]

				B. W. Thomas Waiting Strategies for Anticipating Service Requests from Known Customer Locations Transportation Science, August 1, 2007; 41(3): 319 - 331. [Abstract] [PDF]

				A. Lim and X. Zhang A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows INFORMS Journal on Computing, January 1, 2007; 19(3): 443 - 457. [Abstract] [PDF]

				L. M. Hvattum, A. Lokketangen, and G. Laporte Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic Transportation Science, November 1, 2006; 40(4): 421 - 438. [Abstract] [PDF]

				A. M. Campbell and M. Savelsbergh Incentive Schemes for Attended Home Delivery Services Transportation Science, August 1, 2006; 40(3): 327 - 341. [Abstract] [PDF]

				Z.-L. Chen and H. Xu Dynamic Column Generation for Dynamic Vehicle Routing with Time Windows Transportation Science, February 1, 2006; 40(1): 74 - 88. [Abstract] [PDF]