TY - GEN A1 - Borndörfer, Ralf A1 - Cardonha, Carlos T1 - A Binary Quadratic Programming Approach to the Vehicle Positioning Problem N2 - The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view. T3 - ZIB-Report - 09-12 KW - quadratic programming KW - integer programming KW - nonlinear programming KW - vehicle positioning Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11242 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Cardonha, Carlos T1 - A Binary Quadratic Programming Approach to the Vehicle Positioning Problem T2 - Modeling, Simulation and Optimization of Complex Processes -- Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009 N2 - The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view. Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-25707-0 SP - 41 EP - 52 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen T1 - A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit N2 - This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction. T3 - ZIB-Report - 04-14 KW - vehicle scheduling KW - crew scheduling KW - integrated scheduling KW - public transit KW - bundle method Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7898 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen ED - Hickman, Mark ED - Mirchandani, Pitu ED - Voß, Stefan T1 - A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit T2 - Computer-aided Systems in Public Transport Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2004/790/ VL - 600 SP - 3 EP - 24 PB - Springer-Verlag ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Case Study on Optimizing Toll Enforcements on Motorways T2 - 3rd Student Conference on Operational Research N2 - In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach. Y1 - 2012 U6 - https://doi.org/10.4230/OASIcs.SCOR.2012.1 VL - 22 SP - 1 EP - 10 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - A Case Study on Optimizing Toll Enforcements on Motorways N2 - In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach. T3 - ZIB-Report - 12-21 KW - Vehicle Routing Problem KW - Duty Rostering KW - Integer Programming KW - Operations Research Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15498 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem T2 - 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems. Y1 - 2014 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2014.79 VL - 42 SP - 79 EP - 91 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem N2 - We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems. T3 - ZIB-Report - 14-26 KW - column generation KW - coarse-to-fine approach KW - multi-layer approach KW - rolling stock rotation problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51009 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schelten, Uwe A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - A Column Generation Approach to Airline Crew Scheduling N2 - The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH. T3 - ZIB-Report - 05-37 KW - Integer Programming KW - Airline Crew Scheduling KW - Branch and Generate Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8713 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schelten, Uwe A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Haasis, Hans-Dietrich T1 - A Column Generation Approach to Airline Crew Scheduling T2 - Operations Research Proceedings 2005 Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2005/871/ SP - 343 EP - 348 PB - Springer-Verlag ER -