<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>10308</id>
    <completedYear/>
    <publishedYear>2026</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Eikonal Approach for Globally Optimal Free Flight Trajectories</title>
    <abstract language="eng">We present an eikonal-based approach that is capable of finding a continuous globally optimal trajectory for an aircraft in a stationary wind field. This minimizes emissions and fuel consumption. If the destination is close to a cut locus of the associated Hamilton-Jacobi-Bellman equation, small numerical discretization errors can lead to selecting a merely locally optimal trajectory and missing the globally optimal one. Based on finite element error estimates, we construct a trust region around the cut loci in order to guarantee uniqueness of trajectories for destinations sufficiently far from cut loci.</abstract>
    <identifier type="arxiv">2603.11830</identifier>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="SubmissionStatus">under review</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Martin Weiser</submitter>
    <author>Arturas Jocas</author>
    <author>Martin Weiser</author>
    <collection role="institutes" number="num">Numerical Mathematics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="institutes" number="MSoCP">Modeling and Simulation of Complex Processes</collection>
    <collection role="projects" number="MathPlus-AA3-3">MathPlus-AA3-3</collection>
    <collection role="persons" number="jocas">Jocas, Arturas</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>10072</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>415</pageFirst>
    <pageLast>421</pageLast>
    <pageNumber>7</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Springer Nature Switzerland</publisherName>
    <publisherPlace>Cham</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2025-07-23</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Non-linear Battery Behavior in Electric Vehicle Scheduling Problems</title>
    <abstract language="eng">The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2023. OR 2023.</parentTitle>
    <identifier type="doi">10.1007/978-3-031-58405-3_53</identifier>
    <identifier type="isbn">9783031584046</identifier>
    <identifier type="issn">2731-040X</identifier>
    <enrichment key="opus_doi_flag">true</enrichment>
    <enrichment key="opus_doi_json">{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T20:10:07Z","timestamp":1753215007653,"version":"3.41.2"},"publisher-location":"Cham","reference-count":11,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031584046","type":"print"},{"value":"9783031584053","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-58405-3_53","type":"book-chapter","created":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T19:39:59Z","timestamp":1753213199000},"page":"415-421","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-linear Battery Behavior in\u00a0Electric Vehicle Scheduling Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5433-184X","authenticated-orcid":false,"given":"Fabian","family":"L\u00f6bel","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7223-9174","authenticated-orcid":false,"given":"Ralf","family":"Bornd\u00f6rfer","sequence":"additional","affiliation":[]},{"given":"Steffen","family":"Weider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,23]]},"reference":[{"issue":"2","key":"53_CR1","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1016\/j.ejor.2022.06.050","volume":"306","author":"H Diefenbach","year":"2023","unstructured":"Diefenbach, H., Emde, S., &amp; Glock, C. H. (2023). Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models. European Journal of Operational Research, 306(2), 828\u2013848. https:\/\/doi.org\/10.1016\/j.ejor.2022.06.050","journal-title":"European Journal of Operational Research"},{"key":"53_CR2","doi-asserted-by":"publisher","unstructured":"Erdeli\u0107, T., &amp; Cari\u0107, T. (2019). A survey on the electric vehicle routing problem: variants and solution approaches. Journal of Advanced Transportation, 2019, 1\u201348 (2019). https:\/\/doi.org\/10.1155\/2019\/5075671","DOI":"10.1155\/2019\/5075671"},{"key":"53_CR3","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s12469-017-0164-0","volume":"9","author":"ME van Kooten Niekerk","year":"2017","unstructured":"van Kooten Niekerk, M. E., van den Akker, J. M., &amp; Hoogeveen, J. A. (2017). Scheduling electric vehicles. Public Transport, 9, 155\u2013176. https:\/\/doi.org\/10.1007\/s12469-017-0164-0","journal-title":"Public Transport"},{"issue":"7","key":"53_CR4","doi-asserted-by":"publisher","first-page":"1461","DOI":"10.1080\/01605682.2020.1730250","volume":"72","author":"C Lee","year":"2021","unstructured":"Lee, C. (2021). An exact algorithm for the electric-vehicle routing problem with nonlinear charging time. Journal of the Operational Research Society, 72(7), 1461\u20131485. https:\/\/doi.org\/10.1080\/01605682.2020.1730250","journal-title":"Journal of the Operational Research Society"},{"key":"53_CR5","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/j.trc.2019.05.009","volume":"104","author":"L Li","year":"2019","unstructured":"Li, L., Lo, H. K., &amp; Xiao, F. (2019). Mixed bus fleet scheduling under range and refueling constraints. Transportation Research Part C: Emerging Technologies, 104, 443\u2013462. https:\/\/doi.org\/10.1016\/j.trc.2019.05.009","journal-title":"Transportation Research Part C: Emerging Technologies"},{"key":"53_CR6","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.trb.2017.02.004","volume":"103","author":"A Montoya","year":"2017","unstructured":"Montoya, A., Gu\u00e9ret, C., Mendoza, J. E., &amp; Villegas, J. G. (2017). The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological, 103, 87\u2013110. https:\/\/doi.org\/10.1016\/j.trb.2017.02.004. , green Urban Transportation.","journal-title":"Transportation Research Part B: Methodological"},{"key":"53_CR7","doi-asserted-by":"publisher","unstructured":"Olsen, N., &amp; Kliewer, N. (2020). Scheduling electric buses in public transport: modeling of the charging process and analysis of assumptions. Logistics Research, 13(4). https:\/\/doi.org\/10.23773\/2020_4","DOI":"10.23773\/2020_4"},{"key":"53_CR8","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.trb.2017.01.020","volume":"103","author":"S Pelletier","year":"2017","unstructured":"Pelletier, S., Jabali, O., Laporte, G., &amp; Veneroni, M. (2017). Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models. Transportation Research Part B: Methodological, 103, 158\u2013187. https:\/\/doi.org\/10.1016\/j.trb.2017.01.020","journal-title":"Transportation Research Part B: Methodological"},{"key":"53_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.10.058","author":"SSG Perumal","year":"2022","unstructured":"Perumal, S. S. G., Lusby, R. M., &amp; Larsen, J. (2022). Electric bus planning &amp; scheduling: A review of related problems and methodologies. European Journal of Operational Research. https:\/\/doi.org\/10.1016\/j.ejor.2021.10.058","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"53_CR10","doi-asserted-by":"publisher","first-page":"527","DOI":"10.7307\/ptt.v33i4.3730","volume":"33","author":"A Zhang","year":"2021","unstructured":"Zhang, A., Li, T., Tu, R., Dong, C., Chen, H., Gao, J., &amp; Liu, Y. (2021). The effect of nonlinear charging function and line change constraints on electric bus scheduling. Promet - Traffic &amp; Transportation, 33(4), 527\u2013538. https:\/\/doi.org\/10.7307\/ptt.v33i4.3730","journal-title":"Promet - Traffic &amp; Transportation"},{"key":"53_CR11","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.trb.2022.03.002","volume":"159","author":"Y Zhou","year":"2022","unstructured":"Zhou, Y., Meng, Q., &amp; Ong, G. P. (2022). Electric bus charging scheduling for a single public transport route considering nonlinear charging profile and battery degradation effect. Transportation Research Part B: Methodological, 159, 49\u201375. https:\/\/doi.org\/10.1016\/j.trb.2022.03.002","journal-title":"Transportation Research Part B: Methodological"}],"container-title":["Lecture Notes in Operations Research","Operations Research Proceedings 2023"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-58405-3_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T19:39:59Z","timestamp":1753213199000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-58405-3_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031584046","9783031584053"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-58405-3_53","relation":{},"ISSN":["2731-040X","2731-0418"],"issn-type":[{"value":"2731-040X","type":"print"},{"value":"2731-0418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"23 July 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"OR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hamburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 August 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"or2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.or2023.uni-hamburg.de","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}</enrichment>
    <enrichment key="opus_crossrefLicence">https://www.springernature.com/gp/researchers/text-and-data-mining</enrichment>
    <enrichment key="opus_import_origin">crossref</enrichment>
    <enrichment key="opus_doiImportPopulated">PersonAuthorFirstName_1,PersonAuthorLastName_1,PersonAuthorIdentifierOrcid_1,PersonAuthorFirstName_2,PersonAuthorLastName_2,PersonAuthorIdentifierOrcid_2,PersonAuthorFirstName_3,PersonAuthorLastName_3,PublisherName,PublisherPlace,TitleMain_1,Language,TitleParent_1,PageNumber,PageFirst,PageLast,PublishedYear,IdentifierIsbn,IdentifierIssn,Enrichmentopus_crossrefLicence</enrichment>
    <enrichment key="ConferencePlace">Hamburg, Germany</enrichment>
    <enrichment key="ConferenceTitle">International Conference on Operations Research (OR 2023)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2023-11-02</enrichment>
    <enrichment key="opus.source">doi-import</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-92441</enrichment>
    <enrichment key="Series">Lecture Notes in Operations Research</enrichment>
    <author>Fabian Löbel</author>
    <editor>Guido Voigt</editor>
    <submitter>Fabian Löbel</submitter>
    <author>Ralf Borndörfer</author>
    <editor>Malte Fliedner</editor>
    <author>Steffen Weider</author>
    <editor>Knut Haase</editor>
    <editor>Wolfgang Brüggermann</editor>
    <editor>Kai Hoberg</editor>
    <editor>Joern Meissner</editor>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Electric Vehicle Scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Non-Linear Charging</value>
    </subject>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="persons" number="fabian.loebel">Löbel, Fabian</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="EBUS">EBUS</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9965</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst>21</pageFirst>
    <pageLast>34</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>5</volume>
    <type>incollection</type>
    <publisherName>Thieme</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Mathematische Optimierung in der OP-Planung</title>
    <abstract language="deu">Deutsche Krankenhäuser sehen sich derzeit mit enormen Schwierigkeiten konfrontiert. Ungefähr jede 2. Klinik muss drastische Sparmaßnahmen ergreifen, was auch die Allgemeinversorgung beeinträchtigt. Die Gründe dafür sind vielschichtig: stark gestiegene Sach- und Personalkosten bei gleicher Finanzierung, teilweiser Patientenrückgang, starke regionale Unterschiede in der Versorgung, Fachkräftemangel und fehlende Investitionen in Kern- und Zukunftsbereiche, insbesondere der Digitalisierung. Das belastet die Haushalte der Kliniken. Insbesondere die Digitalisierung und die Anwendung von Methoden der künstlichen Intelligenz und der mathematischen Optimierung könnten eine Schlüsselrolle spielen, um die komplexen Krankenhausprozesse mit Kennzahlen qualitativ zu bewerten und zu verbessern. In diesem Artikel stellen wir vier Praxisprobleme aus der OP-Planung vor und benennen welche Entscheidungen, Nebenbedingungen und Zielkriterien mit mathematischen Entscheidungsmodellen dargestellt und optimiert werden können. Hierzu erläutern wir das erweiterte Potenzial einer umfassenden Anwendung von mathematischer Optimierung im OP-Bereich.</abstract>
    <parentTitle language="deu">OP-Management up2date</parentTitle>
    <identifier type="doi">10.1055/a-2322-2124</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">10.03.2025</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Alexander Tesch</author>
    <submitter>Alexander Tesch</submitter>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="BMBF-IBOSS">BMBF-IBOSS</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
  </doc>
  <doc>
    <id>9939</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Logic-Constrained Shortest Paths for Flight Planning</title>
    <abstract language="eng">The Logic-Constrained Shortest Path Problem (LCSP) combines a one-to-one shortest path problem with satisfiability constraints imposed on the routing graph. This setting arises in flight planning, where air traffic control (ATC) authorities are enforcing a set of traffic flow restrictions (TFRs) on aircraft routes in order to increase safety and throughput. We propose a new branch and bound-based algorithm for the LCSP. The resulting algorithm has three main degrees of freedom: the node selection rule, the branching rule and the conflict. While node selection and branching rules have been long studied in the MIP and SAT communities, most of them cannot be applied out of the box for the LCSP. We review the existing literature and develop tailored variants of the most prominent rules. The conflict, the set of variables to which the branching rule is applied, is unique to the LCSP. We analyze its theoretical impact on the B&amp;B algorithm. In the second part of the paper, we show how to model the Flight Planning Problem with TFRs as an LCSP and solve it using the branch and bound algorithm. We demonstrate the algorithm’s efficiency on a dataset consisting of a global flight graph and a set of around 20000 real TFRs obtained from our industry partner Lufthansa Systems GmbH. We make this dataset publicly available. Finally, we conduct an empirical in-depth analysis of node selection rules, branching rules and conflicts. Carefully choosing an appropriate combination yields an improvement of an order of magnitude compared to an uninformed choice.</abstract>
    <identifier type="arxiv">2412.13235</identifier>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="SubmissionStatus">under review</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ricardo Euler</author>
    <submitter>Ricardo Euler</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>9797</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>other</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-07-19</completedDate>
    <publishedDate>2024-07-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Electric Bus Scheduling with Non-Linear Charging, Power Grid Bottlenecks, and Dynamic Recharge Rates</title>
    <abstract language="eng">Public transport operators are gradually electrifying their bus fleets, predominantly with battery-powered drive trains. These buses commonly have to be scheduled to recharge in-service, which gives rise to a number of challenges. A major problem is that the relationship between charging time and replenished driving range is non-linear, which is often approximately modeled. We examine the associated approximation error and show how it can result in a gross over- or underestimation of the fleet size. Moreover, we demonstrate that commonly used piecewise linear underestimations of the charge curve do not result in an underestimation of the predicted charge states in electric vehicle scheduling and routing models.&#13;
Furthermore, since power grid upgrades are currently not keeping up with an ever growing electricity demand, operators are introducing active charge management tools to dynamically adjust the charging speed depending on the amount of available energy. It is therefore imperative to extend electric bus scheduling models to account for these developments.&#13;
We propose a novel mixed-integer programming formulation for the electric bus scheduling problem featuring an improved approximation of the non-linear battery charging behavior as well as dynamic recharge speeds to accommodate grid load limits. The idea is to linearly interpolate what we call the charge increment function, which is closely related to the derivative of the commonly used charge curve. This provides very good error control and integrates easily into integer programming models. We demonstrate the practical usefulness of our model on a diverse library of real-life instances.</abstract>
    <identifier type="arxiv">2407.14446</identifier>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="SubmissionStatus">under review</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Fabian Löbel</author>
    <submitter>Fabian Löbel</submitter>
    <author>Ralf Borndörfer</author>
    <author>Steffen Weider</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="persons" number="fabian.loebel">Löbel, Fabian</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="EBUS">EBUS</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9795</id>
    <completedYear>2024</completedYear>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>11:1</pageFirst>
    <pageLast>11:16</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>123</volume>
    <type>conferenceobject</type>
    <publisherName>Schloss Dagstuhl -- Leibniz-Zentrum für Informatik</publisherName>
    <publisherPlace>Dagstuhl, Germany</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-10-07</completedDate>
    <publishedDate>2024-10-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach</title>
    <abstract language="eng">Attractive and cost-efficient public transport requires solving computationally difficult optimization problems from network design to crew rostering. While great progress has been made in many areas, new requirements to handle increasingly complex constraints are constantly coming up. One such challenge is a new type of resource constraints that are used to deal with the state-of-charge of battery-electric vehicles, which have limited driving ranges and need to be recharged in-service. Resource constrained vehicle scheduling problems can classically be modelled in terms of either a resource constrained (multi-commodity) flow problem or in terms of a path-based set partition problem. We demonstrate how a novel integrated version of both formulations can be leveraged to solve resource constrained vehicle scheduling with replenishment in general and the electric bus scheduling problem in particular by Lagrangian relaxation and the proximal bundle method.</abstract>
    <parentTitle language="eng">24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2024.11</identifier>
    <identifier type="urn">urn:nbn:de:0030-drops-211992</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2024-08-07</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <submitter>Fabian Löbel</submitter>
    <author>Ralf Borndörfer</author>
    <author>Andreas Löbel</author>
    <author>Fabian Löbel</author>
    <author>Steffen Weider</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="loebel">Löbel, Andreas</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="persons" number="fabian.loebel">Löbel, Fabian</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="EBUS">EBUS</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9773</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>13:1</pageFirst>
    <pageLast>13:19</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>123</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-10-07</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Bayesian Rolling Horizon Approach for Rolling Stock Rotation Planning with Predictive Maintenance</title>
    <abstract language="eng">We consider the rolling stock rotation planning problem with predictive maintenance (RSRP-PdM), where a timetable given by a set of trips must be operated by a fleet of vehicles. Here, the health states of the vehicles are assumed to be random variables, and their maintenance schedule should be planned based on their predicted failure probabilities. Utilizing the Bayesian update step of the Kalman filter, we develop a rolling horizon approach for RSRP-PdM, in which the predicted health state distributions are updated as new data become available. This approach reduces the uncertainty of the health states and thus improves the decision-making basis for maintenance planning. To solve the instances, we employ a local neighborhood search, which is a modification of a heuristic for RSRP-PdM, and demonstrate its effectiveness. Using this solution algorithm, the presented approach is compared with the results of common maintenance strategies on test instances derived from real-world timetables. The obtained results show the benefits of the rolling horizon approach.</abstract>
    <parentTitle language="eng">24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2024.13</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">epub ahead of print</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <author>Ralf Borndörfer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9643</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>259</pageFirst>
    <pageLast>276</pageLast>
    <pageNumber>17</pageNumber>
    <edition/>
    <issue/>
    <volume>14742</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">ULD Build-Up Scheduling with Logic-Based Benders Decomposition</title>
    <abstract language="eng">We study a complex planning and scheduling problem arising from the build-up process of air cargo pallets and containers, collectively referred to as unit load devices (ULD), in which ULDs must be assigned to workstations for loading. Since air freight usually becomes available gradually along the planning horizon, ULD build-ups must be scheduled neither too early to avoid underutilizing ULD capacity, nor too late to avoid resource conflicts with other flights. Whenever possible, ULDs should be built up in batches, thereby giving ground handlers more freedom to rearrange cargo and utilize the ULD's capacity efficiently. The resulting scheduling problem has an intricate cost function and produces large time-expanded models, especially for longer planning horizons. We propose a logic-based Benders decomposition approach that assigns batches to time intervals and workstations in the master problem, while the actual schedule is decided in a subproblem. By choosing appropriate intervals, the subproblem becomes a feasibility problem that decomposes over the workstations. Additionally, the similarity of many batches is exploited by a strengthening procedure for no-good cuts. We benchmark our approach against a time-expanded MIP formulation from the literature on a publicly available data set. It solves 15% more instances to optimality and decreases run times by more than 50% in the geometric mean. This improvement is especially pronounced for longer planning horizons of up to one week, where the Benders approach solves over 50% instances more than the baseline</abstract>
    <parentTitle language="eng">Integration of Constraint Programming, Artificial Intelligence, and Operations Research</parentTitle>
    <identifier type="doi">10.1007/978-3-031-60597-0_17</identifier>
    <enrichment key="Series">Lecture Notes in Computer Science</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">02.02.2024</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ricardo Euler</author>
    <submitter>Ricardo Euler</submitter>
    <author>Ralf Borndörfer</author>
    <author>Christian Puchert</author>
    <author>Tuomo Takkula</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="Cargo">Cargo</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9602</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Iterative Refinement Approach for the Rolling Stock Rotation Problem with Predictive Maintenance</title>
    <abstract language="eng">The rolling stock rotation problem with predictive maintenance (RSRP-PdM) involves the assignment of trips to a fleet of vehicles with integrated maintenance scheduling based on the predicted failure probability of the vehicles. These probabilities are determined by the health states of the vehicles, which are considered to be random variables distributed by a parameterized family of probability distribution functions. During the operation of the trips, the corresponding parameters get updated. In this article, we present a dual solution approach for RSRP-PdM and generalize a linear programming based lower bound for this problem to families of probability distribution functions with more than one parameter. For this purpose, we define a rounding function that allows for a consistent underestimation of the parameters and model the problem by a state-expanded event-graph in which the possible states are restricted to a discrete set. This induces a flow problem that is solved by an integer linear program. We show that the iterative refinement of the underlying discretization leads to solutions that converge from below to an optimal solution of the original instance. Thus, the linear relaxation of the considered integer linear program results in a lower bound for RSRP-PdM. Finally, we report on the results of computational experiments conducted on a library of test instances.</abstract>
    <identifier type="arxiv">2404.08367</identifier>
    <enrichment key="SubmissionStatus">under review</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PeerReviewed">no</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <author>Ralf Borndörfer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9556</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>100434</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>30</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Approximating rolling stock rotations with integrated predictive maintenance</title>
    <abstract language="eng">We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for six instances derived from real-world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.</abstract>
    <parentTitle language="eng">Journal of Rail Transport Planning &amp; Management</parentTitle>
    <identifier type="doi">10.1016/j.jrtpm.2024.100434</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2024-02-28</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-89531</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <author>Ralf Borndörfer</author>
    <author>Boris Grimm</author>
    <author>Alexander Tesch</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9505</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>106186</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>154</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2023-02-24</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem</title>
    <abstract language="eng">The Fairness-Oriented Crew Rostering Problem (FCRP) considers the joint optimization of attractiveness and fairness in cyclic crew rostering. Like many problems in scheduling and logistics, the combinatorial complexity of cyclic rostering causes exact methods to fail for large-scale practical instances. In case of the FCRP, this is accentuated by the additionally imposed fairness requirements. Hence, heuristic methods are necessary. We present a three-phase heuristic for the FCRP combining column generation techniques with variable-depth neighborhood search. The heuristic exploits different mathematical formulations to find feasible solutions and to search for improvements. We apply our methodology to practical instances from Netherlands Railways (NS), the main passenger railway operator in the Netherlands Our results show the three-phase heuristic finds good solutions for most instances and outperforms a state-of-the-art commercial solver.</abstract>
    <parentTitle language="eng">Computers &amp; Operations Research</parentTitle>
    <identifier type="doi">10.1016/j.cor.2023.106186</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">epub ahead of print</enrichment>
    <enrichment key="AcceptedDate">2023-03-06</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Thomas Breugem</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Thomas Schlechte</author>
    <author>Christof Schulz</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="schulz">Schulz, Christof</collection>
    <collection role="projects" number="WS-OPT">WS-OPT</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
  </doc>
  <doc>
    <id>9476</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>15</pageLast>
    <pageNumber>15</pageNumber>
    <edition/>
    <issue/>
    <volume>13</volume>
    <type>article</type>
    <publisherName>Elsevier BV</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Price optimal routing in public transportation</title>
    <parentTitle language="eng">EURO Journal on Transportation and Logistics</parentTitle>
    <identifier type="doi">10.1016/j.ejtl.2024.100128</identifier>
    <identifier type="issn">2192-4376</identifier>
    <enrichment key="opus_doi_flag">true</enrichment>
    <enrichment key="opus_doi_json">{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T01:15:18Z","timestamp":1707873318178},"reference-count":36,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T00:00:00Z","timestamp":1706745600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2024,2,8]],"date-time":"2024-02-08T00:00:00Z","timestamp":1707350400000},"content-version":"vor","delay-in-days":7,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["EURO Journal on Transportation and Logistics"],"published-print":{"date-parts":[[2024,2]]},"DOI":"10.1016\/j.ejtl.2024.100128","type":"journal-article","created":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T16:59:39Z","timestamp":1707843579000},"page":"100128","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"title":["Price optimal routing in public transportation"],"prefix":"10.1016","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-5112-4191","authenticated-orcid":false,"given":"Ricardo","family":"Euler","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-8337-4387","authenticated-orcid":false,"given":"Niels","family":"Lindner","sequence":"additional","affiliation":[]},{"given":"Ralf","family":"Bornd\u00f6rfer","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"3","key":"10.1016\/j.ejtl.2024.100128_b1","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1137\/S0097539798337716","article-title":"Formal-language-constrained path problems","volume":"30","author":"Barrett","year":"2000","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ejtl.2024.100128_b2","series-title":"Algorithm Engineering - Selected Results and Surveys","first-page":"19","article-title":"Route planning in transportation networks","volume":"vol. 9220","author":"Bast","year":"2016"},{"key":"10.1016\/j.ejtl.2024.100128_b3","series-title":"Subpath-Optimality of Multi-Criteria Shortest Paths in Time- and Event-Dependent Networks","author":"Berger","year":"2009"},{"key":"10.1016\/j.ejtl.2024.100128_b4","series-title":"17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)","first-page":"15:1","article-title":"Cost projection methods for the shortest path problem with crossing costs","volume":"vol. 59","author":"Blanco","year":"2017"},{"key":"10.1016\/j.ejtl.2024.100128_b5","series-title":"The Shortest Path Problem with Crossing Costs","author":"Blanco","year":"2016"},{"issue":"4","key":"10.1016\/j.ejtl.2024.100128_b6","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1080\/10875549.2014.951905","article-title":"Getting around when you\u2019re just getting by: Transportation survival strategies of the poor","volume":"18","author":"Blumenberg","year":"2014","journal-title":"J. Poverty"},{"key":"10.1016\/j.ejtl.2024.100128_b7","first-page":"1","article-title":"Ein graphen-basiertes modell zur beschreibung von preissystemen im \u00f6ffentlichen nahverkehr","volume":"002\/127","author":"Bornd\u00f6rfer","year":"2021","journal-title":"HEUREKA 21"},{"key":"10.1016\/j.ejtl.2024.100128_b8","series-title":"Ein mathematisches Modell zur Beschreibung von Preissystemen im \u00f6V","author":"Bornd\u00f6rfer","year":"2018"},{"key":"10.1016\/j.ejtl.2024.100128_b9","first-page":"299","article-title":"Paths and cycles in colored graphs.","volume":"31","author":"Broersma","year":"2005","journal-title":"Australas. J. Combin."},{"key":"10.1016\/j.ejtl.2024.100128_b10","doi-asserted-by":"crossref","DOI":"10.1016\/j.regsciurbeco.2022.103803","article-title":"Experimental evidence on the effects of means-tested public transportation subsidies on travel behavior","volume":"96","author":"Brough","year":"2022","journal-title":"Reg. Sci. Urban Econ."},{"key":"10.1016\/j.ejtl.2024.100128_b11","doi-asserted-by":"crossref","DOI":"10.1016\/j.regsciurbeco.2020.103616","article-title":"The impact of fare-free public transport on travel behavior: Evidence from a randomized controlled trial","volume":"86","author":"Bull","year":"2021","journal-title":"Reg. Sci. Urban Econ."},{"key":"10.1016\/j.ejtl.2024.100128_b12","series-title":"Resilience and Sustainable Transportation Systems","first-page":"290","article-title":"Mode choice behavior analysis under the impact of transfer fare discount: A case study from Beijing public transit system","author":"Chen","year":"2020"},{"key":"10.1016\/j.ejtl.2024.100128_b13","article-title":"An improved multiobjective shortest path algorithm","volume":"135","author":"de las Casas","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.ejtl.2024.100128_b14","series-title":"2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments","first-page":"54","article-title":"Fast and exact public transit routing with restricted Pareto sets","author":"Delling","year":"2019"},{"issue":"3","key":"10.1016\/j.ejtl.2024.100128_b15","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1287\/trsc.2014.0534","article-title":"Round-based public transit routing","volume":"49","author":"Delling","year":"2015","journal-title":"Transp. Sci."},{"key":"10.1016\/j.ejtl.2024.100128_b16","series-title":"Proceedings of the 7th International Conference on Experimental Algorithms","first-page":"347","article-title":"Multi-criteria shortest paths in time-dependent train networks","author":"Disser","year":"2008"},{"key":"10.1016\/j.ejtl.2024.100128_b17","series-title":"19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)","first-page":"12:1","article-title":"A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks","volume":"vol. 75","author":"Euler","year":"2019"},{"key":"10.1016\/j.ejtl.2024.100128_b18","series-title":"Fare Policies, Structures and Technologies","author":"Fleishman","year":"1996"},{"issue":"3","key":"10.1016\/j.ejtl.2024.100128_b19","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1109\/TSE.1976.233819","article-title":"On two problems in the generation of program test paths","volume":"SE-2","author":"Gabow","year":"1976","journal-title":"IEEE Trans. Softw. Eng."},{"key":"10.1016\/j.ejtl.2024.100128_b20","series-title":"Efficient Algorithms for Intermodal Routing and Monitoring in Travel Information Systems","author":"G\u00fcndling","year":"2020"},{"key":"10.1016\/j.ejtl.2024.100128_b21","article-title":"Bicriterion path problems","volume":"vol. 177","author":"Hansen","year":"1980"},{"key":"10.1016\/j.ejtl.2024.100128_b22","series-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"issue":"4","key":"10.1016\/j.ejtl.2024.100128_b23","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/321906.321910","article-title":"On finding the maxima of a set of vectors","volume":"22","author":"Kung","year":"1975","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.ejtl.2024.100128_b24","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0377-2217(84)90077-8","article-title":"On a multicriteria shortest path problem","volume":"16","author":"Martins","year":"1984","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.ejtl.2024.100128_b25","series-title":"MDV fares","author":"Mitteldeutscher Verkehrsverbund GmbH","year":"2019"},{"key":"10.1016\/j.ejtl.2024.100128_b26","series-title":"MDV GTFS data","author":"Mitteldeutscher Verkehrsverbund GmbH","year":"2019"},{"issue":"3","key":"10.1016\/j.ejtl.2024.100128_b27","first-page":"321","article-title":"Semiring frameworks and algorithms for shortest-distance problems","volume":"7","author":"Mohri","year":"2002","journal-title":"J. Autom. Lang. Comb."},{"key":"10.1016\/j.ejtl.2024.100128_b28","series-title":"Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways","first-page":"657","article-title":"Paying less for train connections with MOTIS","volume":"vol. 2","author":"M\u00fcller-Hannemann","year":"2005"},{"issue":"3","key":"10.1016\/j.ejtl.2024.100128_b29","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/79147.214078","article-title":"Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length","volume":"37","author":"Orda","year":"1990","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.ejtl.2024.100128_b30","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s00186-018-0649-x","article-title":"Algorithms for non-linear and stochastic resource constrained shortest path","volume":"89","author":"Parmentier","year":"2019","journal-title":"Math. Methods Oper. Res."},{"issue":"3","key":"10.1016\/j.ejtl.2024.100128_b31","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1016\/j.cor.2010.08.003","article-title":"Multi-objective and multi-constrained non-additive shortest path problems","volume":"38","author":"Reinhardt","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/j.ejtl.2024.100128_b32","series-title":"Expanding Access to the City: How Public Transit Fare Policy Shapes Travel Decision Making and Behavior of Low-Income riders","author":"Rosenblum","year":"2020"},{"key":"10.1016\/j.ejtl.2024.100128_b33","series-title":"The cheapest ticket problem in public transport","author":"Sch\u00f6bel","year":"2021"},{"key":"10.1016\/j.ejtl.2024.100128_b34","series-title":"VBN nightliner fares","author":"Verkehrsverbund Bremen\/Niedersachsen GmbH","year":"2019"},{"key":"10.1016\/j.ejtl.2024.100128_b35","series-title":"VBN fares","author":"Verkehrsverbund Bremen\/Niedersachsen GmbH","year":"2023"},{"key":"10.1016\/j.ejtl.2024.100128_b36","series-title":"Linear and Combinatorial Optimization in Ordered Algebraic Structures","volume":"vol. 10","author":"Zimmermann","year":"1981"}],"container-title":["EURO Journal on Transportation and Logistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S2192437624000037?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S2192437624000037?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T16:59:48Z","timestamp":1707843588000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S2192437624000037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2]]},"references-count":36,"alternative-id":["S2192437624000037"],"URL":"http:\/\/dx.doi.org\/10.1016\/j.ejtl.2024.100128","relation":{},"ISSN":["2192-4376"],"issn-type":[{"value":"2192-4376","type":"print"}],"subject":["Management Science and Operations Research","Transportation","Modeling and Simulation"],"published":{"date-parts":[[2024,2]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Price optimal routing in public transportation","name":"articletitle","label":"Article Title"},{"value":"EURO Journal on Transportation and Logistics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ejtl.2024.100128","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2024 Published by Elsevier B.V. on behalf of Association of European Operational Research Societies (EURO).","name":"copyright","label":"Copyright"}],"article-number":"100128"}}</enrichment>
    <enrichment key="opus_crossrefDocumentType">journal-article</enrichment>
    <enrichment key="opus_crossrefLicence">https://www.elsevier.com/tdm/userlicense/1.0/</enrichment>
    <enrichment key="opus_import_origin">crossref</enrichment>
    <enrichment key="opus_doiImportPopulated">SubjectUncontrolled_1,SubjectUncontrolled_2,SubjectUncontrolled_3,PersonAuthorFirstName_1,PersonAuthorLastName_1,PersonAuthorIdentifierOrcid_1,PersonAuthorFirstName_2,PersonAuthorLastName_2,PersonAuthorIdentifierOrcid_2,PersonAuthorFirstName_3,PersonAuthorLastName_3,PublisherName,TitleMain_1,Language,TitleParent_1,ArticleNumber,PublishedYear,IdentifierIssn,Enrichmentopus_crossrefLicence</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">08.02.2024</enrichment>
    <enrichment key="opus.source">doi-import</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-86414</enrichment>
    <author>Ricardo Euler</author>
    <submitter>Ricardo Euler</submitter>
    <author>Niels Lindner</author>
    <author>Ralf Borndörfer</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Management Science and Operations Research</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Transportation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Modeling and Simulation</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="MOIN">MOIN</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9447</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue>5</issue>
    <volume>59</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Comparison of Two Models for Rolling Stock Scheduling</title>
    <abstract language="eng">A major step in the planning process of passenger railway operators is the assignment of rolling stock, that is, train units, to the trips of the timetable. A wide variety of mathematical optimization models have been proposed to support this task, which we discuss and argue to be justified in order to deal with operational differences between railway operators, and hence different planning requirements, in the best possible way. Our investigation focuses on two commonly used models, the composition model and the hypergraph model, that were developed for Netherlands Railways (NS) and DB Fernverkehr AG (DB), respectively. We compare these models in two distinct problem settings, an NS setting and DB-light setting and consider different model variants to tune the models to these settings. We prove that in both of these settings, the linear programming bounds of the two models are equally strong as long as a number of reasonable assumptions are met. However, through a numerical evaluation on NS and DB-light instances, we show that the numerical performance of the models strongly depends on the instances. Although the composition model is the most compact and fastest model for the NS instances, an adjusted version of this model grows quickly for the DB-light instances and is then outperformed by the considered hypergraph model variants. Moreover, we show that a depot-extended version of the hypergraph model is able to combine strengths of both models and show good performance on both the NS and DB-light instances.</abstract>
    <parentTitle language="deu">Transportation Science</parentTitle>
    <identifier type="doi">10.1287/trsc.2024.0505</identifier>
    <identifier type="arxiv">2312.09697</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Rowan Hoogervorst</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>9294</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>CCC 1</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Robustness Analysis of Long Distance Train Crew Schedules in Germany</title>
    <abstract language="eng">Nowadays railway networks are highly complex and often very fragile systems. A wide variety of individual operations that influence each other have to go hand in hand to end up with a smoothly and efficiently running system. Many of these operations suffer from uncertainty as trains could be delayed, the signaling system be disrupted or scheduled crews could be ill. Usually these opartions could be organized hierarchically from long term strategical decisions to real time decision management. Each stage in the hierarchy defines a different mathematical optimization problem, which is solved sequentially. At every stage the knowledge about preceding or succeeding planning stages may vary and also the interaction between two stages in this chain of problems may vary from almost no interaction to highly dependent situations. This paper deals with a topic that is an example for the latter case, namely the interaction between vehicle schedules, vehicle punctuality, and crew schedules. To reduce the number of potential rescheduling actions we developed a software tool in cooperation with our practical partner DB Fernverkehr AG (DBF) to predict a certain set of critical crew schedules. This tool evaluates, predicts, and determines "bottlenecks" in the crew schedule in the sense of potentially required rescheduling actions due to likely delays. The approach was tested on real life crew and train timetable data of DBF and can be regarded as the computation of key performance indicators, which is often desired. For our experiments we had access to the operated timetable and crew schedule of DBF for periods of two and six weeks in 2019.</abstract>
    <parentTitle language="eng">Proceedings Of The Fifth Iinternational Conference On Railway Technology: Research, Development and Maintenance</parentTitle>
    <identifier type="doi">10.4203/ccc.1.23.17</identifier>
    <identifier type="issn">2753-3239</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Boris Grimm</submitter>
    <author>Boris Grimm</author>
    <author>Stanley Schade</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>9293</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>13:1</pageFirst>
    <pageLast>13:15</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>115</volume>
    <type>conferenceobject</type>
    <publisherName>Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik</publisherName>
    <publisherPlace>Dagstuhl, Germany</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization</title>
    <abstract language="eng">The fundamental task of every passenger railway operator is to offer an attractive railway timetable to the passengers while operating it as cost efficiently as possible. The available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating costs are minimum. This so-called Rolling Stock Rotation Problem (RSRP) is well studied in the literature. In this paper we consider an acyclic version of the RSRP that includes vehicle maintenance. As the latter is an important aspect, maintenance services have to be planned simultaneously to ensure the rotation’s feasibility in practice. Indeed, regular maintenance is important for the safety and reliability of the rolling stock as well as enforced by law in many countries. We present a new integer programming formulation that links a hyperflow to model vehicle compositions and their coupling decisions to a set of path variables that take care of the resource consumption of the individual vehicles. To solve the model we developed different column generation algorithms which are compared to each other as well as to the MILP flow formulation of [Ralf Borndörfer et al., 2016] on a test set of real world instances.</abstract>
    <parentTitle language="eng">23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)</parentTitle>
    <identifier type="doi">https://doi.org/10.4230/OASIcs.ATMOS.2023.13</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">31.07.23</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="FulltextUrl">https://drops.dagstuhl.de/storage/01oasics/oasics-vol115-atmos2023/OASIcs.ATMOS.2023.13/OASIcs.ATMOS.2023.13.pdf</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Julian Bushe</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>9244</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2023-10-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Non-Linear Battery Behavior in Electric Vehicle Scheduling Problems</title>
    <abstract language="eng">The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-92441</identifier>
    <identifier type="doi">10.1007/978-3-031-58405-3_53</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Fabian Löbel</author>
    <submitter>Fabian Löbel</submitter>
    <author>Ralf Borndörfer</author>
    <author>Steffen Weider</author>
    <series>
      <title>ZIB-Report</title>
      <number>23-24</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Electric Vehicle Scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Non-Linear Charging</value>
    </subject>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="persons" number="fabian.loebel">Löbel, Fabian</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="EBUS">EBUS</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/9244/zibreport2324.pdf</file>
  </doc>
  <doc>
    <id>9235</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>349</pageFirst>
    <pageLast>384</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>17</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2025-02-13</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">K-Shortest Simple Paths Using Biobjective Path Search</title>
    <abstract language="eng">In this paper we introduce a new algorithm for the k-Shortest Simple Paths (K-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick (2012) that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.</abstract>
    <parentTitle language="eng">Mathematical Programming Computation</parentTitle>
    <identifier type="doi">10.1007/s12532-025-00276-0</identifier>
    <identifier type="arxiv">2309.10377</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <licence>Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International</licence>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Antonio Sedeño-Noda</author>
    <author>Ralf Borndörfer</author>
    <author>Max Huneshagen</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>9234</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>106852</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>173</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-09-21</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">New Dynamic Programming Algorithm for the Multiobjective Minimum Spanning Tree Problem</title>
    <abstract language="eng">The Multiobjective Minimum Spanning Tree (MO-MST) problem is a variant of the Minimum Spanning Tree problem, in which the costs associated with every edge of the input graph are vectors. In this paper, we design a new dynamic programming MO-MST algorithm. Dynamic programming for a MO-MST instance leads to the definition of an instance of the One-to-One Multiobjective Shortest Path (MOSP) problem and both instances have equivalent solution sets. The arising MOSP instance is defined on a so called transition graph. We study the original size of this graph in detail and reduce its size using cost dependent arc pruning criteria. To solve the MOSP instance on the reduced transition graph, we design the Implicit Graph Multiobjective Dijkstra Algorithm (IG-MDA), exploiting recent improvements on MOSP algorithms from the literature. All in all, the new IG-MDA outperforms the current state of the art on a big set of instances from the literature. Our code and results are publicly available.</abstract>
    <parentTitle language="eng">Computers &amp; Operations Research</parentTitle>
    <identifier type="doi">10.1016/j.cor.2024.106852</identifier>
    <identifier type="arxiv">2306.16203</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <licence>Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International</licence>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Antonio Sedeño-Noda</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>9212</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>15:1</pageFirst>
    <pageLast>15:6</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>115</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates</title>
    <abstract language="eng">The ongoing electrification of logistics systems and vehicle fleets increases the complexity of associated vehicle routing or scheduling problems.&#13;
Battery-powered vehicles have to be scheduled to recharge in-service, and the relationship between charging time and replenished driving range is non-linear.&#13;
In order to access the powerful toolkit offered by mixed-integer and linear programming techniques, this battery behavior has to be linearized.&#13;
Moreover, as electric fleets grow, power draw peaks have to be avoided to save on electricity costs or to adhere to hard grid capacity limits, such that it becomes desirable to keep recharge rates dynamic.&#13;
We suggest a novel linearization approach of battery charging behavior for vehicle scheduling problems, in which the recharge rates are optimization variables and not model parameters.</abstract>
    <parentTitle language="eng">23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2023.15</identifier>
    <identifier type="urn">urn:nbn:de:0030-drops-187765</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2023-07-31</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Fabian Löbel</author>
    <submitter>Fabian Löbel</submitter>
    <author>Ralf Borndörfer</author>
    <author>Steffen Weider</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="persons" number="fabian.loebel">Löbel, Fabian</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="EBUS">EBUS</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>9204</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>3:1</pageFirst>
    <pageLast>3:6</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>115</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Convergence Properties of Newton’s Method for Globally Optimal Free Flight Trajectory Optimization</title>
    <abstract language="eng">The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition.</abstract>
    <parentTitle language="eng">23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2023.3</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2023-08-27</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-91309</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Martin Weiser</submitter>
    <author>Fabian Danecker</author>
    <author>Martin Weiser</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="institutes" number="MSoCP">Modeling and Simulation of Complex Processes</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MathPlus-AA3-3">MathPlus-AA3-3</collection>
    <collection role="projects" number="MathPlus-TrU-4">MathPlus-TrU-4</collection>
  </doc>
  <doc>
    <id>9184</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted>2023</thesisYearAccepted>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>4</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Newton's Method for Global Free Flight Trajectory Optimization</title>
    <abstract language="eng">Globally optimal free flight trajectory optimization can be achieved with a combination of discrete and continuous optimization. A key requirement is that Newton's method for continuous optimization converges in a sufficiently large neighborhood around a minimizer. We show in this paper that, under certain assumptions, this is the case.</abstract>
    <parentTitle language="eng">Operations Research Forum</parentTitle>
    <identifier type="doi">10.1007/s43069-023-00238-z</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-91846</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-89876</enrichment>
    <enrichment key="SourceTitle">Operations Research Forum 4, 63 (2023).</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Fabian Danecker</submitter>
    <author>Fabian Danecker</author>
    <author>Martin Weiser</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="institutes" number="MSoCP">Modeling and Simulation of Complex Processes</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MathPlus-AA3-3">MathPlus-AA3-3</collection>
    <collection role="projects" number="MathPlus-TrU-4">MathPlus-TrU-4</collection>
  </doc>
  <doc>
    <id>9173</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2023-07-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance</title>
    <abstract language="eng">We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-91734</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>23-20</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Rolling Stock Rotation Planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Predictive Maintenance</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Test Library</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/9173/ZR-23-20.pdf</file>
  </doc>
  <doc>
    <id>9130</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2023-07-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Convergence Properties of Newton's Method for Globally Optimal Free Flight Trajectory Optimization</title>
    <abstract language="eng">The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-91309</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Fabian Danecker</submitter>
    <author>Fabian Danecker</author>
    <author>Martin Weiser</author>
    <series>
      <title>ZIB-Report</title>
      <number>23-19</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>shortest path</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>flight planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>free flight</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimal control</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>global optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Newton's method</value>
    </subject>
    <collection role="ccs" number="">Global optimization (NEW)</collection>
    <collection role="ccs" number="">Boundary value problems</collection>
    <collection role="ccs" number="">Graph algorithms</collection>
    <collection role="msc" number="49-XX">CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]</collection>
    <collection role="msc" number="65-XX">NUMERICAL ANALYSIS</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="compmed">Computational Medicine</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="institutes" number="MSoCP">Modeling and Simulation of Complex Processes</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MathPlus-TrU-4">MathPlus-TrU-4</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/9130/ZIB-Report-23-19.pdf</file>
  </doc>
  <doc>
    <id>8987</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Newton's Method for Global Free Flight Trajectory Optimization</title>
    <abstract language="eng">Globally optimal free flight trajectory optimization can be achieved with a combination of discrete and continuous optimization. A key requirement is that Newton's method for continuous optimization converges in a sufficiently large neighborhood around a minimizer. We show in this paper that, under certain assumptions, this is the case.</abstract>
    <identifier type="urn">urn:nbn:de:0297-zib-89876</identifier>
    <identifier type="doi">10.12752/8987</identifier>
    <enrichment key="PreprintUrn">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="SourceTitle">Operations Research Forum 4, 63 (2023).</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Fabian Danecker</submitter>
    <author>Fabian Danecker</author>
    <author>Martin Weiser</author>
    <series>
      <title>ZIB-Report</title>
      <number>23-08</number>
    </series>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="institutes" number="MSoCP">Modeling and Simulation of Complex Processes</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MathPlus-TrU-4">MathPlus-TrU-4</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8987/BorndoerferDaneckerWeiser2022.pdf</file>
  </doc>
  <doc>
    <id>8964</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>295</pageFirst>
    <pageLast>301</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Springer, Cham</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2022-08-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimal Line Plans in the Parametric City and the Impact of In-Motion Costs</title>
    <abstract language="eng">Line planning in public transport involves determining vehicle routes and assigning frequencies of service such that travel demands are satisfied. We evaluate how line plans, which are optimal with respect to in-motion costs (IMC), the objective function depending purely on arc-lengths for both user and operator costs, performs with respect to the value of resources consumed (VRC). The latter is an elaborate, socio-economic cost function which includes discomfort caused by delay, boarding and alighting times, and transfers. Even though discomfort is a large contributing factor to VRC and is entirely disregarded in IMC,  we observe that the two cost functions are qualitatively comparable.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2021</parentTitle>
    <identifier type="isbn">978-3-031-08623-6</identifier>
    <identifier type="doi">10.1007/978-3-031-08623-6_44</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-84195</enrichment>
    <enrichment key="Series">Lecture Notes in Operations Research</enrichment>
    <editor>Norbert Trautmann</editor>
    <submitter>Berenike Masing</submitter>
    <author>Berenike Masing</author>
    <editor>Mario Drägi</editor>
    <author>Niels Lindner</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="persons" number="masing">Masing, Berenike</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="SymLPP">SymLPP</collection>
  </doc>
  <doc>
    <id>8953</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2023-01-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Approximating the RSRP with Predictive Maintenance</title>
    <abstract language="eng">We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-89531</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <author>Felix Prause</author>
    <submitter>Felix Prause</submitter>
    <author>Ralf Borndörfer</author>
    <author>Boris Grimm</author>
    <author>Alexander Tesch</author>
    <series>
      <title>ZIB-Report</title>
      <number>23-04</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Rolling Stock Rotation Planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Predictive Maintenance</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Linear Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Heuristic</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Lower Bound</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="prause">Prause, Felix</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="BerDiBa">BerDiBa</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8953/ZR-23-04.pdf</file>
  </doc>
  <doc>
    <id>8866</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1:1</pageFirst>
    <pageLast>1:15</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>106</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles</title>
    <abstract language="eng">The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A∗ heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances.</abstract>
    <parentTitle language="eng">22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2022.1</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Marco Blanco</author>
    <submitter>Marco Blanco</submitter>
    <author>Ralf Borndörfer</author>
    <author>Pedro Maristany de las Casas</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>8881</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>13</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>106</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization</title>
    <abstract language="eng">We present an efficient algorithm that finds a globally optimal solution to the 2D Free Flight Trajectory Optimization Problem (aka Zermelo Navigation Problem) up to arbitrary precision in finite time. The algorithm combines a discrete and a continuous optimization phase. In the discrete phase, a set of candidate paths that densely covers the trajectory space is created on a directed auxiliary graph. Then Yen’s algorithm provides a promising set of discrete candidate paths which subsequently undergo a locally convergent refinement stage. Provided that the auxiliary graph is sufficiently dense, the method finds a path that lies within the convex domain around the global minimizer. From this starting point, the second stage will converge rapidly to the optimum. The density of the auxiliary graph depends solely on the wind field, and not on the accuracy of the&#13;
solution, such that the method inherits the superior asymptotic convergence properties of the optimal control stage.</abstract>
    <parentTitle language="eng">22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2022.2</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2022-08-01</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Martin Weiser</submitter>
    <author>Fabian Danecker</author>
    <author>Martin Weiser</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="institutes" number="MSoCP">Modeling and Simulation of Complex Processes</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MathPlus-AA3-3">MathPlus-AA3-3</collection>
  </doc>
  <doc>
    <id>8861</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst>419</pageFirst>
    <pageLast>443</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>166</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">The price of symmetric line plans in the Parametric City</title>
    <abstract language="eng">We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. We prove that the symmetry gap is small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations.</abstract>
    <parentTitle language="eng">Transportation Research Part B: Methodological</parentTitle>
    <identifier type="doi">10.1016/j.trb.2022.10.009</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-88613</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-85648</enrichment>
    <author>Berenike Masing</author>
    <submitter>Berenike Masing</submitter>
    <author>Niels Lindner</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="persons" number="masing">Masing, Berenike</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="SymLPP">SymLPP</collection>
  </doc>
  <doc>
    <id>8815</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>253</pageFirst>
    <pageLast>277</pageLast>
    <pageNumber/>
    <edition/>
    <issue>2</issue>
    <volume>81</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2022-11-10</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Vertex Covering with Capacitated Trees</title>
    <abstract language="eng">The covering of a graph with (possibly disjoint) connected subgraphs is a funda-mental problem in graph theory. In this paper, we study a version to cover a graph’svertices by connected subgraphs subject to lower and upper weight bounds, and pro-pose a column generation approach to dynamically generate feasible and promisingsubgraphs. Our focus is on the solution of the pricing problem which turns out to bea variant of the NP-hard Maximum Weight Connected Subgraph Problem. We com-pare different formulations to handle connectivity, and find that a single-commodityflow formulation performs best. This is notable since the respective literature seemsto have widely dismissed this formulation. We improve it to a new coarse-to-fine flowformulation that is theoretically and computationally superior, especially for largeinstances with many vertices of degree 2 like highway networks, where it provides aspeed-up factor of 5 over the non-flow-based formulations. We also propose a pre-processing method that exploits a median property of weight-constrained subgraphs,a primal heuristic, and a local search heuristic. In an extensive computational studywe evaluate the presented connectivity formulations on different classes of instances,and demonstrate the effectiveness of the proposed enhancements. Their speed-upsessentially multiply to an overall factor of well over 10. Overall, our approach allowsthe reliable solution of instances with several hundreds of vertices in a few min-utes. These findings are further corroborated in a comparison to existing districtingmodels on a set of test instances from the literature</abstract>
    <parentTitle language="eng">Networks</parentTitle>
    <identifier type="doi">10.1002/net.22130</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2022-10-24</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-82616</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Stephan Schwartz</author>
    <author>William Surau</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="persons" number="surau">Surau, William</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
  </doc>
  <doc>
    <id>8783</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>63</pageFirst>
    <pageLast>68</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints</title>
    <abstract language="eng">Finding connected subgraphs of maximum weight subject to additional constraints on the subgraphs is a common (sub)problem in many applications. In this paper, we study the Maximum Weight Connected Subgraph Problem with a given root node and a lower and upper capacity constraint on the chosen subgraph. In addition, the nodes of the input graph are colored blue and red, and the chosen subgraph is required to be balanced regarding its cumulated blue and red weight. This problem arises as an essential subproblem in district planning applications. We show that the problem is NP-hard and give an integer programming formulation. By exploiting the capacity and balancing condition, we develop a powerful reduction technique that is able to significantly shrink the problem size. In addition, we propose a method to strengthen the LP relaxation of our formulation by identifying conflict pairs, i.e., nodes that cannot be both part of a chosen subgraph. Our computational study confirms the positive impact of the new preprocessing technique and of the proposed conflict cuts.</abstract>
    <parentTitle language="eng">Proceedings of the 10th International Network Optimization Conference (INOC), Aachen, Germany, June 7–10, 2022</parentTitle>
    <identifier type="doi">10.48786/inoc.2022.12</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-84427</enrichment>
    <submitter>Stephan Schwartz</submitter>
    <author>Ralf Borndörfer</author>
    <author>Stephan Schwartz</author>
    <author>William Surau</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="persons" number="surau">Surau, William</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
  </doc>
  <doc>
    <id>8781</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>254</pageFirst>
    <pageLast>260</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2022-08-30</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">ULD Build-Up Scheduling with Dynamic Batching in an Air Freight Hub</title>
    <abstract language="eng">Air freight is usually shipped in standardized unit load devices (ULDs). The planning process for the consolidation of transit cargo from inbound flights or locally emerging shipments into ULDs for outbound flights is called build-up scheduling. More specifically, outbound ULDs must be assigned a time and a workstation subject to both workstation capacity constraints and the availability of shipments which in turn depends on break-down decisions for incoming ULDs. ULDs scheduled for the same outbound flight should be built up in temporal and spatial proximity. This serves both to minimize overhead in transportation times and to allow workers to move freight between ULDs. We propose to address this requirement by processing ULDs for the same outbound flight in batches.&#13;
For the above build-up scheduling problem, we introduce a multi-commodity network design model. Outbound flights are modeled as commodities; transit cargo is represented by cargo flow volume and unpack and batch decisions are represented as design variables. The model is solved with a standard MIP solver on a set of benchmark data. For instances with a limited number of resource conflicts, near-optimal solutions are found in under two hours for a whole week of operations.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2021</parentTitle>
    <identifier type="doi">10.1007/978-3-031-08623-6_38</identifier>
    <enrichment key="Series">Lecture Notes in Operations Research</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2021-12-09</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-83482</enrichment>
    <author>Ricardo Euler</author>
    <submitter>Ricardo Euler</submitter>
    <author>Ralf Borndörfer</author>
    <author>Timo Strunk</author>
    <author>Tuomo Takkula</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="Cargo">Cargo</collection>
  </doc>
  <doc>
    <id>8641</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Price Optimal Routing in Public Transportation</title>
    <abstract language="eng">We consider the price-optimal earliest arrival problem in public transit (POEAP) in which we aim to calculate the Pareto-front of journeys with respect to ticket price and arrival time in a public transportation network. Public transit fare structures are often a combination of various fare strategies such as, e.g., distance-based fares, zone-based fares or flat fares. The rules that determine the actual ticket price are often very complex. Accordingly, fare structures are notoriously difficult to model as it is in general not sufficient to simply assign costs to arcs in a routing graph. Research into POEAP is scarce and usually either relies on heuristics or only considers restrictive fare models that are too limited to cover the full scope of most real-world applications. We therefore introduce conditional fare networks (CFNs), the first framework for representing a large number of real-world fare structures. We show that by relaxing label domination criteria, CFNs can be used as a building block in label-setting multi-objective shortest path algorithms. By the nature of their extensive modeling capabilities, optimizing over CFNs is NP-hard. However, we demonstrate that adapting the multi-criteria RAPTOR (MCRAP) algorithm for CFNs yields an algorithm capable of solving POEAP to optimality in less than 400 ms on average on a real-world data set. By restricting the size of the Pareto-set, running times are further reduced to below 10 ms.</abstract>
    <identifier type="doi">https://doi.org/10.48550/arXiv.2204.01326</identifier>
    <identifier type="arxiv">2204.01326</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-86414</identifier>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ricardo Euler</author>
    <submitter>Ricardo Euler</submitter>
    <author>Niels Lindner</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="MOIN">MOIN</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>8573</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>277</pageFirst>
    <pageLast>298</pageLast>
    <pageNumber/>
    <edition/>
    <issue>3</issue>
    <volume>82</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2023-07-08</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Targeted multiobjective Dijkstra Algorithm</title>
    <abstract language="eng">We introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. It is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. For any explored subpath, a label setting MOSP algorithm decides whether the subpath can be discarded or must be stored as part of the output. A major design choice is how to store subpaths from the moment they are first explored until the mentioned final decision can be made. The T-MDA combines the polynomially bounded size of the priority queue used in the MDA and alazy management of paths that are not in the queue. The running time bounds from the MDA remain valid. In practice, the T-MDA outperforms known algorithms from the literature and the increased memory consumption is negligible. In this paper, we benchmark the T-MDA against an improved version of the state of the art NAMOA∗drOne-to-One MOSP algorithm from the literature on a standard testbed.</abstract>
    <parentTitle language="eng">Networks</parentTitle>
    <identifier type="arxiv">2110.10978</identifier>
    <identifier type="doi">10.1002/net.22174</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Pedro Maristany de las Casas</author>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Luitgard Kraus</author>
    <author>Antonio Sedeno-Noda</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>8564</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2022-01-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Price of Symmetric Line Plans in the Parametric City</title>
    <abstract language="eng">We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. The symmetry gap is provably small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="arxiv">2201.09756</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-85648</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Berenike Masing</author>
    <submitter>Berenike Masing</submitter>
    <author>Niels Lindner</author>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>22-01</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>parametric city modeling</value>
    </subject>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="persons" number="masing">Masing, Berenike</collection>
    <collection role="projects" number="SymLPP">SymLPP</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8564/ZR-22-01.pdf</file>
  </doc>
  <doc>
    <id>8551</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>135</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Improved Multiobjective Shortest Path Algorithm</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Computers &amp; Operations Research</parentTitle>
    <identifier type="doi">10.1016/j.cor.2021.105424</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-79712</enrichment>
    <author>Pedro Maristany de las Casas</author>
    <submitter>Ekaterina Engel</submitter>
    <author>Antonio Sedeno-Noda</author>
    <author>Ralf Borndörfer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8442</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-10-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints</title>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-84427</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Stephan Schwartz</author>
    <author>William Surau</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-34</number>
    </series>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="persons" number="surau">Surau, William</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8442/ZIB-Report-21-34.pdf</file>
  </doc>
  <doc>
    <id>8419</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-09-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimal Line Plans in the Parametric City and the Impact of In-Motion Costs</title>
    <abstract language="eng">Line planning in public transport involves determining vehicle routes and assigning frequencies of service such that travel demands are satisfied. We evaluate how line plans, which are optimal with respect to in-motion costs (IMC), the objective function depending purely on arc-lengths for both user and operator costs, performs with respect to the value of resources consumed (VRC). The latter is an elaborate, socio-economic cost function which includes discomfort caused by delay, boarding and alighting times, and transfers. Even though discomfort is a large contributing factor to VRC and is entirely disregarded in IMC, we observe that the two cost functions are qualitatively comparable.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-84195</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Berenike Masing</author>
    <submitter>Berenike Masing</submitter>
    <author>Niels Lindner</author>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-27</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>public transport</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>mixed-integer prgramming</value>
    </subject>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="persons" number="masing">Masing, Berenike</collection>
    <collection role="projects" number="SymLPP">SymLPP</collection>
  </doc>
  <doc>
    <id>8406</id>
    <completedYear>2021</completedYear>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>17:1</pageFirst>
    <pageLast>17:6</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>96</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-09-27</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Open Access Series in Informatics (OASIcs), 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2021.17</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Guvenc Sahin</author>
    <submitter>Ralf Borndörfer</submitter>
    <author>Amin Ahmadi Digehsara</author>
    <author>Ralf Borndörfer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8407</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>100315</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>22</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Timetable Optimization for a Moving Block System</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Journal of Rail Transport Planning &amp; Management</parentTitle>
    <identifier type="doi">10.1016/j.jrtpm.2022.100315</identifier>
    <identifier type="issn">2210-9706</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2021-03-25</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-82547</enrichment>
    <author>Thomas Schlechte</author>
    <submitter>Niels Lindner</submitter>
    <author>Ralf Borndörfer</author>
    <author>Jonas Denißen</author>
    <author>Simon Heller</author>
    <author>Torsten Klug</author>
    <author>Michael Küpper</author>
    <author>Niels Lindner</author>
    <author>Markus Reuther</author>
    <author>Andreas Söhlke</author>
    <author>William Steadman</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="klug">Klug, Torsten</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>8348</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-09-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">ULD Build-Up Scheduling with Dynamic Batching in an Air Freight Hub</title>
    <abstract language="eng">Air freight is usually shipped in standardized unit load devices (ULDs).&#13;
The planning process for the consolidation of  transit cargo from inbound flights or locally emerging shipments into ULDs for outbound flights is called build-up scheduling. &#13;
More specifically, outbound ULDs must be assigned a time and a workstation subject to both workstation capacity constraints and the availability of shipments which in turn depends on break-down decisions for incoming ULDs.&#13;
ULDs scheduled for the same outbound flight should be built up in temporal and spatial proximity.&#13;
This serves both to minimize overhead in transportation times  and to allow workers to move freight between ULDs.&#13;
We propose to address this requirement by processing ULDs for the same outbound flight in batches. &#13;
&#13;
For the above build-up scheduling problem, we introduce a multi-commodity network design model.&#13;
Outbound flights are modeled as commodities; transit cargo is represented by cargo flow volume and unpack and batch decisions are represented as design variables. &#13;
The model is solved with standard MIP solvers on a set of benchmark data.&#13;
For instances with a limited number of resource conflicts, near-optimal solutions are found in under two hours for a whole week of operations.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-83482</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ricardo Euler</author>
    <submitter>Ricardo Euler</submitter>
    <author>Ralf Borndörfer</author>
    <author>Timo Strunk</author>
    <author>Tuomo Takkula</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-31</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Logistics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Airline Applications</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="Cargo">Cargo</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8348/ZR-21-31.pdf</file>
  </doc>
  <doc>
    <id>8331</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>830</pageFirst>
    <pageLast>856</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>198</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Error Bounds for Discrete-Continuous Free Flight Trajectory Optimization</title>
    <abstract language="eng">Flight planning, the computation of optimal routes in view of flight time and  fuel consumption under given weather conditions, is traditionally done by finding globally shortest paths in a predefined airway network. Free flight trajectories, not restricted to a network, have the potential to reduce the costs significantly, and can be computed using locally convergent continuous optimal control methods.&#13;
&#13;
Hybrid methods that start with a discrete global search and refine with a fast continuous local optimization combine the best properties of both approaches, but rely on a good switchover, which requires error estimates for discrete paths relative to continuous trajectories.&#13;
    &#13;
Based on vertex density and local complete connectivity, we derive localized and a priori bounds for the flight time of discrete paths relative to the optimal continuous trajectory, and illustrate their properties on a set of benchmark problems. It turns out that localization improves the error bound by four orders of magnitude, but still leaves ample opportunities for tighter bounds using a posteriori error estimators.</abstract>
    <parentTitle language="eng">Journal of Optimization Theory and Applications</parentTitle>
    <identifier type="doi">10.1007/s10957-023-02264-7</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="AcceptedDate">2023-06-19</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Martin Weiser</submitter>
    <author>Fabian Danecker</author>
    <author>Martin Weiser</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="institutes" number="MSoCP">Modeling and Simulation of Complex Processes</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MathPlus-AA3-3">MathPlus-AA3-3</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8331/article.pdf</file>
  </doc>
  <doc>
    <id>8325</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>27:1</pageFirst>
    <pageLast>27:14</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>207</volume>
    <type>conferenceobject</type>
    <publisherName>Schloss Dagstuhl - Leibniz-Zentrum für Informatik</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Connected k-partition of k-connected graphs and c-claw-free graphs</title>
    <abstract language="eng">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.&#13;
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 &gt; 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.</abstract>
    <parentTitle language="eng">Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021</parentTitle>
    <identifier type="doi">10.4230/LIPIcs.APPROX/RANDOM.2021.27</identifier>
    <identifier type="urn">urn:nbn:de:0030-drops-147200</identifier>
    <enrichment key="Series">LIPIcs</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Katrin Casel</author>
    <author>Davis Issac</author>
    <author>Aikaterini Niklanovits</author>
    <author>Stephan Schwartz</author>
    <author>Ziena Zeif</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
  </doc>
  <doc>
    <id>8313</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>154</pageFirst>
    <pageLast>159</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-08-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Finding Minimum Balanced Separators - an Exact Approach</title>
    <abstract language="eng">Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2021</parentTitle>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-83138</identifier>
    <identifier type="doi">https://doi.org/10.1007/978-3-031-08623-6_24</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>William Surau</submitter>
    <author>Stephan Schwartz</author>
    <author>William Surau</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-25</number>
    </series>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="persons" number="surau">Surau, William</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8313/ZIB-Report-21-25.pdf</file>
  </doc>
  <doc>
    <id>8261</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-06-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Vertex Covering with Capacitated Trees</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-82616</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Stephan Schwartz</author>
    <author>William Surau</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-14</number>
    </series>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="persons" number="surau">Surau, William</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8261/ZIB-Report-21-14.pdf</file>
  </doc>
  <doc>
    <id>8254</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-06-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Microscopic Timetable Optimization for a Moving Block System</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-82547</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Jonas Denißen</author>
    <author>Simon Heller</author>
    <author>Torsten Klug</author>
    <author>Michael Küpper</author>
    <author>Niels Lindner</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <author>Andreas Söhlke</author>
    <author>William Steadman</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-13</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Moving Block</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Railway Track Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Railway Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Train Routing</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="klug">Klug, Torsten</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <thesisPublisher>Zuse Institute Berlin (ZIB)</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-zib/files/8254/ZR-21-13.pdf</file>
  </doc>
  <doc>
    <id>8205</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>22</pageLast>
    <pageNumber/>
    <edition/>
    <issue>2</issue>
    <volume>14</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An FPTAS for Dynamic Multiobjective Shortest Path Problems</title>
    <abstract language="eng">The Dynamic Multiobjective Shortest Path problem features multidimensional costs that can depend on several variables and not only on time; this setting is motivated by flight planning applications and the routing of electric vehicles. We give an exact algorithm for the FIFO case and derive from it an FPTAS for both, the static Multiobjective Shortest Path (MOSP) problems and, under mild assumptions, for the dynamic problem variant. The resulting FPTAS is computationally efficient and beats the known complexity bounds of other FPTAS for MOSP problems.</abstract>
    <parentTitle language="eng">Algorithms</parentTitle>
    <identifier type="doi">https://doi.org/10.3390/a14020043</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2021-01-22</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-80954</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <author>Pedro Maristany de las Casas</author>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Ralf Borndörfer</author>
    <author>Luitgard Kraus</author>
    <author>Antonio Sedeño-Noda</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>8134</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2020-12-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Discrete-Continuous Algorithm for Free Flight Planning</title>
    <abstract language="eng">We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="doi">10.3390/a14010004</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-81343</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="SourceTitle">Algorithms</enrichment>
    <enrichment key="AcceptedDate">2020-12-20</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Fabian Danecker</submitter>
    <author>Fabian Danecker</author>
    <author>Martin Weiser</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-33</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>shortest path</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>flight planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>free flight</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>discrete-continuous algorithm</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimal control</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>discrete optimization</value>
    </subject>
    <collection role="msc" number="49M37">Methods of nonlinear programming type [See also 90C30, 65Kxx]</collection>
    <collection role="msc" number="65K10">Optimization and variational techniques [See also 49Mxx, 93B40]</collection>
    <collection role="msc" number="65L10">Boundary value problems</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="institutes" number="compmed">Computational Medicine</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="institutes" number="MfLMS">Mathematics for Life and Materials Science</collection>
    <collection role="institutes" number="MSoCP">Modeling and Simulation of Complex Processes</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MathPlus-AA3-3">MathPlus-AA3-3</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8134/BorndoerferDaneckerWeiser2020.pdf</file>
  </doc>
  <doc>
    <id>8126</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst>20</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue>12</issue>
    <volume/>
    <type>other</type>
    <publisherName>Wiley</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Algorithmen unterstützen OP-Planung</title>
    <abstract language="deu">Mathematische Algorithmen&#13;
können durch Vorhersage&#13;
von Unsicherheiten optimierte OP-Pläne berechnen,&#13;
sodass mehrere Zielkriterien&#13;
wie Überstunden, Wartezeit&#13;
und Ausfälle im OP minimiert werden.</abstract>
    <parentTitle language="deu">Management &amp; Krankenhaus</parentTitle>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="SubmissionStatus">in press</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="FulltextUrl">https://www.management-krankenhaus.de/restricted-files/136444</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Alexander Tesch</author>
    <author>Guillaume Sagnol</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="BMBF-IBOSS">BMBF-IBOSS</collection>
    <collection role="institutes" number="healthcare">Mathematics of Health Care</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8099</id>
    <completedYear>2020</completedYear>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>4</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>14</volume>
    <type>article</type>
    <publisherName>MDPI</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2020-12-25</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Discrete-Continuous Algorithm for Free Flight Planning</title>
    <abstract language="eng">We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.</abstract>
    <parentTitle language="eng">Algorithms</parentTitle>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="doi">10.3390/a14010004</identifier>
    <enrichment key="AcceptedDate">2020-12-20</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-81343</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Fabian Danecker</submitter>
    <author>Fabian Danecker</author>
    <author>Martin Weiser</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>shortest path</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>flight planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>free flight</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>discrete-continuous algorithm</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimal control</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>discrete optimization</value>
    </subject>
    <collection role="msc" number="49M37">Methods of nonlinear programming type [See also 90C30, 65Kxx]</collection>
    <collection role="msc" number="65K10">Optimization and variational techniques [See also 49Mxx, 93B40]</collection>
    <collection role="msc" number="65L10">Boundary value problems</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="institutes" number="num">Numerical Mathematics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weiser">Weiser, Martin</collection>
    <collection role="institutes" number="MfLMS">Mathematics for Life and Materials Science</collection>
    <collection role="institutes" number="MSoCP">Modeling and Simulation of Complex Processes</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MathPlus-AA3-3">MathPlus-AA3-3</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8095</id>
    <completedYear>2020</completedYear>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2020-12-01</completedDate>
    <publishedDate>2020-12-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An FPTAS for Dynamic Multiobjective Shortest Path Problems</title>
    <abstract language="eng">We propose in this paper the Dynamic Multiobjective Shortest Problem. It features multidimensional states that can depend on several variables and not only on time; this setting is  motivated by flight planning and electric vehicle routing applications. We give an exact algorithm for the FIFO case and derive from it an FPTAS, which is computationally efficient. It also features the best known complexity in the static case.</abstract>
    <identifier type="urn">urn:nbn:de:0297-zib-80954</identifier>
    <identifier type="doi">https://doi.org/10.3390/a14020043</identifier>
    <enrichment key="SourceTitle">Appeared in Algorithms 2021, 14(2), 43</enrichment>
    <author>Pedro Maristany de las Casas</author>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Ralf Borndörfer</author>
    <author>Luitgard Kraus</author>
    <author>Antonio Sedeño-Noda</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-31</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multiobjective Shortest Paths</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Time Dependent Shortest Paths</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multiobjective Approximation Algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Flight Planning Problem</value>
    </subject>
    <collection role="msc" number="90B99">None of the above, but in this section</collection>
    <collection role="msc" number="90C29">Multi-objective and goal programming</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <thesisPublisher>Zuse Institute Berlin (ZIB)</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-zib/files/8095/main.pdf</file>
  </doc>
  <doc>
    <id>8083</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>757</pageFirst>
    <pageLast>763</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Springer International Publishing</publisherName>
    <publisherPlace>Cham</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing</title>
    <abstract language="eng">The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2019</parentTitle>
    <identifier type="doi">https://doi.org/10.1007/978-3-030-48439-2_92</identifier>
    <identifier type="isbn">978-3-030-48438-5</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-73868</enrichment>
    <author>Fabian Löbel</author>
    <submitter>Niels Lindner</submitter>
    <editor>Janis S. Neufeld</editor>
    <author>Niels Lindner</author>
    <editor>Udo Buscher</editor>
    <author>Ralf Borndörfer</author>
    <editor>Rainer Lasch</editor>
    <editor>Dominik Möst</editor>
    <editor>Jörn Schönberger</editor>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="fabian.loebel">Löbel, Fabian</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="projects" number="MathPlus-Incubator-Timetabling">MathPlus-Incubator-Timetabling</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>8069</id>
    <completedYear>2021</completedYear>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst>1</pageFirst>
    <pageLast>15</pageLast>
    <pageNumber>15</pageNumber>
    <edition/>
    <issue/>
    <volume>002/127</volume>
    <type>article</type>
    <publisherName>FGSV</publisherName>
    <publisherPlace>Stuttgart</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-04-13</completedDate>
    <publishedDate>2021-04-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Ein  Graphen-basiertes  Modell  zur  Beschreibung  von Preissystemen im öffentlichen Nahverkehr</title>
    <abstract language="deu">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.</abstract>
    <parentTitle language="deu">HEUREKA 21</parentTitle>
    <identifier type="url">https://verlag.fgsv-datenbanken.de/tagungsbaende?kat=HEUREKA&amp;subkat=FGSV+002%2F127+%282021%29&amp;fanr=&amp;va=&amp;titel=&amp;text=&amp;autor=&amp;tagungsband=1256&amp;_titel=Ein+Graphen-basiertes+Modell+zur+Beschreibung+von+Preissystemen+im+%C3%B6ffentlichen+Nahverkehr</identifier>
    <enrichment key="Series">FGSV Heureka</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Ricardo Euler</submitter>
    <author>Ricardo Euler</author>
    <author>Marika Karbstein</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="projects" number="MOIN">MOIN</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>8041</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>42</pageFirst>
    <pageLast>62</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>51</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>Institute for Operations Research and the Management Sciences (INFORMS)</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-02-10</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Informs Journal on Applied Analytics</parentTitle>
    <identifier type="doi">10.1287/inte.2020.1069</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2020-11-05</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Ralf Borndörfer</submitter>
    <author>Thomas Eßer</author>
    <author>Patrick Frankenberger</author>
    <author>Andreas Huck</author>
    <author>Christoph Jobmann</author>
    <author>Boris Krostitz</author>
    <author>Karsten Kuchenbecker</author>
    <author>Kai Moorhagen</author>
    <author>Philipp Nagl</author>
    <author>Michael Peterson</author>
    <author>Markus Reuther</author>
    <author>Thilo Schang</author>
    <author>Michael Schoch</author>
    <author>Hanno Schülldorf</author>
    <author>Peter Schütz</author>
    <author>Tobias Therolf</author>
    <author>Kerstin Waas</author>
    <author>Steffen Weider</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="projects" number="MATHEON-B22">MATHEON-B22</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="ROTOR">ROTOR</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="EBUS">EBUS</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8039</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>102726</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>119</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Multi-period line planning with resource transfers</title>
    <abstract language="eng">Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.</abstract>
    <parentTitle language="eng">Transportation Research Part C: Emerging Technologies</parentTitle>
    <identifier type="doi">10.1016/j.trc.2020.102726</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2020-07-13</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-74662</enrichment>
    <submitter>Ralf Borndörfer</submitter>
    <author>Guvenc Sahin</author>
    <author>Amin Ahmadi</author>
    <author>Ralf Borndörfer</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="MathPlus-Incubator-Timetabling">MathPlus-Incubator-Timetabling</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7971</id>
    <completedYear>2021</completedYear>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-06-18</completedDate>
    <publishedDate>2021-06-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Improved Multiobjective Shortest Path Algorithm</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-79712</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Antonio Sedeno-Noda</author>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-26</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multiobjective Shortest Path Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Output-Sensitive Multiobjective Combinatorial Problems</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Network Optimization</value>
    </subject>
    <collection role="ccs" number="G.2">DISCRETE MATHEMATICS</collection>
    <collection role="msc" number="05C85">Graph algorithms [See also 68R10, 68W05]</collection>
    <collection role="msc" number="68R10">Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]</collection>
    <collection role="msc" number="90-02">Research exposition (monographs, survey articles)</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7971/main.pdf</file>
  </doc>
  <doc>
    <id>7702</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2020-02-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Solution Approach to the Vehicle Routing Problem with Perishable Goods</title>
    <abstract language="eng">This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date date, which may vary for different products. Storing products is prohibited.&#13;
Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e., temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-77020</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Mats Olthoff</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-03</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7702/ZR-20-03.pdf</file>
  </doc>
  <doc>
    <id>7701</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Solution Approach to the Vehicle Routing Problem with Perishable Goods</title>
    <abstract language="eng">This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date date, which may vary for different products. Storing products is prohibited. Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e.,&#13;
temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018.</abstract>
    <parentTitle language="eng">Operations Research 2019 Proceedings</parentTitle>
    <identifier type="urn">urn:nbn:de:0297-zib-77020</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="AcceptedDate">2019-12-13</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-77020</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Mats Olthoff</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7550</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2020-01-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance</title>
    <abstract language="eng">For providing railway services the company’s railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride&#13;
and it is often related to the image of the company itself. Thus, it is highly desired to&#13;
have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see Maroti and Kroon 2005, or Cordeau et. al. 2001 for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer&#13;
linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in Borndörfer et. al. 2015. The new approach is tested on real world instances modeling different scenarios&#13;
for the ICE high speed train network in Germany and compared to the approaches&#13;
of Reuther 2017 that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.</abstract>
    <parentTitle language="deu">19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)</parentTitle>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="doi">https://doi.org/10.4230/OASIcs.ATMOS.2019.1</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-75501</identifier>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-61</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7550/ZR-19-61.pdf</file>
  </doc>
  <doc>
    <id>7543</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1:1</pageFirst>
    <pageLast>1:12</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>75</volume>
    <type>conferenceobject</type>
    <publisherName>Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik</publisherName>
    <publisherPlace>Dagstuhl, Germany</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-09-14</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance</title>
    <abstract language="eng">For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Maróti and Kroon, 2005; Gábor Maróti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Borndörfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.</abstract>
    <parentTitle language="eng">19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2019.1</identifier>
    <identifier type="url">https://drops.dagstuhl.de/opus/volltexte/2019/11413/</identifier>
    <enrichment key="Series">OpenAccess Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">epub ahead of print</enrichment>
    <enrichment key="FulltextUrl">https://drops.dagstuhl.de/opus/volltexte/2019/11413/pdf/OASIcs-ATMOS-2019-1.pdf</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-75501</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <editor>Valentina Cacchiani</editor>
    <author>Ralf Borndörfer</author>
    <editor>Alberto Marchetti-Spaccamela</editor>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7509</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>12:1</pageFirst>
    <pageLast>12:15</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>75</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Graph- and Monoid-based Framework for Price-Sensitive Routing in Local Public Transportation Networks</title>
    <abstract language="eng">We present a novel framework to mathematically describe the fare systems of local public transit companies. The model allows the computation of a provably cheapest itinerary even if prices depend on a number of parameters and non-linear conditions. Our approach is based on a ticket graph model to represent tickets and their relation to each other. Transitions between tickets are modeled via transition functions over partially ordered monoids and a set of symbols representing special properties of fares (e.g. surcharges). Shortest path algorithms rely on the subpath optimality property. This property is usually lost when dealing with complicated fare systems. We restore it by relaxing domination rules for tickets depending on the structure of the ticket graph. An exemplary model for the fare system of Mitteldeutsche Verkehrsbetriebe (MDV) is provided. By integrating our framework in the multi-criteria RAPTOR algorithm we provide a price-sensitive algorithm for the earliest arrival problem and assess its performance on data obtained from MDV. We discuss three preprocessing techniques that improve run times enough to make the algorithm applicable for real-time queries.</abstract>
    <parentTitle language="eng">19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2019.12</identifier>
    <enrichment key="Series">OpenAccess Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Ricardo Euler</author>
    <submitter>Ricardo Euler</submitter>
    <author>Ralf Borndörfer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="projects" number="MOIN">MOIN</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7472</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>100175</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue>15</issue>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-12-14</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Concurrent Approach to the Periodic Event Scheduling Problem</title>
    <abstract language="eng">We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.</abstract>
    <parentTitle language="eng">Journal of Rail Transport Planning &amp; Management</parentTitle>
    <identifier type="issn">2210-9706</identifier>
    <identifier type="doi">10.1016/j.jrtpm.2019.100175</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-71907</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <author>Sarah Roth</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7471</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>100552</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue>35</issue>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-08-20</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Separation of cycle inequalities in periodic timetabling</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Discrete Optimization</parentTitle>
    <identifier type="doi">10.1016/j.disopt.2019.100552</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-69746</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Heide Hoppmann</author>
    <author>Marika Karbstein</author>
    <author>Niels Lindner</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="hoppmann">Hoppmann, Heide</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7466</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-09-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Multi-Period Line Planning with Resource Transfers</title>
    <abstract language="eng">Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with transfer of resources during a finite length planning horizon of multiple periods. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of line type designs and question the choice of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-74662</identifier>
    <author>Guvenc Sahin</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Amin Ahmadi</author>
    <author>Ralf Borndörfer</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-51</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7466/ZR-19-51.pdf</file>
  </doc>
  <doc>
    <id>7429</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-08-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Three-Phase Heuristic for Cyclic Crew Rostering with Fairness Requirements</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-74297</identifier>
    <author>Thomas Breugem</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Ralf Borndörfer</author>
    <author>Thomas Schlechte</author>
    <author>Christof Schulz</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-43</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Crew Planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Column Generation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Variable-Depth Neighborhood Search</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="schulz">Schulz, Christof</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7429/ZR-19-43.pdf</file>
  </doc>
  <doc>
    <id>7399</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>8</pageLast>
    <pageNumber/>
    <edition/>
    <issue>10</issue>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-03-16</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimization of handouts for rolling stock rotations</title>
    <abstract language="eng">A railway operator creates (rolling stock) rotations in order to have a precise master plan for the operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply traverses a set of operational days while covering trips of the timetable. As it is well known, the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging and still a topical research subject. Nevertheless, we study a completely different but strongly related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In our industrial application at DB Fernverkehr AG, the handout is exactly as important as the rotation itself. Moreover, it turns out that also other European railway operators use exactly the same methodology (but not terminology). Since a rotation can have many handouts of different quality, we show how to compute optimal ones through an integer program (IP) by standard software. In addition, a construction as well as an improvement heuristic are presented. Our computational results show that the heuristics are a very reliable standalone approach to quickly find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a computational comparison to the IP approach.</abstract>
    <parentTitle language="eng">Journal of Rail Transport Planning &amp; Management</parentTitle>
    <identifier type="doi">10.1016/j.jrtpm.2019.02.001</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2019-02-20</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-61430</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Boris Grimm</submitter>
    <author>Boris Grimm</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7398</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>160</pageFirst>
    <pageLast>168</pageLast>
    <pageNumber/>
    <edition/>
    <issue>069</issue>
    <volume>Linköping Electronic Conference Proceedings</volume>
    <type>conferenceobject</type>
    <publisherName>Linköping University Electronic Press, Linköpings universitet</publisherName>
    <publisherPlace>Linköping, Sweden</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-09-13</completedDate>
    <publishedDate>2019-06-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt</title>
    <abstract language="eng">Planning    rolling    stock    movements    in    industrial    passenger    railway    applications    isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for  the  ICE  high  speed  fleet  of  DB  Fernverkehr  AG  one  of  the  largest  passenger  railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended.</abstract>
    <parentTitle language="eng">Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019</parentTitle>
    <identifier type="issn">1650-3686</identifier>
    <identifier type="isbn">978-91-7929-992-7</identifier>
    <identifier type="url">http://www.ep.liu.se/ecp/article.asp?issue=069&amp;article=011&amp;volume=</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">epub ahead of print</enrichment>
    <enrichment key="AcceptedDate">2019-03-22</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-73976</enrichment>
    <enrichment key="FulltextUrl">http://www.ep.liu.se/ecp/069/011/ecp19069011.pdf</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Boris Grimm</submitter>
    <author>Boris Grimm</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7397</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-07-18</completedDate>
    <publishedDate>2019-07-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt</title>
    <abstract language="eng">Planning    rolling    stock    movements    in    industrial    passenger    railway    applications    isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for  the  ICE  high  speed  fleet  of  DB  Fernverkehr  AG  one  of  the  largest  passenger  railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73976</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-02</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>case study</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>re-optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway rolling stock optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7397/ZR-19-02.pdf</file>
  </doc>
  <doc>
    <id>7386</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-07-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing</title>
    <abstract language="eng">The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73868</identifier>
    <identifier type="doi">https://doi.org/https://doi.org/10.1007/978-3-030-48439-2_92</identifier>
    <author>Fabian Löbel</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-36</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Event Scheduling Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integrated Passenger Routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Shortest Routes in Public Transport</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="fabian.loebel">Löbel, Fabian</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7386/paper_OR19.pdf</file>
  </doc>
  <doc>
    <id>7367</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-06-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Approximating Balanced Graph Partitions</title>
    <abstract language="eng">We consider the problem of partitioning a weighted graph into k&#13;
connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a $\Delta$-approximation where $\Delta$ is the maximum degree of an arbitrary spanning tree of the given graph.&#13;
Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-73675</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Ziena Elijazyfer</author>
    <author>Stephan Schwartz</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-25</number>
    </series>
    <collection role="msc" number="05-XX">COMBINATORICS (For finite fields, see 11Txx)</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7367/ZR-19-25.pdf</file>
  </doc>
  <doc>
    <id>7190</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-02-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Concurrent Approach to the Periodic Event Scheduling Problem</title>
    <abstract language="eng">We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71907</identifier>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="AcceptedDate">2019-03-22</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <author>Sarah Roth</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-07</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Event Scheduling Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7190/concurrent-pesp.pdf</file>
  </doc>
  <doc>
    <id>7133</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-01-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Rolling Stock Rotation Planning Problem under Revenue Considerations</title>
    <abstract language="eng">In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period.  Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-71339</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Christof Schulz</author>
    <author>Steffen Weider</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-01</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schulz">Schulz, Christof</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7133/ZR-19-01.pdf</file>
  </doc>
  <doc>
    <id>7132</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Rolling Stock Rotation Planning Problem under Revenue Considerations</title>
    <abstract language="eng">In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period.  Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.</abstract>
    <parentTitle language="eng">Proceedings of the Rail Transport Demand Management Conference</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-71339</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Christof Schulz</author>
    <author>Steffen Weider</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schulz">Schulz, Christof</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6967</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2018-07-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Kombilösung: Optimierung des Liniennetzes in Karlsruhe</title>
    <abstract language="deu">Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-69677</identifier>
    <enrichment key="SourceTitle">Der Nahverkehr 1-2, p. 33-38, 2019</enrichment>
    <enrichment key="AcceptedDate">07.11.2018</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Ralf Borndörfer</submitter>
    <author>Ascan Egerer</author>
    <author>Marika Karbstein</author>
    <author>Ralf Messerschmidt</author>
    <author>Marc Perez</author>
    <author>Steven Pfisterer</author>
    <author>Petra Strauß</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-45</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>ÖPNV</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Linienplanung</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="pacs" number="00.00.00">GENERAL</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6967/ZR-18-45.pdf</file>
  </doc>
  <doc>
    <id>7075</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>687</pageFirst>
    <pageLast>692</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Springer International Publishing</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Demand-Driven Line Planning with Selfish Routing</title>
    <abstract language="eng">Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2017</parentTitle>
    <identifier type="doi">10.1007/978-3-319-89920-6_91</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-64547</enrichment>
    <author>Malte Renken</author>
    <submitter>Niels Lindner</submitter>
    <author>Amin Ahmadi</author>
    <author>Ralf Borndörfer</author>
    <author>Guvenc Sahin</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7074</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>16:1</pageFirst>
    <pageLast>16:15</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>65</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable</title>
    <abstract language="eng">We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [9], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.</abstract>
    <parentTitle language="eng">18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2018.16</identifier>
    <enrichment key="Series">OpenAccess Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-69688</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Marika Karbstein</author>
    <author>Christian Liebchen</author>
    <author>Niels Lindner</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7056</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2018-09-26</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Ein mathematisches Modell zur Beschreibung von Preissystemen im öV</title>
    <abstract language="deu">Dieses Dokument fasst den Stand der mathematischen Modellierung von&#13;
