Optimization Online


On the Stochastic Vehicle Routing Problem with time windows, correlated travel times, and time dependency

Federica Bomboi (fbomboi***at***unica.it)
Christoph Buchheim (christoph.buchheim***at***math.tu-dortmund.de)
Jonas Prünte (jonas.pruente***at***math.tu-dortmund.de)

Abstract: Most state-of-the-art algorithms for the Vehicle Routing Problem, such as Branch-and- Price algorithms or meta heuristics, rely on a fast feasibility test for a given route. We devise the fi rst approach to approximately check feasibility in the Stochastic Vehicle Routing Problem with time windows, where travel times are correlated and depend on the time of the day. Assuming jointly normally distributed travel times, we use a chance constraint approach to model feasibility, where two different application scenarios are considered, depending on whether missing a customer makes the rest of the route infeasible or not. In addition, we present an adaptive sampling algorithm that is tailored for our setting and is much faster than standard sampling techniques. We use a case study for both scenarios, based on realistic instances, to illustrate that taking correlations and time dependencies into account signi cantly improves the quality of the solutions, i.e., the precision of the feasibility decision. In particular, the nonconsideration of correlations often leads to solutions containing infeasible routes.

Keywords: Stochastic VRP, time windows, correlated travel times, dynamic travel times, chance constraints

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 05/16/2019
Entry Accepted: 05/16/2019
Entry Last Modified: 11/05/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society