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.2015.111
URN: urn:nbn:de:0030-drops-54536
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5453/
Go to the corresponding OASIcs Volume Portal

Borndörfer, Ralf ; Reuther, Markus

Regional Search for the Resource Constrained Assignment Problem

pdf-format:
4.pdf (0.6 MB)

Abstract

The resource constrained assignment problem (RCAP) is to find a minimal cost partition of the nodes of a directed graph into cycles such that a resource constraint is fulfilled. The RCAP has its roots in rolling stock rotation optimization where a railway timetable has to be covered by rotations, i.e., cycles. In that context, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes variants of the vehicle routing problem (VRP). The paper contributes an exact branch and bound algorithm for the RCAP and, primarily, a straightforward algorithmic concept that we call regional search (RS). As a symbiosis of a local and a global search algorithm, the result of an RS is a local optimum for a combinatorial optimization problem. In addition, the local optimum must be globally optimal as well if an instance of a problem relaxation is computed. In order to present the idea for a standardized setup we introduce an RS for binary programs. But the proper contribution of the paper is an RS that turns the Hungarian method into a powerful heuristic for the resource constrained assignment problem by utilizing the exact branch and bound. We present computational results for RCAP instances from an industrial cooperation with Deutsche Bahn Fernverkehr AG as well as for VRP instances from the literature. The results show that our RS provides a solution quality of 1.4 % average gap w.r.t. the best known solutions of a large test set. In addition, our branch and bound algorithm can solve many RCAP instances to proven optimality, e.g., almost all asymmetric traveling salesman and capacitated vehicle routing problems that we consider.

BibTeX - Entry

@InProceedings{borndrfer_et_al:OASIcs:2015:5453,
  author =	{Ralf Bornd{\"o}rfer and Markus Reuther},
  title =	{{Regional Search for the Resource Constrained Assignment Problem}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{111--129},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Giuseppe F. Italiano and Marie Schmidt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5453},
  URN =		{urn:nbn:de:0030-drops-54536},
  doi =		{10.4230/OASIcs.ATMOS.2015.111},
  annote =	{Keywords: assignment problem, local search, branch and bound, rolling stock rota- tion problem, vehicle routing problem}
}

Keywords: assignment problem, local search, branch and bound, rolling stock rota- tion problem, vehicle routing problem
Collection: 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)
Issue Date: 2015
Date of publication: 14.09.2015

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