direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


1D Vehicle Scheduling with Conflicts
Zitatschlüssel Report-022-2010
Autor Gellert, Torsten J. and König, Felix G.
Jahr 2010
Nummer 022
Monat october
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Systems of rail-mounted vehicles play a key role in many logistics applications, and the efficiency of their operation frequently has a significant impact on the overall performance of the surrounding production environment. In theory, assigning transport requests to the vehicles of such systems and scheduling their execution amounts to finding $k$ tours on a common line, where tours may never cross each other in time–-dynamic collision constraints need to be respected. The goal is to minimize the makespan for a given set of transport requests. We establish a model capturing the core challenges in transport planning problems of this type and relate it to other models in literature. After proving $NP$-hardness for a basic version of the problem, the large part of the paper is dedicated to devising various fast heuristic algorithms suitable for practice. We present computational results regarding the performance of the algorithms proposed for several classes of problem instances.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag