Search Results

Documents authored by Schmidt, Christiane

Document
DOI: 10.4230/OASIcs.ATMOS.2026.5
Dispatching-Area Design

Authors: Tomas Lidén, Christiane Schmidt, and Rabii Zahir

Published in: OASIcs, Volume 147, 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)

Abstract
Increasing traffic density and system interdependencies in railway networks can lead to imbalanced workload distribution among train dispatchers. Traditional dispatching-area design, often based on historical and geographical considerations, may no longer reflect current infrastructure complexity and coordination requirements, potentially affecting punctuality and operational robustness. In this paper, we study the problem of partitioning a set of train stations into a predefined number of dispatching areas, formulated as a multi-objective mixed-integer programming problem. The objective is to minimize a weighted sum of inter-area interaction complexity and intra-area operational complexity. Inter-area complexity captures coordination needs through the number of trains crossing area boundaries, while intra-area complexity is modeled using station-related parameters, including track layout, traffic density, starting and ending services, and traffic heterogeneity (mix of passenger and freight traffic). We apply the suggested approach to instances from the Malmö dispatching center in the southern part of the Swedish railway network, illustrating how an optimization-grounded sectorization framework can support structured and balanced redesign of dispatching areas. We evaluate the model’s robustness by through sensitivity analyses on objective weights, minimum area size, and the number of dispatching areas. These analyses provide insights into how different planning priorities influence the resulting sectorization.
Cite as

Tomas Lidén, Christiane Schmidt, and Rabii Zahir. Dispatching-Area Design. In 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026). Open Access Series in Informatics (OASIcs), Volume 147, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liden_et_al:OASIcs.ATMOS.2026.5,
  author =	{Lid\'{e}n, Tomas and Schmidt, Christiane and Zahir, Rabii},
  title =	{{Dispatching-Area Design}},
  booktitle =	{26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)},
  pages =	{5:1--5:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-453-6},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{147},
  editor =	{Cacchiani, Valentina and Funke, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2026.5},
  URN =		{urn:nbn:de:0030-drops-278018},
  doi =		{10.4230/OASIcs.ATMOS.2026.5},
  annote =	{Keywords: Railway sectorization, Area design, Train dispatching}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2026.81
Segment Watchman Routes

Authors: Anna Brötzner, Omrit Filtser, Bengt J. Nilsson, Christian Rieck, and Christiane Schmidt

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon P is seen from more than one direction: we search for two routes W₁,W₂, such that every point p ∈ P is contained in a segment w₁w₂ ⊆ P such that w₁ ∈ W₁ and w₂ ∈ W₂. We call such routes segment watchman routes. We show that finding the two routes that are optimal with respect to the min-max criterion is weakly NP-hard even in simple polygons, and that finding the routes that are optimal with respect to the min-sum criterion is NP-hard in polygons with holes. Moreover, we present sufficient conditions for routes to be segment watchman routes, and provide a polynomial-time 2-approximation under both the min-max criterion and the min-sum criterion, both in simple polygons. Finally, we show how to generalize our results for k watchmen.
Cite as

