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.
