Optimization Online


Branch-and-Price for Probabilistic Vehicle Routing

Felipe Lagos(felipe.lagos***at***gatech.edu)
Mathias Klapp(maklapp***at***ing.puc.cl)
Alejandro Toriello(atoriello***at***isye.gatech.edu)

Abstract: The Vehicle Routing Problem with Probabilistic Customers (VRP-PC) is a fundamental building block within the broad family of a priori routing models and has two decision stages. In the first stage, the dispatcher determines a set of vehicle routes serving all potential customer locations before the actual requests for service realize. In the second stage, vehicles are dispatched after observing the subset of customers requiring service; a customer not requiring service is skipped from its planned route at execution. The objective is to minimize the expected vehicle travel cost assuming known customer realization probabilities. We propose a column generation framework to solve the VRP-PC to a given optimality tolerance; as with other branch-and-price VRP schemes, our framework can handle sequence-dependent constraints such as time windows. Specifically, we present two novel algorithms, one that under-approximates a solution's expected cost, and another that uses its exact expected cost. Each algorithm is equipped with a route pricing mechanism that iteratively improves the approximation precision of a route's reduced cost; this produces fast route insertions at the start of the algorithm and reaches termination conditions at the end of the execution. We provide a priori and a posteriori performance guarantees for these algorithms and test their performance on VRP-PC instances with time windows. Our results suggest that both algorithms can numerically optimize instances with up to 40 customers and realization probabilities of 0.5, 0.7 and 0.9.

Keywords: vehicle routing, probabilistic routing

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

Category 2: Integer Programming

Citation: Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, December 2017

Download: [PDF]

Entry Submitted: 12/05/2017
Entry Accepted: 12/06/2017
Entry Last Modified: 12/05/2017

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