Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 3 von 5
Zurück zur Trefferliste

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.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Markus Reuther
Dokumentart:Konferenzbeitrag
Titel des übergeordneten Werkes (Englisch):14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Band:42
Erste Seite:62
Letzte Seite:78
Serie:OpenAccess Series in Informatics (OASIcs)
Jahr der Erstveröffentlichung:2014
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2014.62
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.