Local Search for the Resource Constrained Assignment Problem

  • 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.

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Markus Reuther
Document Type:In Proceedings
Parent Title (English):14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Volume:42
First Page:62
Last Page:78
Series:OpenAccess Series in Informatics (OASIcs)
Year of first publication:2014
DOI:http://dx.doi.org/10.4230/OASIcs.ATMOS.2014.62

$Rev: 13581 $