• Deutsch
Login

  • Home
  • Search
  • Browse
  • Publish
  • FAQ

Refine

Author

  • Tesch, Alexander (18)
  • Schlechte, Thomas (4)
  • Gilg, Brady (3)
  • Klug, Torsten (3)
  • Martienssen, Rosemarie (3)
  • Paat, Joseph (3)
  • Schulz, Christof (3)
  • Sagnol, Guillaume (2)
  • Schmidt genannt Waldschmidt, Daniel (2)
  • Seymen, Sinan (2)
+ more

Year of publication

  • 2020 (1)
  • 2018 (6)
  • 2017 (3)
  • 2016 (5)
  • 2015 (2)
  • 2013 (1)

Document Type

  • ZIB-Report (8)
  • In Proceedings (5)
  • Article (3)
  • Bachelor's Thesis (1)
  • Master's Thesis (1)

Language

  • English (17)
  • German (1)

Has Fulltext

  • yes (10)
  • no (8)

Is part of the Bibliography

  • no (17)
  • yes (1)

Keywords

  • Cumulative Scheduling (3)
  • Constraint Programming (2)
  • Energetic Reasoning (2)
  • Scheduling (2)
  • Approximation Algorithms (1)
  • Compact MIP (1)
  • Depot Planning (1)
  • Extensible Bin Packing (1)
  • Mixed-Integer Programming (1)
  • Propagation Algorithm (1)
+ more

Institute

  • Mathematical Optimization (18)
  • Mathematics of Health Care (2)
  • Mathematics of Transportation and Logistics (1)

18 search hits

  • 1 to 10
  • BibTeX
  • CSV
  • RIS
  • XML
  • 10
  • 20
  • 50
  • 100

Sort by

  • Year
  • Year
  • Title
  • Title
  • Author
  • Author
G-RIPS 2014 RailLab - Towards robust rolling stock rotations (2015)
Brett, Charles ; Hoberg, Rebecca ; Pacheco, Meritxell ; Smith, Kyle ; Borndörfer, Ralf ; Euler, Ricardo ; Gamrath, Gerwin ; Grimm, Boris ; Heismann, Olga ; Reuther, Markus ; Schlechte, Thomas ; Tesch, Alexander
The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an opportunity for high-achieving graduate-level students to work in teams on a real-world research project proposed by a sponsor from industry or the public sector. Each G-RIPS team consists of four international students (two from the US and two from European universities), an academic mentor, and an industrial sponsor. This is the report of the Rail-Lab project on the definition and integration of robustness aspects into optimizing rolling stock schedules. In general, there is a trade-off for complex systems between robustness and efficiency. The ambitious goal was to explore this trade-off by implementing numerical simulations and developing analytic models. In rolling stock planning a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects, have to be considered in an integrated model. General hypergraphs provide the modeling power to tackle those requirements. Furthermore, integer programming approaches are able to produce high quality solutions for the deterministic problem. When stochastic time delays are considered, the mathematical programming problem is much more complex and presents additional challenges. Thus, we started with a basic variant of the deterministic case, i.e., we are only considering hypergraphs representing vehicle composition and regularity. We transfered solution approaches for robust optimization from the airline industry to the setting of railways and attained a reasonable measure of robustness. Finally, we present and discuss different methods to optimize this robustness measure.
Conflict-free railway track assignment at depots (2018)
Gilg, Brady ; Klug, Torsten ; Martienssen, Rosemarie ; Paat, Joseph ; Schlechte, Thomas ; Schulz, Christof ; Seymen, Senan ; Tesch, Alexander
Managing rolling stock with no passengers aboard is a critical component of railway operations. One aspect of managing rolling stock is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with a fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we show that the TAP is NP-hard and present two integer programming models for solving the TAP. We compare both models on a theoretical level. Moreover, to our knowledge, we consider the first approach that integrates track lengths along with the three most common types of parking tracks FIFO, LIFO and FREE tracks in a common model. Furthermore, to optimize against uncertainty in the arrival times of the trains we extend our models by stochastic and robust modeling techniques. We conclude by giving computational results for both models, observing that they perform well on real timetables.
Compact MIP Models for the Resource-Constrained Project Scheduling Problem (2015)
Tesch, Alexander
In the Resource-Constrained Project Scheduling Problem (RCPSP) a set of jobs is planned subject to resource- and precedence constraints. The objective is to minimize the makespan, that is the time when all jobs have been completed. There exist several Mixed-Integer-Programming (MIP) models in order to solve the problem. Most common models are based on time-discretization. In this case, the scheduling horizon is split into unit size intervals and each job gets assigned a unique starting interval. The drawback of time-discrete models is the computational intractability for large scheduling horizons or fine discretizations. In this connection, this thesis deals with compact MIP models where the model size is independent of the scheduling horizon. In addition to two compact models from the literature, we present two new compact models. We investigate their induced polyhedra and deduce an inclusion hierarchy via linear transformations. Moreover, we give a combinatorial interpretation of these transformations. Furthermore, we study a class of valid cutting planes for the compact models, which are known as cover inequalities. In order to strengthen these cutting planes we introduce a lifting algorithm that is independent of the model size. Subsequently, we examine lower bounds for the RCPSP from linear programming. Based on a linear transformation, we reveal a connection between two approaches from the literature. For one model we generate strong cutting planes that are obtained from a primal-dual relation between the models. Two cutting plane algorithms are derived. Likewise, we show that similar cutting planes can be transferred to the compact MIP models. Our models have been implemented, tested and evaluated on the instances of the PSPLIB problem library.
Exact Energetic Reasoning in O(n^2 log^2 n) (2016)
Tesch, Alexander
In this paper, we address the Energetic Reasoning propagation rule for the Cumulative Scheduling Problem (CuSP). An energetic reasoning propagation algorithm is called exact, if it computes the maximum possible energetic reasoning propagation for all the jobs. The currently best known exact energetic reasoning algorithm has complexity O(n^3). In this paper, we present a new exact energetic reasoning propagation algorithm with improved complexity of O(n^2 \log^2 n).
Kompakte MIP Modelle für das Ressourcenbeschränkte Projektplanungsproblem (2016)
Tesch, Alexander
A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n) (2016)
Tesch, Alexander
In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule.
A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n) (2016)
Tesch, Alexander
In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule.
Improved Compact Models for the Resource-Constrained Project Scheduling Problem (2016)
Tesch, Alexander
In this article, we study compact Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP). Compared to the classical time-indexed formulation, the size of compact models is strongly polynomial in the number of jobs. In addition to two compact models from the literature, we propose a new compact model. We can show that all three compact models are equivalent by successive linear transformations. For their LP-relaxations, however, we state a full inclusion hierarchy where our new model dominates the previous models in terms of polyhedral strength. Moreover, we reveal a polyhedral relationship to the common time-indexed model. Furthermore, a general class of valid cutting planes for the compact models is introduced and finally all models are evaluated by computational experiments.
Conflict-Free Railway Track Assignment at Depots (2017)
Gilg, Brady ; Klug, Torsten ; Martienssen, Rosemarie ; Paat, Joseph ; Schlechte, Thomas ; Schulz, Christof ; Seymen, Sinan ; Tesch, Alexander
Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables.
Conflict-Free Railway Track Assignment at Depots (2017)
Gilg, Brady ; Klug, Torsten ; Martienssen, Rosemarie ; Paat, Joseph ; Schlechte, Thomas ; Schulz, Christof ; Seymen, Sinan ; Tesch, Alexander
Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables.
  • 1 to 10

OPUS4 Logo

  • Contact
  • Impressum und Datenschutz
  • Sitelinks