Search Results

Documents authored by Weider, Steffen

Document
DOI: 10.4230/OASIcs.ATMOS.2024.11
Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach

Authors: Ralf Borndörfer, Andreas Löbel, Fabian Löbel, and Steffen Weider

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
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.
Cite as

Ralf Borndörfer, Andreas Löbel, Fabian Löbel, and Steffen Weider. Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2024.11,
  author =	{Bornd\"{o}rfer, Ralf and L\"{o}bel, Andreas and L\"{o}bel, Fabian and Weider, Steffen},
  title =	{{Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{11:1--11:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.11},
  URN =		{urn:nbn:de:0030-drops-211992},
  doi =		{10.4230/OASIcs.ATMOS.2024.11},
  annote =	{Keywords: Electric Bus Scheduling, Electric Vehicle Scheduling, Non-linear Charging, Multi-commodity Flow, Set Partition, Lagrangian Relaxation, Proximal Bundle Method}
}
Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2023.15
Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates (Short Paper)

Authors: Fabian Löbel, Ralf Borndörfer, and Steffen Weider

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
The ongoing electrification of logistics systems and vehicle fleets increases the complexity of associated vehicle routing or scheduling problems. Battery-powered vehicles have to be scheduled to recharge in-service, and the relationship between charging time and replenished driving range is non-linear. In order to access the powerful toolkit offered by mixed-integer and linear programming techniques, this battery behavior has to be linearized. 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. 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.
Cite as

Fabian Löbel, Ralf Borndörfer, and Steffen Weider. Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 15:1-15:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lobel_et_al:OASIcs.ATMOS.2023.15,
  author =	{L\"{o}bel, Fabian and Bornd\"{o}rfer, Ralf and Weider, Steffen},
  title =	{{Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{15:1--15:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.15},
  URN =		{urn:nbn:de:0030-drops-187765},
  doi =		{10.4230/OASIcs.ATMOS.2023.15},
  annote =	{Keywords: Electric Vehicle Scheduling, Battery Powered Vehicles, Charging Process, Non-linear Charging, Recharge Modeling, Dynamic Recharge Rate}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.146
A Hypergraph Model for Railway Vehicle Rotation Planning

Authors: Ralf Borndörfer, Markus Reuther, Thomas Schlechte, and Steffen Weider

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the "regularity" of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.
Cite as

Ralf Borndörfer, Markus Reuther, Thomas Schlechte, and Steffen Weider. A Hypergraph Model for Railway Vehicle Rotation Planning. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 146-155, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2011.146,
  author =	{Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen},
  title =	{{A Hypergraph Model for Railway Vehicle Rotation Planning}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{146--155},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.146},
  URN =		{urn:nbn:de:0030-drops-32746},
  doi =		{10.4230/OASIcs.ATMOS.2011.146},
  annote =	{Keywords: Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.13
Railway Track Allocation by Rapid Branching

Authors: Ralf Borndörfer, Thomas Schlechte, and Steffen Weider

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.
Cite as

Ralf Borndörfer, Thomas Schlechte, and Steffen Weider. Railway Track Allocation by Rapid Branching. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 13-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2010.13,
  author =	{Bornd\"{o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen},
  title =	{{Railway Track Allocation by Rapid Branching}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{13--23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.13},
  URN =		{urn:nbn:de:0030-drops-27465},
  doi =		{10.4230/OASIcs.ATMOS.2010.13},
  annote =	{Keywords: track allocation problem, integer programming, rapid branching heuristic, proximal bundle method}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact