# Library

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
• 2005-2009  (12)
• ddc:000  (12)
Source
Years
Year
Keywords
Language
• 1
Unknown
Publication Date: 2020-08-05
Description: We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 2
Publication Date: 2020-08-05
Description: Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional $\epsilon$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/pdf
Format: application/postscript
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 3
Unknown
Publication Date: 2020-12-15
Description: The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 4
Unknown
Publication Date: 2020-12-15
Description: The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/pdf
Format: application/postscript
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 5
Unknown
Publication Date: 2020-08-05
Description: This article is about the optimal track allocation problem (OPTRA) to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations: a standard formulation that models block conflicts in terms of packing constraints, and a new extended formulation that is based on additional configuration' variables. We show that the packing constraints in the standard formulation stem from an interval graph, and that they can be separated in polynomial time. It follows that the LP relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the extended formulation produces the same LP bound, and that it can also be computed with this model in polynomial time. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view, because it features a constant number of rows and is therefore amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hannover-Fulda-Kassel region of the German long distance railway network are reported.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 6
Unknown
Publication Date: 2020-12-15
Description: In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 7
Unknown
Publication Date: 2020-12-15
Description: Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question What is a good public transport network?.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 8
Unknown
Publication Date: 2020-03-09
Description: 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.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 9
Unknown
Publication Date: 2020-08-05
Description: The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 10
Unknown
Publication Date: 2020-08-05
Description: We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
Close ⊗