# Library

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

Proceed reservation?

Export
Filter
• Opus Repository ZIB  (46)
• 2005-2009  (46)
Source
Years
Year
Keywords
Language
• 1
Unknown
Publication Date: 2020-12-15
Description: This paper introduces the "line connectivity problem", a generalization of the Steiner tree problem and a special case of the line planning problem. We study its complexity and give an IP formulation in terms of an exponential number of constraints associated with "line cut constraints". These inequalities can be separated in polynomial time. We also generalize the Steiner partition inequalities.
Keywords: ddc:510
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
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 ...
• 3
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 ...
• 4
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 ...
• 5
Unknown
Publication Date: 2020-08-05
Keywords: ddc:510
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
Publication Date: 2020-08-05
Description: 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.
Keywords: ddc:510
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 ...
• 7
Unknown
Publication Date: 2020-08-05
Description: The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems.
Keywords: ddc:510
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-12-15
Language: English
Type: article , doc-type:article
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 9
Unknown
Publication Date: 2020-12-15
Language: English
Type: conferenceobject , doc-type:conferenceObject
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 10
Unknown
Publication Date: 2020-09-24
Language: English
Type: conferenceobject , doc-type:conferenceObject
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
Close ⊗