Optimization Online


Exact Algorithms for the Chance-Constrained Vehicle Routing Problem

Thai Dinh (thaindinh***at***gmail.com)
Ricardo Fukasawa (rfukasawa***at***uwaterloo.ca)
James Luedtke (jim.luedtke***at***wisc.edu)

Abstract: We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for the VRP with stochastic demands require independent demands. We first study an edge-based formulation for the CCVRP, in particular addressing the challenge of how to determine a lower bound on the number of vehicles required to serve a subset of customers. We then investigate the use of a branch-and-cut-and-price (BCP) algorithm. While BCP algorithms have been considered the state of the art in solving the deterministic VRP, few attempts have been made to extend this framework to the VRP with stochastic demands. In contrast to the deterministic VRP, we find that the pricing problem for the CCVRP problem is strongly NP-hard, even when the routes being priced are allowed to have cycles. We therefore propose a further relaxation of the routes that enables pricing via dynamic programming. Numerical results indicate that the proposed methods can solve instances of CCVRP having up to 55 vertices.

Keywords: Vehicle routing, chance constraints, stochastic programming

Category 1: Stochastic Programming

Category 2: Integer Programming (0-1 Programming )

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


Download: [PDF]

Entry Submitted: 05/13/2016
Entry Accepted: 05/13/2016
Entry Last Modified: 05/19/2016

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