We study a so-called static approach for the problem of routing vehicles conflict-free through a given street network. In fact, we assume that routes are computed without taking time-dependences into account
and collisions are avoided via a particular reservation procedure. In this context, the task is to cope with two arising problems: the appearance of congestion and detours on the one hand and the risk of deadlocks on the other.
We provide a two-stage routing approach for that problem. In the first phase we focus on balancing the load on the edges of the
given graph that models the underlying street network. Therefore, we consider the Online Load Balancing Problem with Bounded Stretch
Factor and give an optimal algorithm with respect to a specific performance ratio, the stretch factor restricted competitive ratio. Furthermore, in a second phase, we investigate the detection and avoidance of deadlock situations.
For the evaluation of the entire algorithm we consider the routing of Automated Guided Vehicles (AGVs) at HHLA Container Terminal
Altenwerder (CTA).
We study the fundamental problem of scheduling bidirectional traffic across machines arranged on a path. The main feature of the problem is that jobs traveling in the same direction can be scheduled in quick succession on a machine, while jobs in the other direction have to wait for an additional transit time. We show that this tradeoff makes the problem significantly harder than the related flow shop problem, by showing that it is NP-hard even for jobs with identical processing and transit times. We give polynomial algorithms for a single machine and any constant number of machines. In contrast, we show the problem to be NP-hard on a single machine and with identical processing and transit times if some pairs of jobs in different directions are allowed to run on the machine concurrently. We generalize a PTAS of Afrati et al. [1999] for one direction and a single machine to the bidirectional case on any constant number of machines.