@misc{BorndoerferReutherSchlechteetal.2011, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {A Hypergraph Model for Railway Vehicle Rotation Planning}, issn = {1438-0064}, doi = {/10.4230/OASIcs.ATMOS.2011.146}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-32746}, number = {11-36}, year = {2011}, abstract = {We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.}, language = {en} } @misc{Oleynikova2018, type = {Master Thesis}, author = {Oleynikova, Ekaterina}, title = {Mathematical optimization of joint order batching and picker routing problems}, pages = {60}, year = {2018}, abstract = {In this thesis we study order picking optimization problems for a two-blocks rectangle warehouse layout. We present combinatorial formulations and linear programming models based on the Steiner graph representation for order batching, picker routing, and joint order batching and picker routing problems. A special case of the latter is considered. This case assumes that each order contains exactly one item and each item can be picked from different possible locations in a warehouse. The underlying optimization problem is called joint multi-location order batching and picker routing problem (JMLOBPRP). Since having only one-item orders turns the JMLOBPRP into a special case of a capacitated vehicle routing problem, we suggest to implement algorithmic approaches for those to solve the JMLOBPRP. In particular, we define the JMLOBPRP as a generalization of the resource constrained assignment problem, for which a regional search method exists. The intention of the thesis is to investigate how a relaxation of the JMLOBPRP, a so-called group assignment problem (GrAP), can be solved following the ideas of regional search. We present a mathematical model of the GrAP and prove that it is NP-hard. Furthermore, we propose a novel heuristic algorithm for the GrAP. We call this method a network search algorithm, as it is based on a Lagrangian relaxation of the GrAP, which is solved by the network simplex method. On each its iteration network search examines a solution region suggested by the network simplex algorithm and improves the incumbent solution. Numerical experiments are conducted to assess a performance of the network search method. We create more realistic problem instances. The proposed algorithm is compared to the integer optimal solution of the GrAP and optimal fractional solution of its linear relaxation. Both computed using the commercial linear solver Gurobi. Our experiments show that the developed network search algorithm leads to the hight-quality solution within a short computing time. The results obtained testing large problem instances which cannot be solved by Gurobi within a reasonable computing time, show that the network search method provides a solution approach which can be used in practice.}, language = {en} } @misc{GrimmBorndoerferSchulzetal.2019, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schulz, Christof and Weider, Steffen}, title = {The Rolling Stock Rotation Planning Problem under Revenue Considerations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71339}, year = {2019}, abstract = {In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.}, language = {en} } @inproceedings{GrimmBorndoerferSchulzetal.2018, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schulz, Christof and Weider, Steffen}, title = {The Rolling Stock Rotation Planning Problem under Revenue Considerations}, booktitle = {Proceedings of the Rail Transport Demand Management Conference}, year = {2018}, abstract = {In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.}, language = {en} } @misc{BeckenbachHatzelWiederrecht2018, author = {Beckenbach, Isabel and Hatzel, Meike and Wiederrecht, Sebastian}, title = {The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71149}, year = {2018}, abstract = {The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lov{\´a}sz and Plummer developed a decomposition theory for graphs with perfect matchings and their corresponding polytopes known as the tight cut decomposition which breaks down every graph into a number of indecomposable graphs, so called bricks. For many properties that are of interest on graphs with perfect matchings, including the description of the perfect matching polytope, it suffices to consider these bricks. A key result by Lov{\´a}sz on the tight cut decomposition is that the list of bricks obtained is the same independent of the choice of tight cuts made during the tight cut decomposition procedure. This implies that finding a tight cut decomposition is polynomial time equivalent to finding a single tight cut. We generalise the notions of a tight cut, a tight cut contraction and a tight cut decomposition to hypergraphs. By providing an example, we show that the outcome of the tight cut decomposition on general hypergraphs is no longer unique. However, we are able to prove that the uniqueness of the tight cut decomposition is preserved on a slight generalisation of uniform hypergraphs. Moreover, we show how the tight cut decomposition leads to a decomposition of the perfect matching polytope of uniformable hypergraphs and that the recognition problem for tight cuts in uniformable hypergraphs is polynomial time solvable.}, language = {en} } @misc{BorndoerferEgererKarbsteinetal.2018, author = {Bornd{\"o}rfer, Ralf and Egerer, Ascan and Karbstein, Marika and Messerschmidt, Ralf and Perez, Marc and Pfisterer, Steven and Strauß, Petra}, title = {Kombil{\"o}sung: Optimierung des Liniennetzes in Karlsruhe}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69677}, year = {2018}, abstract = {Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombil{\"o}sung.}, language = {de} } @misc{GrimmBorndoerferOlthoff2020, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Olthoff, Mats}, title = {A Solution Approach to the Vehicle Routing Problem with Perishable Goods}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-77020}, year = {2020}, abstract = {This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date date, which may vary for different products. Storing products is prohibited. Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e., temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018.}, language = {en} } @inproceedings{GrimmBorndoerferOlthoff2019, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Olthoff, Mats}, title = {A Solution Approach to the Vehicle Routing Problem with Perishable Goods}, booktitle = {Operations Research 2019 Proceedings}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-77020}, year = {2019}, abstract = {This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date date, which may vary for different products. Storing products is prohibited. Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e., temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018.}, language = {en} } @misc{GrimmBorndoerferReutheretal.2020, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}, journal = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, issn = {1438-0064}, doi = {https://doi.org/10.4230/OASIcs.ATMOS.2019.1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75501}, year = {2020}, abstract = {For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see Maroti and Kroon 2005, or Cordeau et. al. 2001 for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in Bornd{\"o}rfer et. al. 2015. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of Reuther 2017 that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal.2019, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}, volume = {75}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, editor = {Cacchiani, Valentina and Marchetti-Spaccamela, Alberto}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2019.1}, pages = {1:1 -- 1:12}, year = {2019}, abstract = {For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Mar{\´o}ti and Kroon, 2005; G{\´a}bor Mar{\´o}ti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Bornd{\"o}rfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.}, language = {en} }