Konrad-Zuse-Zentrum
|
Division Scientific Computing
Department Optimization |
| |
Transportation problems are not only historically one of the most prominent fields of application of the mathematical disciplines of optimization and operations research ([6,7]). Problems of this type confront us just today: The reform of the German railway system is as immediate as the deregulation of the air traffic in the European Union, where a similar deregulation will transform the public transportation sector as soon as 1999. Computerized planning and scheduling of logistic systems is needed -- based on mathematical optimization techniques!
Two important characteristics of transportation problems are their complexity and the on-line aspect. We illustrate these by means of two typical examples.
Example 1 is the operation of a public transportation company of a city: A huge optimization problem of line planning, timetabling, vehicle scheduling, duty scheduling, and duty rostering! Such complex questions can at present not be solved as a whole and one must resort to hierarchical planning in consecutive steps. And these subproblems are already at the limits of what one can accomplish today: The combination of sheer size with technical restrictions and complicated labour regulations results in challenging optimization problems.
Example 2 is the control of the material flow in a flexible manufacturing system. This problem displays another characteristic: Breakdowns, sudden generations and cancellations of tasks, and other unpredictable events result in permanent alterations of the system's status and these have to be dealt with in real time.
The aim of our projects in this area is to model transportation problems, to simulate them, and to develop mathematical methods for their solution. In the off-line case with complete data such as in public transportation this means to find optimal solutions or solutions with a proven quality in acceptable computation times. The situation is more complicated for on-line problems, where the evaluation of the solution quality itself is already a topic of research. We try to identify useful criteria by means of simulations and use them for the development of practicable methods. For on-line as well as for off-line problems, the indivisibility of resources and means of transportation leads to methods of integer programming.
We are currently working on the following projects. In the off-line area we investigate two problems in public transportation, vehicle scheduling and the subsequent duty scheduling, and the supplementary vehicle scheduling in handicapped people's transport. In the on-line area we pursue several projects about on-line optimization of automated transportation systems in flexible manufacturing systems.
Responsible: M. Grötschel, A. Löbel.
Cooperation: Berliner Verkehrsbetriebe, HanseCom GmbH (Hamburg), Gesellschaft für Informatik, Verkehrs- und Umweltplanung GmbH (Berlin)
Support: Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie.
Project Description:
Vehicle scheduling in public transportation is the task to service a given set of timetabled trips with a minimum number of vehicles. In addition to this primary objective that aims at low fixed costs for the vehicle fleet, one is also interested in minimizing operation costs. The vehicle scheduling problems of our cooperation partners, the public transportation companies of the cities of Berlin (BVG) and Hamburg (HHA and VHH), have enormous dimensions: Up to 14 garages with 10 different types of vehicles service more than 25,000 timetabled trips, and up to 70,000,000 possibilities to drive a vehicle in a legal way from the end of one trip to the start of the next!
These problems can nonetheless be solved to proven optimality (or close to optimality) with mathematical optimization techniques. We use an integer programming approach that is based on a multicommodity flow model. This model does neither restrict the feasibility space nor does it decompose the problem; it exploits, in contrast to many other vehicle scheduling approaches, all degrees of freedom. Our models lead to integer linear programs with up to 70,000,000 variables that we attack with novel Lagrange and LP techniques and special network flow algorithms.
The transfer of our algorithms into the products of our cooperation partners, the market leading software companies HanseCom GmbH and IVU GmbH, is in progress and has partly been completed. The Siemens AG has also acquired rights of sale. Test runs for the BVG, the HHA, and the VHH indicate substantial potential savings: The Berlin garage of Spandau alone can save 38 vehicles (19.5%) (these are official BVG numbers), for the HHA we have computed a possible reduction of 26 vehicles (3.1%) and 10% of the operation costs. For the VHH we could certify a very good quality of the current schedule: They already operate with the minimum number of vehicles, but we can save another 5.7% of operation costs.
Optimization methods for vehicles scheduling in public transportation are surveyed in [10], their application at the BVG is discussed in [18]. Mathematical methods for vehicle scheduling are described in the thesis [15], particular topics in [14,17] (LP techniques), [13] (Lagrange methods), and [16] (Dantzig-Wolfe decomposition).
Responsible: R. Borndörfer, A. Löbel, Steffen Weider.
Cooperation: HanseCom GmbH (Hamburg), Gesellschaft für Informatik, Verkehrs- und Umweltplanung GmbH (Berlin)
Support: Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie.
Project Description:
Duty scheduling in public transportation follows vehicle scheduling, and this new project investigates this next planning step. The vehicle schedule gives rise to a set of tasks (to drive a vehicle) that have to be combined into a set of daily duties such that the required staff is minimum. The duties must, of course, conform with all kinds of legal, contractual, social, and technical regulations. We estimate that the duty scheduling problems of our cooperation partners involve about 10,000 tasks per garage.
We do not expect that we can solve these complex and large scale problems to optimality, but we are confident that we can produce, in reasonable computation time, substantially better duty schedules than the methods that are used at present. Our approach is different from the methodology that we used for vehicle scheduling, although the problems seem to be similar at first glance. But duty scheduling involves additional constraints like break regulations, working times, etc. We deal with these by means of set partitioning and set covering models that lead to branch-and-price methods of integer programming, and we use combinatorial relaxations of the duty scheduling problem to derive lower bounds for an evaluation of the solution quality.
Our project is financed in equal parts by the BMB+F and our cooperation partners, the software companies HanseCom GmbH and IVU GmbH; the transfer of our algorithms into their software products is the main content of the respective cooperation contracts.
Responsible: R. Borndörfer, M. Grötschel.
Cooperation: Berliner Senatsverwaltung für Soziales; Berliner Zentralausschus für Soziale Aufgaben e.V. (BZA); Intranetz Gesellschaft für Informationslogistik mbH.
Support: Berliner Senatsverwaltung für Wissenschaft, Forschung und Kultur.
Project Description:
Vehicle scheduling in handicapped people's transport is a problem on the borderline between off-line and on-line optimization: The customers of a dial-a-ride system (financed by public funds) have to be transported with a fleet of mini-busses that are rented on a daily basis on demand. The specific needs of handicapped customers result in comparison to other dial-a-ride systems in a number of complications like the necessity of certain additional services etc., while the costs for vehicle renting are supposed to be minimized. Berlin's Telebus service for handicapped people, that is operated by our cooperation partner BZA, uses a fleet of about 100 mini-busses to service up to 2,000 requests per day. It goes without saying that the customers would like to order a Telebus on-line like a taxi, but this is not (or only to a very limited extent) possible at present.
For this reason, we are working on an off-line version of the vehicle scheduling problem that starts from a fixed set of requests and fits with the current operation of the BZA. Our mathematical approach uses a set partitioning model to deal with the complicated rules that govern the transportation of handicapped people. We develop a branch-and-cut algorithm that is based on polyhedral investigations. The Telebus problems, however, turn out to be harder than we had expected and we can at present not solve the corresponding integer programs to optimality. But we can compute suboptimal vehicle schedules that, together with other improvements, make it possible that Telebus can service today with exactly the same amount of money about 30% more requests than in 1992 when the project started.
There are two transfers of results from this project: Our Telebus optimization system is in use at the BZA since June 3, 1995, and two members of our research team have set up the software company Intranetz GmbH, that works together with our institute in the Telebus project.
Vehicle scheduling in handicapped people's transport is discussed in the articles [4,5], tour generation techniques are described in [12], mathematical methods are treated in [3,5,8,9].
Responsible: N. Ascheuer, M. Grötschel, J. Rambau.
Cooperation: Herlitz PBS AG (Berlin, Germany)
Support: Deutsche Forschungsgemeinschaft im Rahmen des Schwerpunktprogramms ``Echtzeit-Optimierung großer Systeme''.
Project Description:
The Herlitz PBS AG Berlin is the main manufacturing firm of office supplies in Germany. Their main distribution center contains 18 automated high-rise storage racks connected to order-picking areas. There is a constant influx of orders which have to be fulfilled within short time windows. Typically, a customer's request covers a wide product range. Since the diverse products are stored in several separate areas of the distribution center, an online optimization problem for the complete transportation system has to be solved. The online optimization of the transportation system in the whole distribution center is one of our future plans. At the moment, we are concentrating on two subproblems.
The first system we investigate is the warehouse where greeting cards are stored in an automated shelving system. In accordance with customers' orders the different greeting cards have to be collected in boxes to be shipped to the customers. Order pickers on eight automatic guided vehicles collect the orders from several automated storage systems while following a circular course. Each vehicle is able to handle a maximum of 19 orders. The vehicles are unable to pass one another which causes waiting times.
The online optimization problem consists of assigning the orders to the vehicles such that the time in which the daily orders are processed is minimized. Our first approach was to reduce the vehicles' congestion-time while minimizing the total number of stops the vehicles make to pick up orders.
We have implemented several primal heuristics which can be applied in online situations. Additionally, we have developed a simulation program modeling the Herlitz distribution center. Within this simulation model, we have compared the online behavior of the different heuristics. Furthermore, we evaluate the quality of the solutions by an a-posteriori analysis based on certain integer programming formulations. Up to 700 orders per day yield integer programs with several ten thousand rows and columns. Working on these programs with LP techniques, respecting the given precedence constraints for the orders plays an important role.
We found out that significant improvements in respect to the completion time of the orders can be achieved by applying our online heuristics. More important, the number of vehicles can be reduced to six or seven vehicles without any negative impact on the system. Further details can be found in [11].
The second focus of interest is the efficient management of the complete pallet transportation and warehousing system. The warehouses consists of high-rise pallet racks. Stacker cranes handle the storage and retrieval of the pallets. Roller conveyors and elevators connect the pallet racks to the different parts of the warehouse. The goal of the optimization is the availability of the pallets at the predetermined time. For the elevator systems and the automatic storage systems we have implemented details simulation models and developed first optimization approaches.
Through a project in cooperation with the Siemens-Nixdorf Informationssysteme AG, Augsburg, we have already gathered experience with the optimization of stacker crane movements. Within this project, we have developed an optimization program for minimizing the time a crane moves without payload [2]. Our investigations were concentrated on an online variation of the Asymmetric Traveling Salesman Problem.
![\begin{figure}[!ht]
\epsfig{file=Transport_Umlaufplanung_umlauf.ps,width=\textwidth}
\end{figure}](img12.gif)
![\begin{figure}[!ht]
\psfig{file=Transport_Dienstplanung_Dpl_udi.ps,width=\textwidth}
\end{figure}](img13.gif)