License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2013.137
URN: urn:nbn:de:0030-drops-42500
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4250/
Go to the corresponding OASIcs Volume Portal

Sarpong, Boadu Mensah ; Artigues, Christian ; Jozefowiez, Nicolas

Column Generation for Bi-Objective Vehicle Routing Problems with a Min-Max Objective

pdf-format:
12.pdf (0.5 MB)

Abstract

Column generation has been very useful in solving single objective
vehicle routing problems (VRPs). Its role in a branch-and-price algorithm is to compute a lower bound which is then used in a branch-and-bound framework to guide the search for integer solutions. In spite of the success of the method, only a few papers treat its application to multi-objective problems and this paper seeks to contribute in this respect. We study how good lower bounds
for bi-objective VRPs in which one objective is a min-max function can be computed by column generation. A way to model these problems as well as a strategy to effectively search for columns are presented. We apply the ideas to two VRPs and our results show that strong lower bounds for this class of problems can be obtained in "reasonable" times if columns are intelligently managed. Moreover, the quality of the bounds obtained from the proposed model
are significantly better than those obtained from the corresponding
"standard" approach.

BibTeX - Entry

@InProceedings{sarpong_et_al:OASIcs:2013:4250,
  author =	{Boadu Mensah Sarpong and Christian Artigues and Nicolas Jozefowiez},
  title =	{{Column Generation for Bi-Objective Vehicle Routing Problems with a Min-Max Objective}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{137--149},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Daniele Frigioni and Sebastian Stiller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4250},
  URN =		{urn:nbn:de:0030-drops-42500},
  doi =		{10.4230/OASIcs.ATMOS.2013.137},
  annote =	{Keywords: Multi-objective optimization, column generation, integer programming, vehicle routing}
}

Keywords: Multi-objective optimization, column generation, integer programming, vehicle routing
Collection: 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2013
Date of publication: 05.09.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI