|Duration:||June 2010 - May
heads:||Rolf H. Möhring |
Marco E. Lübbecke 
|Support:||DFG Research Center
"Mathematics for Key Technologies" (Matheon
Scheduling deals with allocating tasks to scarce resources over time whereas routing demands for decisions concerning space, typically in a network. In several optimization problems we see both aspects, like in the classical vehicle routing problem with time windows. Yet, so far the two concepts are treated rather separately than in a truly integrated way.
Material flows in logistics ask for an integrated approach. They involve the complex situation that the capacity or availability of resources changes over time and depends on the routing of the tasks or even of the resources themselves in a (logical or physical) network.
This project's goal is to combine scheduling theory and algorithms with the complicated resource and task dependencies which stem from routing decisions in networks, and which are present in various logistics applications. The work program to be accomplished comprises three major areas.
Scheduling theory has much to offer on resource capacities (also varying over time), sequence dependent setup cost, or e.g., flow shops. However, a theoretical notion of “inter-dependency” of resources and tasks through time and space is not known and shall be developed in this project. When clarifying the complexity status, a different interpretation of dependency is to consider network flows as performing the “movement of flow” by capacitated resources (machines) which move along the network themselves. The possibly conflicting machines can be considered as adversaries which brings us in the realm of games on networks.
Further interesting questions occur when thinking of the “degree of interdependency” between routing and scheduling. What is its influence on the optimization potential that may be gained by an integrated treatment? Can we characterize in which situations one of the two aspects is more influential? Will (modest) separation of the two aspects lead to approximation algorithms for the integrated problem?
Currently, it is not even clear how to accurately model a situation where the cost of a schedule can be evaluated only when the whole schedule is known by, say, an integer program. Even for combinatorial relaxations, models are far from being tractable, even with large-scale techniques like branch-and-price. In order to actually compute solutions we need to identify suitable relaxations or decomposition approaches. As a starting point we will consider resource constraint scheduling where the competition for scarce resources can be interpreted via a static conflicts graph. When we incorporate routing decisions for tasks over time, conflicts become dynamic, and a possible representation is given by dynamic conflict graphs. Identifying suitable parameters of this dynamics may be the key to good algorithms. Here we will use our expertise from B8 to obtain approximate solutions, e.g., with the help of condensed time-expanded (dynamic) conflicts graphs.
Not all practical situations bear the full complexity of integrated scheduling and flows. For theoretical and computational reasons it is important to study special cases, e.g., cases with a simple network topology or limited resource dependencies. One such case is the control of ship traffic through the Kiel canal (German: Nord-Ostsee-Kanal), which is considered the world`s busiest artificial waterway. Bi-directional ship traffic, in particular entering, passing, overtaking, safety distances, and waiting at turnouts, is precisely regulated, but the actual scheduling is done manually by experienced helmsmen. The Wasser- und Schifffahrtsamt Kiel-Holtenau will engage with us is a project to develop optimization algorithms for an improved traffic control and for an optimized design of the enlargement of the canal capacity scheduled for 2010--2012.
A more complex industrial application with PSI-BT involves the scheduling of several cranes in a steel yard in order to transport steel slabs between various locations. We see this problem as a prototype of integrated scheduling and routing. To solve this problem, we will also build on our computational work for Swiss Federal Railways where a first approach to flow conservation over time was developed.
Related applications, which all have their interpretation in our general setting, are railroad shunting problems, scheduling laser welding robots (C30), or the integration of line planning and timetabling in public transport (B15). We will revisit these (and the theoretical and algorithmic results obtained) when developing a unified view.
|Author||Lübbecke, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.|
|Abstract||We introduce, discuss, and solve a hard practical optimization problem which we call the ship traffic control problem (STCP). Since we plan bi-directional traffic, STCP relates to, and in fact generalizes train timetabling on single-track networks. The objective of finding quickest routes motivates the integration of recent algorithmic ideas from dynamic collision-free routing of automated guided vehicles. We offer a unified view of routing and scheduling which blends simultaneous (global) and sequential (local) solution approaches to allot scarce network resources to a fleet of vehicles in a collision-free manner. This leads us to construct a fast online heuristic. The STCP originates from the Kiel Canal which is the basis for the trade between the countries of the baltic area and the rest of the world. As traffic is projected to significantly increase, the canal is planned to be enlarged in a billion Euro project. Our work forms the mathematical and algorithmic basis for a tool to evaluate the different enlargement options. In view of computational experiments on real traffic data expert planners approved that our combinatorial algorithm is well-suited for this decision support. With the help of instance-dependent lower bounds we assess the quality of our solutions which significantly improves upon manual plans. We are confident that our ideas can be extended to other application areas like train timetabling and collision-free routing, also in more general networks.|
- Matheon B13: Optimization under Uncertainty in Logistics and Scheduling 
- Matheon B18: Applications of Network Flows in Evacuation Planning 
- Matheon B23: Robust Optimization for Network Applications 
- Matheon C30: Automatic reconfiguration of robotic welding cells 
- ZIB, KOSMOS - Optimal routing of rail freight traffic 
- Ship Traffic Optimization for the Kiel Canal
Wasser- und Schifffahrtsamt Kiel-Holtenau .
- Martin Luy, Algorithmen zum Scheduling von Schleusenvorgängen am Beispiel des Nord-Ostsee-Kanals, 2010.
- Robert Pankrath, Algorithmen für die Verkehrsflussoptimierung auf dem Nord-Ostsee-Kanal, 2010.
- Torsten Gellert, Steuerung von Kränen auf einer Schiene: Optimierung von 1-dimensionalen Transportsystemen, 2009.