Optimization Online


Branch-and-Price for Routing with Probabilistic Customers

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 stochastic routing models, and has two decision stages. In the first stage, a dispatcher determines a set of vehicle routes serving all potential customer locations, before 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. 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. Compared to branch-and-cut algorithms for the VRP-PC using arc-based formulations, our framework can more readily incorporate sequence-dependent constraints. We provide a priori and a posteriori performance guarantees for these algorithms, and demonstrate their effectiveness via a computational study on instances with realization probabilities ranging from 0.5 to 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, May 2018

Download: [PDF]

Entry Submitted: 12/05/2017
Entry Accepted: 12/06/2017
Entry Last Modified: 03/28/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