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.2014.62
URN: urn:nbn:de:0030-drops-47538
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4753/
Go to the corresponding OASIcs Volume Portal

Reuther, Markus

Local Search for the Resource Constrained Assignment Problem

pdf-format:
p062-06-reuther.pdf (0.6 MB)

Abstract

The resource constrained assignment problem (RCAP) is to find a minimal cost cycle partition in a directed graph such that a resource constraint is fulfilled. The RCAP has its roots in an application that deals with the covering of a railway timetable by rolling stock vehicles. Here, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes several variants of vehicle routing problems. We contribute a local search algorithm for this problem that is derived from an exact algorithm which is similar to the Hungarian method for the standard assignment problem. Our algorithm can be summarized as a k-OPT heuristic, exchanging k arcs of an alternating cycle of the incumbent solution in each improvement step. The alternating cycles are found by dual arguments from linear programming. We present computational results for instances from our railway application at Deutsche Bahn Fernverkehr AG as well as for instances of the vehicle routing problem from the literature.

BibTeX - Entry

@InProceedings{reuther:OASIcs:2014:4753,
  author =	{Markus Reuther},
  title =	{{Local Search for the Resource Constrained Assignment Problem}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{62--78},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Stefan Funke and Mat{\'u}{\v{s}} Mihal{\'a}k},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4753},
  URN =		{urn:nbn:de:0030-drops-47538},
  doi =		{10.4230/OASIcs.ATMOS.2014.62},
  annote =	{Keywords: Assignment Problem, Local Search, Rolling Stock Rotation Problem, Vehicle Routing Problem}
}

Keywords: Assignment Problem, Local Search, Rolling Stock Rotation Problem, Vehicle Routing Problem
Collection: 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2014
Date of publication: 19.09.2014

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