Bibliothek

feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
Filter
  • 2020-2023
  • 2015-2019  (15)
  • 2010-2014  (17)
  • 2019  (15)
  • 2014  (17)
Datenquelle
Erscheinungszeitraum
  • 2020-2023
  • 2015-2019  (15)
  • 2010-2014  (17)
Jahr
Sprache
  • 1
    Publikationsdatum: 2020-08-05
    Beschreibung: Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 2
    Publikationsdatum: 2020-08-05
    Sprache: Deutsch
    Materialart: article , doc-type:article
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 3
    Publikationsdatum: 2020-08-05
    Sprache: Deutsch
    Materialart: conferenceobject , doc-type:conferenceObject
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 4
    Publikationsdatum: 2020-08-05
    Beschreibung: In this paper, we consider the Cyclic Crew Rostering Problem with Fairness Requirements (CCRP-FR). In this problem, attractive cyclic rosters have to be constructed for groups of employees, considering multiple, a priori determined, fairness levels. The attractiveness follows from the structure of the rosters (e.g., sufficient rest times and variation in work), whereas fairness is based on the work allocation among the different roster groups. We propose a three-phase heuristic for the CCRP-FR, which combines the strength of column generation techniques with a large-scale neighborhood search algorithm. The design of the heuristic assures that good solutions for all fairness levels are obtained quickly, and can still be further improved if additional running time is available. We evaluate the performance of the algorithm using real-world data from Netherlands Railways, and show that the heuristic finds close to optimal solutions for many of the considered instances. In particular, we show that the heuristic is able to quickly find major improvements upon the current sequential practice: For most instances, the heuristic is able to increase the attractiveness by at least 20% in just a few minutes.
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 5
    Publikationsdatum: 2021-04-14
    Beschreibung: Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.
    Sprache: Englisch
    Materialart: article , doc-type:article
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 6
    Publikationsdatum: 2020-08-05
    Beschreibung: We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of edges to be controlled. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Format: application/pdf
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 7
    Publikationsdatum: 2020-08-05
    Beschreibung: Wir stellen einen mathematischen Optimierungsansatz zur integrierten Dienst- und Dienstreihenfolgeplanung im öffentlichen Nahverkehr vor, mit dem sich bei konstanten Personalkosten die Fahrerzufriedenheit deutlich steigern lässt.
    Sprache: Deutsch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 8
    facet.materialart.
    Unbekannt
    Publikationsdatum: 2020-08-05
    Beschreibung: Nach einem kurzen Abriss über die Bedeutung des Verkehrssektors als eine wichtige Schlüsseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik für Verkehr und Transport. Wir spekulieren dann über zukünftige Entwicklungen, insbesondere im Bereich des öffentlichen Personenverkehrs, und begründen, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bewältigt werden können. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. Überalterung in Europa oder dynamische Trends zu Megastädten in Entwicklungsländern, sich ändernde Lebens- und Produktionsverhältnisse, stark wachsender Bedarf nach Mobilität und enormes Anwachsen der Komplexität der Verkehrsplanung und -durchführung, machen einen verstärkten Zugriff auf mathematische Modellierung, Simulation und Optimierung notwendig. Diese Entwicklung stellt sowohl große Herausforderungen an die Mathematik, wo vielfach noch keine geeigneten Methoden vorhanden sind, als auch an die Praktiker im Bereich von Verkehr und Transport, die sich mit neuen Planungs- und Steuerungstechnologien befassen und diese effizient einsetzen müssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein.
    Sprache: Deutsch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 9
    Publikationsdatum: 2020-08-05
    Beschreibung: The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.
    Sprache: Englisch
    Materialart: conferenceobject , doc-type:conferenceObject
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 10
    Publikationsdatum: 2022-03-11
    Beschreibung: We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $2\sqrt{d}$ for partitioned hypergraphs with parts of size $\leq d$. Furthermore, we show that this bound cannot be improved to $\mathcal{O}(d^{0.5-\epsilon})$.
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...