# Library

rss

Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
Filter
• 2020-2023  (14)
• 2021  (14)
Source
Years
Year
Language
• 1
Unknown
Publication Date: 2021-10-19
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 2
Unknown
Publication Date: 2022-02-01
Description: In this paper, we introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. The T-MDA is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. The resulting speedup is comparable to the speedup that the original A* algorithm achieves for Dijkstra's algorithm. Unlike other methods from the literature, which rely on special properties of the biobjective case, the T-MDA works for any dimension. To the best of our knowledge, it gives rise to the first efficient implementation that can deal with large scale instances with more than two objectives. A version tuned for the biobjective case, the T-BDA, outperforms state-of-the-art methods on almost every instance of a standard benchmark testbed that is not solvable in fractions of a second.
Language: English
Type: article , doc-type:article
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 3
Unknown
Publication Date: 2021-09-30
Description: In dieser Arbeit wird ein graphenbasiertes Modell zur Einbindung von Preissystemen des öffentlichen Nahverkehrs in Routing-Algorithmen vorgestellt. Jeder Knoten des Graphen repräsentiert einen abstrakten Preiszustand einer Route und ist an einen tatsächlichen Preis gekoppelt. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen möglich, diesich algorithmisch behandeln lassen. Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Ticketgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Dies ermöglicht die Berechnung von preisoptimalen Routen. An den Tarifsystemen der Verkehrsverbünde MDV (Mitteldeutscher Verkehrsverbund) und VBB (Verkehrsverbund Berlin-Brandenburg) wird die Konstruktion des Modells detailliert erläutert.
Language: German
Type: article , doc-type:article
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 4
Unknown
Publication Date: 2022-03-14
Description: We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes a minimum complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra’s algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm Multiobjective Dijkstra Algorithm (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins, which we improved using new data structures and pruning techniques. On average, the MDA is 2 to 9 times faster on all used graph types. On some instances the speedup reaches an order of magnitude.
Language: English
Type: article , doc-type:article
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 5
Unknown
Publication Date: 2022-03-14
Description: Deutsche Bahn (DB) operates a large fleet of rolling stock (locomotives, wagons, and train sets) that must be combined into trains to perform rolling stock rotations. This train composition is a special characteristic of railway operations that distinguishes rolling stock rotation planning from the vehicle scheduling problems prevalent in other industries. DB models train compositions using hyperarcs. The resulting hypergraph models are ad-dressed using a novel coarse-to-fine method that implements a hierarchical column genera-tion over three levels of detail. This algorithm is the mathematical core of DB’s fleet em-ployment optimization (FEO) system for rolling stock rotation planning. FEO’s impact within DB’s planning departments has been revolutionary. DB has used it to support the company’s procurements of its newest high-speed passenger train fleet and its intermodal cargo locomotive fleet for cross-border operations. FEO is the key to successful tendering in regional transport and to construction site management in daily operations. DB’s plan-ning departments appreciate FEO’s high-quality results, ability to reoptimize (quickly), and ease of use. Both employees and customers benefit from the increased regularity of operations. DB attributes annual savings of 74 million euro, an annual reduction of 34,000 tons of CO2 emissions, and the elimination of 600 coupling operations in cross-border operations to the implementation of FEO.
Language: English
Type: article , doc-type:article
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 6
Unknown
Publication Date: 2021-09-30
Description: We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 7
Unknown
Publication Date: 2021-08-03
Description: The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs. Our focus is on the solution of the pricing problem which turns out to be a variant of the NP-hard Maximum Weight Connected Subgraph Problem. We compare different formulations to handle connectivity, and find that a single-commodity flow formulation performs best. This is notable since the respective literature seems to have dismissed this formulation. We improve it to a new coarse-to-fine flow formulation that is theoretically and computationally superior, especially for large instances with many vertices of degree 2 like highway networks, where it provides a speed-up factor of 10 over the non-flow-based formulations. We also propose a preprocessing method that exploits a median property of weight constrained subgraphs, a primal heuristic, and a local search heuristic. In an extensive computational study we evaluate the presented connectivity formulations on different classes of instances, and demonstrate the effectiveness of the proposed enhancements. Their speed-ups essentially multiply to an overall factor of 20. Overall, our approach allows the reliabe solution of instances with several hundreds of nodes in a few minutes. These findings are further corroborated in a comparison to existing districting models on a set of test instances from the literature.
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 8
Unknown
Publication Date: 2021-09-16
Description: A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c −1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w_1, ..., w_k. In the 1970s Győri and Lovász showed that if G is k-connected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k 〉 4. Towards finding such a partition T_1, ..., T_k in k-connected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3-approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least w_i/3 or that each T_i has weight most 3w_i, respectively. Also, we present a both-side bounded version that produces a connected partition where each T_i has size at least w_i/3 and at most max({r, 3})w_i, where r ≥1 is the ratio between the largest and smallest value in w_1, ..., w_k. In particular for the balanced version, i.e. w_1 = w_2 = ... = w_k, this gives a partition with 1/3 w_i ≤ w(T_i) ≤ 3w_i.
Language: English
Type: conferenceobject , doc-type:conferenceObject
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 9
Unknown
Publication Date: 2022-03-14
Description: In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.
Language: English
Type: article , doc-type:article
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 10
Unknown
Publication Date: 2022-01-19
Description: We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes the minimal complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm \emph{Multiobjective Dijkstra Algorithm} (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins', which we improved using new data structures and pruning techniques. On average, the MDA is $\times2$ to $\times9$ times faster on all used graph types. On some instances the speedup reaches an order of magnitude.
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...