Preissystemen des öV mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen.  Damit sind sehr einfache und konzise&#13;
Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch&#13;
behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im&#13;
Routinggraphen im Tarifgraphen kann schon während einer Routenberechnung der Preis bestimmt werden.  Wir beschreiben&#13;
zunächst das Konzept. Die konkrete Realisierung wird im Folgenden&#13;
beispielhaft an den Tarifsystemen der Verkehrsverbünde Warnow,&#13;
MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erläutert. Anschließend folgen Überlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbundübergriffs.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-70564</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Ricardo Euler</submitter>
    <author>Ricardo Euler</author>
    <author>Marika Karbstein</author>
    <author>Fabian Mett</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-47</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="MOIN">MOIN</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7056/versionNeueNotation.pdf</file>
  </doc>
  <doc>
    <id>7002</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>2753</pageFirst>
    <pageLast>2761</pageLast>
    <pageNumber/>
    <edition/>
    <issue>10</issue>
    <volume>341</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Hall’s and Kőnig’s theorem in graphs and hypergraphs</title>
    <abstract language="eng">We investigate the relation between Hall’s theorem and Kőnig’s theorem in graphs and hypergraphs. In particular, we characterize the graphs satisfying a deficiency version of Hall’s theorem, thereby showing that this class strictly contains all Kőnig–Egerváry graphs. Furthermore, we give a generalization of Hall’s theorem to normal hypergraphs.</abstract>
    <parentTitle language="eng">Discrete Mathematics</parentTitle>
    <identifier type="doi">10.1016/j.disc.2018.06.013</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SourceTitle">Discrete Mathematics</enrichment>
    <enrichment key="AcceptedDate">2018-06-03</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-56175</enrichment>
    <author>Isabel Beckenbach</author>
    <submitter>Isabel Beckenbach</submitter>
    <author>Ralf Borndörfer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="beckenbach">Beckenbach, Isabel</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6974</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2018-07-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Separation of Cycle Inequalities in Periodic Timetabling</title>
    <abstract language="eng">Cycle inequalities play an important role in the polyhedral study of the periodic&#13;
