Integrated Scheduling and Routing in Logistics and Traffic

Rolf Möhring                                                                                                                         Technische Universität Berlin and Hefei University

See the media page for the video of the talk.

Traffic management and routing in logistic systems are important. One wants to utilize the available street or logistic network in such a way that the network “load” is minimized or the “throughput” is maximized. The aspects of “time” and “congestion” play a crucial role in these problems and require new techniques that need to integrate dynamic network flows and scheduling.

The lecture will illustrate this on two applications:

(1) Routing automated guided vehicles in container terminals (cooperation with HHLA).
(2) Ship traffic optimization on the Kiel Canal (cooperation with the German Federal     Waterways and Shipping Administration).

Both applications benefit from new insights into routing in graphs. In (1) it is a very fast real-time algorithm that avoids collisions, deadlocks, and other conflicts already at route computation, while (2) uses the routing algorithm of (1) for scheduling bidirectional ship traffic.

The scheduling problem arises from scarce resources (locations) at which large ships can only pass each other in opposing directions. It requires decisions on who should wait for whom (scheduling), in which siding to wait (packing) and when and how far to steer a ship between sidings (routing), and all this for online arriving ships at both sides of the canal.

We have developed a combinatorial algorithm that provides a unified view of routing and scheduling that combines simultaneous (global) and sequential (local) solution approaches to allocate scarce network resources to a stream of online arriving vehicles in a collision-free manner. Computational experiments on real traffic data with results obtained by human expert planners show that our algorithm improves upon manual planning by 25%.

The combination of routing and scheduling (without the packing) leads to a new class of scheduling problems dealing with scheduling bidirectional traffic on a path, and we will also address recent complexity and approximation results for this class.

The lecture is based on joint work with Elisabeth Lübbecke and Marco Lübbecke, see.