Optimization Online


A Bucket Graph Based Labeling Algorithm with Application to Vehicle Routing

Ruslan Sadykov(ruslan.Sadykov***at***inria.fr)
Eduardo Uchoa(uchoa***at***producao.uff.br)
Artur Pessoa(artur***at***producao.uff.br)

Abstract: We consider the Resource Constrained Shortest Path problem arising as a subproblem in state-of-the-art Branch-Cut-and-Price algorithms for vehicle routing problems. We propose a variant of the bi-directional label correcting algorithm in which the labels are stored and extended according to so-called bucket graph. Such organization of labels helps to decrease significantly the number of dominance checks and the running time of the algorithm. We also show how the forward/backward route symmetry can be exploited and how to filter the bucket graph using reduced costs. The proposed algorithm can be especially beneficial for vehicle routing instances with large vehicle capacity and/or with time constraints. Computational experiments were performed on instances from the distance constrained vehicle routing problem, including multi-depot and site-depended variants, on the vehicle routing problem with time windows, and on the ``nightmare'' instances of the heterogeneous fleet vehicle routing problem. Very significant improvements over the best algorithms in the literature were achieved and many instances could be solved for the first time.

Keywords: Labeling Algorithm; Resource Constrained Shortest Path; Routing

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Category 3: Other Topics (Dynamic Programming )

Citation: @techreport{SadykovUchoaPessoa2017, Author = {Ruslan Sadykov and Eduardo Uchoa and Artur Pessoa}, Title = {Enhanced Branch-Cut-and-Price Algorithm for Heterogeneous Fleet Vehicle Routing Problems}, Institution = {Cadernos do LOGIS-UFF}, Address = {Niter{\'o}i, Brazil}, Number = {L-2017-7}, pages = {45}, month = {October}, Year = {2017} }

Download: [PDF]

Entry Submitted: 10/18/2017
Entry Accepted: 10/19/2017
Entry Last Modified: 10/18/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