Anna Brötzner, Omrit Filtser, Bengt J. Nilsson, Christian Rieck, and Christiane Schmidt. Segment Watchman Routes. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 81:1-81:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brotzner_et_al:LIPIcs.MFCS.2026.81,
  author =	{Br\"{o}tzner, Anna and Filtser, Omrit and Nilsson, Bengt J. and Rieck, Christian and Schmidt, Christiane},
  title =	{{Segment Watchman Routes}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{81:1--81:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.81},
  URN =		{urn:nbn:de:0030-drops-274634},
  doi =		{10.4230/LIPIcs.MFCS.2026.81},
  annote =	{Keywords: Watchman routes, segment guarding, k-hull guarding, NP-hardness, approximation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.11
Improved Approximation of Two Watchmen’s Routes in Simple Polygons

Authors: Anna Brötzner, Bengt J. Nilsson, and Christiane Schmidt

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study the watchman route problem for a set of two watchmen for the objective of minimizing the length of the longest route (min-max) inside a simple polygon P having n vertices, which is known to be weakly NP-hard. First, we consider seeing a discrete set of m points in the interior of P. We show that even this problem is weakly NP-hard and present an approximation algorithm with approximation ratio 2+ε that runs in O(m⁵n) time, assuming that a starting point for each of the two routes is given. We generalize the algorithm to see all of the interior of P in O(n⁶) time with approximation ratio 2 + π/2 ≈ 3.571, improving on the previously known best algorithm that has an approximation ratio of ≈ 6.922 and runtime O(n²) [Bengt J. Nilsson and Eli Packer, 2024]. Finally, we describe how to extend this algorithm to the case where no starting points are given, this taking O(n⁸) time, yielding an approximation ratio of 3 + π/2 ≈ 4.571, improving on the previously known best approximation algorithm with ratio ≈ 5.969 also having runtime O(n⁸) [Bengt J. Nilsson and Eli Packer, 2024].
Cite as

Anna Brötzner, Bengt J. Nilsson, and Christiane Schmidt. Improved Approximation of Two Watchmen’s Routes in Simple Polygons. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brotzner_et_al:LIPIcs.SWAT.2026.11,
  author =	{Br\"{o}tzner, Anna and Nilsson, Bengt J. and Schmidt, Christiane},
  title =	{{Improved Approximation of Two Watchmen’s Routes in Simple Polygons}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.11},
  URN =		{urn:nbn:de:0030-drops-260472},
  doi =		{10.4230/LIPIcs.SWAT.2026.11},
  annote =	{Keywords: Art gallery problem, watchman route problem, multiple watchmen, path planning, polygons}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.6
Two-Stage Weekly Shift Scheduling for Train Dispatchers

Authors: Tomas Lidén, Christiane Schmidt, and Rabii Zahir

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

Abstract
We consider the problem of creating weekly shift schedules for train dispatchers, which conform to a variety of operational constraints, in particular, several work and rest time restrictions. We create the schedules in a two-stage process. First, using a previously presented IP model, we create a set of feasible daily shifts, which takes care of minimum-rest and shift-length requirements, taskload bounds, and combinability of dispatching areas. We then formulate an IP model to combine these daily shifts into weekly schedules, enforcing that each daily shift is covered by some dispatcher every day of the week, while ensuring that the weekly schedules comply with various restrictions on working hours from a union agreement. With this approach, we aim to identify "good" sets of daily shifts for the longer schedules. We run experiments for real-world sized input and consider different distributions of the daily shifts w.r.t. shift length and ratio of night shifts. Daily shifts with shift-length variability, relatively few long shifts, and a low ratio of night shifts generally yield better weekly schedules. The runtime for the second stage with the best daily-shift pattern is below three hours, which - together with the runtime for stage 1 of ca. 2 hours per run - can be feasible for real-world use.
Cite as

Tomas Lidén, Christiane Schmidt, and Rabii Zahir. Two-Stage Weekly Shift Scheduling for Train Dispatchers. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liden_et_al:OASIcs.ATMOS.2024.6,
  author =	{Lid\'{e}n, Tomas and Schmidt, Christiane and Zahir, Rabii},
  title =	{{Two-Stage Weekly Shift Scheduling for Train Dispatchers}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{6:1--6: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.6},
  URN =		{urn:nbn:de:0030-drops-211944},
  doi =		{10.4230/OASIcs.ATMOS.2024.6},
  annote =	{Keywords: shift scheduling, IP, train dispatcher shift scheduling}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.9
Automatic Design of Aircraft Arrival Routes with Limited Turning Angle

Authors: Tobias Andersson Granberg, Tatiana Polishchuk, Valentin Polishchuk, and Christiane Schmidt

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
We present an application of Integer Programming to the design of arrival routes for aircraft in a Terminal Maneuvering Area (TMA). We generate operationally feasible merge trees of curvature-constrained routes, using two optimization criteria: (1) total length of the tree, and (2) distance flown along the tree paths. The output routes guarantee that the overall traffic pattern in the TMA can be monitored by air traffic controllers; in particular, we keep merge points for arriving aircraft well separated, and we exclude conflicts between arriving and departing aircraft. We demonstrate the feasibility of our method by experimenting with arrival routes for a runway at Arlanda airport in the Stockholm TMA. Our approach can easily be extended in several ways, e.g., to ensure that the routes avoid no-fly zones.
Cite as

Tobias Andersson Granberg, Tatiana Polishchuk, Valentin Polishchuk, and Christiane Schmidt. Automatic Design of Aircraft Arrival Routes with Limited Turning Angle. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{granberg_et_al:OASIcs.ATMOS.2016.9,
  author =	{Granberg, Tobias Andersson and Polishchuk, Tatiana and Polishchuk, Valentin and Schmidt, Christiane},
  title =	{{Automatic Design of Aircraft Arrival Routes with Limited Turning Angle}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{9:1--9:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.9},
  URN =		{urn:nbn:de:0030-drops-65336},
  doi =		{10.4230/OASIcs.ATMOS.2016.9},
  annote =	{Keywords: Air Traffic Management, Standard Terminal Arrival Routes, Standard Instrument Departures, Integer programming, Turn constraints}
}
Document
DOI: 10.4230/DagSemProc.06421.8
Polygon Exploration with Discrete Vision

Authors: Sándor Fekete and Christiane Schmidt

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract
With the advent of autonomous robots with two- and three-dimensional scanning capabilities, classical visibility-based exploration methods from computational geometry have gained in practical importance. However, real-life laser scanning of useful accuracy does not allow the robot to scan continuously while in motion; instead, it has to stop each time it surveys its environment. This requirement was studied by Fekete, Klein and N"uchter for the subproblem of looking around a corner, but until now has not been considered for whole polygonal regions. We give the first comprehensive algorithmic study for this important algorithmic problem that combines stationary art gallery-type aspects with watchman-type issues in an online scenario. We show that there is a lower bound of $Omega(sqrt{n})$ on the competitive ratio in an orthogonal polygon with holes; we also demonstrate that even for orthoconvex polygons, a competitive strategy can only be achieved for limited aspect ratio $A$, i.e., for a given lower bound on the size of an edge. Our main result is an $O(log A)$-competitive strategy for simple rectilinear polygons, which is best possible up to constants.
Cite as

Sándor Fekete and Christiane Schmidt. Polygon Exploration with Discrete Vision. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.8,
  author =	{Fekete, S\'{a}ndor and Schmidt, Christiane},
  title =	{{Polygon Exploration with Discrete Vision}},
  booktitle =	{Robot Navigation},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.8},
  URN =		{urn:nbn:de:0030-drops-8714},
  doi =		{10.4230/DagSemProc.06421.8},
  annote =	{Keywords: Searching, scan cost, visibility problems, watchman problems, online searching, competitive strategies, autonomous mobile robots.}
}

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