4 Search Results for "Irnich, Stefan"

Document
DOI: 10.4230/OASIcs.ATMOS.2025.17
The Line-Based Dial-a-Ride Problem with Transfers

Authors: Jonas Barth, Kendra Reiter, and Marie Schmidt

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
We introduce the line-based dial-a-ride problem with transfers (liDARPT), a variation of the well-studied dial-a-ride problem (DARP), where vehicles transport requests on-demand but are constrained to operate along a set of lines, and passengers are allowed to transfer between lines on their journey. We develop an event-based solution approach for the liDARPT that relies on the construction of an event-based graph and uses a MILP to find optimal circulations in the event-based graph. To make this solution approach effective, we devise a pre-processing routine to limit the size of the event-based graph. We extensively test our approach on novel benchmark instances, inspired by real-life long-distance bus networks. In our experiments, problem instances with up to 80 requests can be solved to optimality within 15 minutes, and an average of 99.69% of requests are accepted in all instances solved to optimality.
Cite as

Jonas Barth, Kendra Reiter, and Marie Schmidt. The Line-Based Dial-a-Ride Problem with Transfers. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:OASIcs.ATMOS.2025.17,
  author =	{Barth, Jonas and Reiter, Kendra and Schmidt, Marie},
  title =	{{The Line-Based Dial-a-Ride Problem with Transfers}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{17:1--17:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.17},
  URN =		{urn:nbn:de:0030-drops-247736},
  doi =		{10.4230/OASIcs.ATMOS.2025.17},
  annote =	{Keywords: dial-a-ride, line-based, transfers, on-demand, ridepooling}
}
Artifact
Software
DOI: 10.4230/artifacts.23820
ng-arb implementation and MPCST

Authors: Luzie Marianczuk

Abstract
Cite as

Luzie Marianczuk. ng-arb implementation and MPCST (Software, Implementation). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23820,
   title = {{ng-arb implementation and MPCST}}, 
   author = {Marianczuk, Luzie},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:554ff8afbd05550498b755c3de500300f5f2a233}{\texttt{swh:1:dir:554ff8afbd05550498b755c3de500300f5f2a233}} (visited on 2025-07-15)},
   url = {https://gitlab.rlp.net/lumarian/ng-arbs},
   doi = {10.4230/artifacts.23820},
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.24
A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees

Authors: Luzie Marianczuk, Ernst Althaus, Stefan Irnich, and Marc E. Pfetsch

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
In this paper, we investigate lower bounds of tree-based optimization problems in order to obtain effective exact algorithms, such as branch-and-bound algorithms. Our new approach inherits the development of dynamic programming algorithms for constrained shortest path problems, as they occur as subproblems in Lagrangian relaxation algorithms and column generation-based algorithms for variants of the Vehicle Routing Problem. In the q-route relaxation, paths must satisfy a capacity constraint while the elementarity constraint is relaxed, that is, paths may contain cycles. An analogue of q-routes for tree optimization problems are q-arbs, a structure that relaxes elementarity for arborescences. We introduce a generalized formulation of q-arbs for a broad class of tree-based problems, and apply the neighborhood restrictions of so-called ng-routes to them to obtain tighter bounds. We apply the new dynamic programming approach to the Minimum Power-Cost Spanning Tree Problem and show empirically that the resulting bounds are often better than traditional LP-based lower bounds of (mixed) integer programming models.
Cite as

Luzie Marianczuk, Ernst Althaus, Stefan Irnich, and Marc E. Pfetsch. A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marianczuk_et_al:LIPIcs.SEA.2025.24,
  author =	{Marianczuk, Luzie and Althaus, Ernst and Irnich, Stefan and Pfetsch, Marc E.},
  title =	{{A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.24},
  URN =		{urn:nbn:de:0030-drops-232620},
  doi =		{10.4230/LIPIcs.SEA.2025.24},
  annote =	{Keywords: lower bounds, symmetric connectivity, power range assignment, dynamic programming, optimal substructure}
}
Document
DOI: 10.4230/DagSemProc.09261.18
New Models and Methods for Arc Routing

Authors: Stefan Irnich

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

Abstract
The talk presents two non-standard extensions for single-vehicle arc-routing problems a.k.a. postman problems: First, street segments that require a service on both sides of the street can be covered either by two separate services or by a single zigzag service. Instead of deciding the type of service beforehand, we propose to take into account the zigzagging option when designing a tour. We present MIP models for the extension of Undirected Chinese and Rural Postman Problem (UCPP, URPP). We show that these models can be solved reasonable well using a cutting-plane or branch-and-cut algorithm. Second, capacitated postman problems occur as subproblems in column-generation and Lagrangian-relaxation approaches of the capacitated arc-routing problem. In order to model these and similar subproblems or submodels, we present the Profitable Capacitated Rural Postman Problem (PCRPP): In the PCRPP, edges that are serviced give a profit, but deadheading through edges generates costs. Both service and deadheading consume time. The task is to find a tour that maximizes the difference of profits and costs, while the overall duration of the tour must not exceed a given bound. The solution approach for this problem is again based on branch-and-cut.
Cite as

Stefan Irnich. New Models and Methods for Arc Routing. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{irnich:DagSemProc.09261.18,
  author =	{Irnich, Stefan},
  title =	{{New Models and Methods for Arc Routing}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.18},
  URN =		{urn:nbn:de:0030-drops-21635},
  doi =		{10.4230/DagSemProc.09261.18},
  annote =	{Keywords: Postman problems, branch-and-cut}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Artifact
  • 1 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2009

  • Refine by Author
  • 2 Irnich, Stefan
  • 2 Marianczuk, Luzie
  • 1 Althaus, Ernst
  • 1 Barth, Jonas
  • 1 Pfetsch, Marc E.
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 OASIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Trees
  • 1 Theory of computation → Dynamic programming

  • Refine by Keyword
  • 1 Postman problems
  • 1 branch-and-cut
  • 1 dial-a-ride
  • 1 dynamic programming
  • 1 line-based
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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