timetabling problem. We give the first pseudo-polynomial time separation algo-&#13;
rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial&#13;
time separability of the change-cycle inequalities. Moreover, we provide several&#13;
NP-completeness results, indicating that pseudo-polynomial time is best possible.&#13;
The efficiency of these cutting planes is demonstrated on real-world instances of the&#13;
periodic timetabling problem.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-69746</identifier>
    <identifier type="doi">https://doi.org/10.1016/j.disopt.2019.100552</identifier>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="AcceptedDate">2019/08/13</enrichment>
    <enrichment key="SourceTitle">Discrete Optimization</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Heide Hoppmann</author>
    <author>Marika Karbstein</author>
    <author>Niels Lindner</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-16</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cycle inequality</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Change-cycle inequality</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6974/sepa_cycle.pdf</file>
  </doc>
  <doc>
    <id>6968</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2018-07-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable</title>
    <abstract language="eng">We consider the following planning problem in public transportation: Given a&#13;
periodic timetable, how many vehicles are required to operate it?&#13;
In [9], for this sequential approach, it is proposed to first expand the periodic&#13;
timetable over time, and then answer the above question by solving a flow-based&#13;
aperiodic optimization problem.&#13;
In this contribution we propose to keep the compact periodic representation of&#13;
the timetable and simply solve a particular perfect matching problem. For practical&#13;
networks, it is very much likely that the matching problem decomposes into several&#13;
connected components. Our key observation is that there is no need to change any&#13;
turnaround decision for the vehicles of a line during the day, as long as the timetable&#13;
stays exactly the same.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-69688</identifier>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2018.16</identifier>
    <enrichment key="SourceTitle">appeared in: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Marika Karbstein</author>
    <author>Christian Liebchen</author>
    <author>Niels Lindner</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-38</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Vehicle scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bipartite matching</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6968/PeriodicVehicleScheduling.pdf</file>
  </doc>
  <doc>
    <id>6958</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>420</pageFirst>
    <pageLast>435</pageLast>
    <pageNumber/>
    <edition/>
    <issue>2</issue>
    <volume>271</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations</title>
    <abstract language="eng">The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects&#13;
and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution,&#13;
and a fixed assignment of jobs to machines must be computed.&#13;
We propose a cutting-plane approach to solve the robust counterpart of this optimization problem.&#13;
To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities.&#13;
The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions.&#13;
We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which&#13;
only approximation approaches were known. Our model can&#13;
be extended to balance the load over several planning periods in a rolling horizon.&#13;
We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that:&#13;
(i) our approach performs well compared to a previous model that ignored the distribution of case durations; &#13;
(ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost;&#13;
(iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available.&#13;
Finally, we draw a number of managerial implications from these observations.</abstract>
    <parentTitle language="eng">European Journal of Operational Research</parentTitle>
    <identifier type="doi">10.1016/j.ejor.2018.05.022</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-58502</enrichment>
    <author>Guillaume Sagnol</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Christoph Barner</author>
    <author>Ralf Borndörfer</author>
    <author>Mickaël Grima</author>
    <author>Mathes Seeling</author>
    <author>Claudia Spies</author>
    <author>Klaus Wernecke</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="projects" number="Charité-OPOSSUM">Charité-OPOSSUM</collection>
    <collection role="projects" number="BMBF-IBOSS">BMBF-IBOSS</collection>
    <collection role="institutes" number="healthcare">Mathematics of Health Care</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6929</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>35</pageFirst>
    <pageLast>44</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>64</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Graph Segmentation Problem</title>
    <abstract language="eng">We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.</abstract>
    <parentTitle language="eng">INOC 2017 – 8th International Network Optimization Conference</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="Series">Electronic Notes in Discrete Mathematics</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-60750</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Stephan Schwartz</author>
    <author>Gerald Bartz</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6927</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>355</pageFirst>
    <pageLast>360</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Springer International Publishing</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On Finding Subpaths With High Demand</title>
    <abstract language="eng">We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. &#13;
Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. &#13;
Our runtime analysis shows, that the presented approach compares very well against the  theoretical minimum runtime.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2017</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-69280</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Stephan Schwartz</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Ralf Borndörfer</author>
    <author>Leonardo Balestrieri</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6928</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2018-06-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On Finding Subpaths With High Demand</title>
    <abstract language="eng">We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. &#13;
Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. &#13;
Our runtime analysis shows, that the presented approach compares very well against the &#13;
theoretical minimum runtime.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-69280</identifier>
    <enrichment key="SourceTitle">Operations Research 2017</enrichment>
    <author>Stephan Schwartz</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Leonardo Balestrieri</author>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-27</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6928/ZR-18-27.pdf</file>
  </doc>
  <doc>
    <id>6764</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>723</pageFirst>
    <pageLast>728</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Springer International Publishing</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Timetable Sparsification by Rolling Stock Rotation Optimization</title>
    <abstract language="eng">Rolling stock optimization is a task that naturally arises by operating a railway system. It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike. Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data.</abstract>
    <parentTitle language="eng">Operations Research 2017</parentTitle>
    <identifier type="doi">10.1007/978-3-319-89920-6_96</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-65948</enrichment>
    <enrichment key="AcceptedDate">2017-11-01</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Stanley Schade</submitter>
    <author>Matthias Breuer</author>
    <author>Boris Grimm</author>
    <author>Markus Reuther</author>
    <author>Stanley Schade</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6594</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2017-11-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Timetable Sparsification by Rolling Stock Rotation Optimization</title>
    <abstract language="eng">Rolling stock optimization is a task that naturally arises by operating a railway system.&#13;
It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike. &#13;
Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-65948</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Boris Grimm</submitter>
    <author>Matthias Breuer</author>
    <author>Boris Grimm</author>
    <author>Markus Reuther</author>
    <author>Stanley Schade</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-63</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6594/ZR-17-63.pdf</file>
  </doc>
  <doc>
    <id>6491</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>235</pageFirst>
    <pageLast>241</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Line Planning on Path Networks with Application to the Istanbul Metrobüs</title>
    <abstract language="eng">Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated&#13;
which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) ``unimodal demand'' case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrobüs system of Istanbul is discussed.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2016</parentTitle>
    <identifier type="doi">10.1007/978-3-319-55702-1_32</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-60119</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Oytun Arslan</author>
    <author>Ziena Elijazyfer</author>
    <author>Hakan Güler</author>
    <author>Malte Renken</author>
    <author>Guvenc Sahin</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6489</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>59</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Cost Projection Methods for the Shortest Path Problem with Crossing Costs</title>
    <abstract language="eng">Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.</abstract>
    <parentTitle language="deu">17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-64817</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <editor>Gianlorenzo D'Angelo</editor>
    <submitter>Thomas Schlechte</submitter>
    <author>Marco Blanco</author>
    <editor>Twan Dollevoet</editor>
    <author>Ralf Borndörfer</author>
    <author>Nam-Dung Hoang</author>
    <author>Anton Kaier</author>
    <author>Pedro Maristany de las Casas</author>
    <author>Thomas Schlechte</author>
    <author>Swen Schlobach</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6481</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2017-08-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Cost Projection Methods for the Shortest Path Problem with Crossing Costs</title>
    <abstract language="eng">Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-64817</identifier>
    <enrichment key="FulltextUrl">Appeared in: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)</enrichment>
    <author>Marco Blanco</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Ralf Borndörfer</author>
    <author>Nam-Dung Hoang</author>
    <author>Anton Kaier</author>
    <author>Pedro Maristany de las Casas</author>
    <author>Thomas Schlechte</author>
    <author>Swen Schlobach</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-48</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6481/ZR-17-48.pdf</file>
  </doc>
  <doc>
    <id>6454</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2017-07-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Demand-Driven Line Planning with Selfish Routing</title>
    <abstract language="eng">Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-64547</identifier>
    <identifier type="doi">10.1007/978-3-319-89920-6_91</identifier>
    <enrichment key="SourceTitle">appeared in: Operations Research Proceedings 2017</enrichment>
    <author>Malte Renken</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Amin Ahmadi</author>
    <author>Ralf Borndörfer</author>
    <author>Guvenc Sahin</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-38</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6454/ZR-17-38.pdf</file>
  </doc>
  <doc>
    <id>6436</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Propagation Approach to Acyclic Rolling Stock Rotation Optimization</title>
    <abstract language="eng">The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.</abstract>
    <parentTitle language="eng">Proceedings of the IAROR conference RailLille</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-63930</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Markus Reuther</author>
    <author>Stanley Schade</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6432</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Pattern Detection For Large-Scale Railway Timetables</title>
    <abstract language="eng">We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.</abstract>
    <parentTitle language="eng">Proceedings of the IAROR conference RailLille</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-63390</enrichment>
    <author>Stanley Schade</author>
    <submitter>Stanley Schade</submitter>
    <author>Ralf Borndörfer</author>
    <author>Matthias Breuer</author>
    <author>Boris Grimm</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <author>Patrick Siebeneicher</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6407</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2017-03-22</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Umsteigen ohne Warten</title>
    <abstract language="deu">Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrplänen vor, bei dem die Umsteigezeiten unter Berücksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Beförderungsqualität.</abstract>
    <parentTitle language="deu">HEUREKA 2017</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">epub ahead of print</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-62006</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Marika Karbstein</submitter>
    <author>Heide Hoppmann</author>
    <author>Marika Karbstein</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="hoppmann">Hoppmann, Heide</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6393</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2017-05-05</completedDate>
    <publishedDate>2017-05-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Propagation Approach to Acyclic Rolling Stock Rotation Optimization</title>
    <abstract language="eng">The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the&#13;
 timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-63930</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the IAROR conference RailLille 2017</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Markus Reuther</author>
    <author>Stanley Schade</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-24</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6393/ZR-17-24.pdf</file>
  </doc>
  <doc>
    <id>6339</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2017-11-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Pattern Detection For Large-Scale Railway Timetables</title>
    <abstract language="eng">We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-63390</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the IAROR conference RailLille 2017</enrichment>
    <author>Stanley Schade</author>
    <submitter>Stanley Schade</submitter>
    <author>Ralf Borndörfer</author>
    <author>Matthias Breuer</author>
    <author>Boris Grimm</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <author>Patrick Siebeneicher</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-17</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway timetables</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>visualization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>pattern detection</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6339/ZR-17-17.pdf</file>
  </doc>
  <doc>
    <id>6200</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2017-02-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Umsteigen ohne Warten</title>
    <abstract language="deu">Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrplänen vor, bei dem die Umsteigezeiten unter&#13;
Berücksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Beförderungsqualität.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-62006</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Marika Karbstein</submitter>
    <author>Heide Hoppmann</author>
    <author>Marika Karbstein</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-05</number>
    </series>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90B20">Traffic problems</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="hoppmann">Hoppmann, Heide</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6200/ZR_17-05.pdf</file>
  </doc>
  <doc>
    <id>6188</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>239</pageFirst>
    <pageLast>253</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>bookpart</type>
    <publisherName>Springer International Publishing</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimisation Methods in Sustainable Manufacturing</title>
    <abstract language="eng">Sustainable manufacturing is driven by the insight that the focus on the economic dimension in current businesses and lifestyles has to be broadened to cover all three pillars of sustainability: economic development, social development, and environmental protection.</abstract>
    <parentTitle language="eng">Sustainable Manufacturing</parentTitle>
    <subTitle language="eng">Challenges, Solutions and Implementation Perspectives</subTitle>
    <identifier type="isbn">978-3-319-48514-0</identifier>
    <identifier type="doi">10.1007/978-3-319-48514-0_15</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Sebastian Schenker</author>
    <submitter>Sebastian Schenker</submitter>
    <editor>Rainer Stark</editor>
    <author>Ingmar Vierhaus</author>
    <editor>Günther Seliger</editor>
    <author>Ralf Borndörfer</author>
    <editor>Jérémy Bonvoisin</editor>
    <author>Armin Fügenschuh</author>
    <author>Martin Skutella</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="fuegenschuh">Fügenschuh, Armin</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="CRC1026">CRC1026</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6183</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>19</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName>Springer</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Template-based Re-optimization of Rolling Stock Rotations</title>
    <abstract language="eng">Rolling stock, i.e., the set of railway vehicles, is among the most&#13;
expensive and limited assets of a railway company and must be used&#13;
efficiently. We consider in this paper the re-optimization&#13;
problem to recover from unforeseen disruptions. We propose a&#13;
template concept that allows to recover cost minimal rolling&#13;
stock rotations from reference rotations under a large variety of&#13;
operational requirements. To this end, connection templates as&#13;
well as rotation templates are introduced and their&#13;
application within a rolling stock rotation planning model is&#13;
discussed. We present an implementation within the rolling stock rotation&#13;
optimization framework rotor and computational results for&#13;
scenarios provided by DB Fernverkehr AG, one of the &#13;
leading railway operators in Europe.</abstract>
    <parentTitle language="eng">Public Transport</parentTitle>
    <identifier type="doi">10.1007/s12469-017-0152-4</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Boris Grimm</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="ROTOR">ROTOR</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>6143</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2016-12-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimization of Handouts for Rolling Stock Rotations Visualization</title>
    <abstract language="eng">A railway operator creates (rolling stock) rotations in order to have a precise master plan for the&#13;
operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply&#13;
traverses a set of operational days while covering trips of the timetable. As it is well known,&#13;
the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging&#13;
and still a topical research subject. Nevertheless, we study a completely different but strongly&#13;
related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce&#13;
a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In&#13;
our industrial application at DB Fernverkehr AG, the handout is exactly as important as the&#13;
rotation itself. Moreover, it turns out that also other European railway operators use exactly the&#13;
same methodology (but not terminology). Since a rotation can have many handouts of different&#13;
quality, we show how to compute optimal ones through an integer program (IP) by standard&#13;
software. In addition, a construction as well as an improvement heuristic are presented. Our&#13;
computational results show that the heuristics are a very reliable standalone approach to quickly&#13;
find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a&#13;
computational comparison to the IP approach.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-61430</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Boris Grimm</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>ZR-16-73</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="ROTOR">ROTOR</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6143/ZR-16-73.pdf</file>
  </doc>
  <doc>
    <id>6137</id>
    <completedYear/>
    <publishedYear>2016</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>28</pageFirst>
    <pageLast>32</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>8</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Regularity patterns for rolling stock rotation optimization</title>
    <abstract language="eng">The operation of railways gives rise to many fundamental optimization problems. One of these problems is to cover a given set of timetabled trips by a set of rolling stock rotations. This is well known as the Rolling Stock Rotation Problem (RSRP). Most approaches in the literature focus primarily on modeling and minimizing the operational costs. However, an essential aspect for the industrial application is mostly neglected. As the RSRP follows timetabling and line planning, where periodicity is a highly desired property, it is also desired to carry over periodic structures to rolling stock rotations and following operations. We call this complex requirement regularity. Regularity turns out to be of essential interest, especially in the industrial scenarios that we tackle in cooperation with DB Fernverkehr AG. Moreover, regularity in the context of the RSRP has not been investigated thoroughly in the literature so far. We introduce three regularity patterns to tackle this requirement, namely regular trips, regular turns, and regular handouts. We present a two-stage approach in order to optimize all three regularity patterns. At first, we integrate regularity patterns into an integer programming approach for the minimization of the operational cost of rolling stock rotations. Afterwards regular handouts are computed. These handouts present the rotations of the first stage in the most regular way. Our computational results (i.e., rolling stock rotations evaluated by planners of DB Fernverkehr AG) show that the three regularity patterns and our concept are a valuable and, moreover, an essential contribution to rolling stock rotation optimization.</abstract>
    <parentTitle language="eng">8th International Conference on Applied Operational Research, Proceedings</parentTitle>
    <enrichment key="Series">Lecture Notes in Management Science</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <author>Stanley Schade</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
</export-example>
