1 Search Results for "Jozefowiez, Nicolas"

Document
DOI: 10.4230/OASIcs.ATMOS.2013.137
Column Generation for Bi-Objective Vehicle Routing Problems with a Min-Max Objective

Authors: Boadu Mensah Sarpong, Christian Artigues, and Nicolas Jozefowiez

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

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.
Cite as

Boadu Mensah Sarpong, Christian Artigues, and Nicolas Jozefowiez. Column Generation for Bi-Objective Vehicle Routing Problems with a Min-Max Objective. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 137-149, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{sarpong_et_al:OASIcs.ATMOS.2013.137,
  author =	{Sarpong, Boadu Mensah and Artigues, Christian and Jozefowiez, Nicolas},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.137},
  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}
}
  • Refine by Author
  • 1 Artigues, Christian
  • 1 Jozefowiez, Nicolas
  • 1 Sarpong, Boadu Mensah

  • Refine by Classification

  • Refine by Keyword
  • 1 Multi-objective optimization
  • 1 column generation
  • 1 integer programming
  • 1 vehicle routing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact