2 Search Results for "van Lieshout, Rolf N."

Document

DOI: 10.4230/OASIcs.ATMOS.2025.1

The Fair Periodic Assignment Problem

Authors: Rolf Nelson van Lieshout and Bartholomeüs Theodorus Cornelis van Rossum

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

Abstract

We study the periodic assignment problem, in which a set of periodically repeating tasks must be assigned to workers within a repeating schedule. The classical efficiency objective is to minimize the number of workers required to operate the schedule. We propose a 𝒪(n log n) algorithm to solve this problem. Next, we formalize a notion of fairness among workers, and impose that each worker performs the same work over time. We analyze the resulting trade-off between efficiency and fairness, showing that the price of fairness is at most one extra worker, and that such a fair solution can always be found using the Nearest Neighbor heuristic. We characterize all instances that admit a solution that is both fair and efficient, and use this result to develop a 𝒪(n log n) exact algorithm for the fair periodic assignment problem. Finally, we show that allowing aperiodic schedules never reduces the price of fairness.

Cite as

Rolf Nelson van Lieshout and Bartholomeüs Theodorus Cornelis van Rossum. The Fair Periodic Assignment Problem. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanlieshout_et_al:OASIcs.ATMOS.2025.1,
  author =	{van Lieshout, Rolf Nelson and van Rossum, Bartholome\"{u}s Theodorus Cornelis},
  title =	{{The Fair Periodic Assignment Problem}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{1:1--1:16},
  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.1},
  URN =		{urn:nbn:de:0030-drops-247574},
  doi =		{10.4230/OASIcs.ATMOS.2025.1},
  annote =	{Keywords: Cyclic scheduling, Fairness, Traveling Salesman Problem}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2018.15

Vehicle Scheduling Based on a Line Plan

Authors: Rolf N. van Lieshout and Paul C. Bouman

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract

We consider the following problem: given a set of lines in a public transportation network with their round trip times and frequencies, a maximum number of vehicles and a maximum number of lines that can be combined into a vehicle circulation, does there exist a set of vehicle circulations that covers all lines given the constraints. Solving this problem provides an estimate of the costs of operating a certain line plan, without having to compute a timetable first. We show that this problem is NP-hard for any restriction on the number of lines that can be combined into a circulation which is equal to or greater than three. We pay special attention to the case where at most two lines can be combined into a circulation, which is NP-hard if a single line can be covered by multiple circulations. If this is not allowed, a matching algorithm can be used to find the optimal solutions, which we show to be a 16/15-approximation for the case where it is allowed. We also provide an exact algorithm that is able to exploit low tree-width of the so-called circulation graph and small numbers of vehicles required to cover single circulations.

Cite as

Rolf N. van Lieshout and Paul C. Bouman. Vehicle Scheduling Based on a Line Plan. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vanlieshout_et_al:OASIcs.ATMOS.2018.15,
  author =	{van Lieshout, Rolf N. and Bouman, Paul C.},
  title =	{{Vehicle Scheduling Based on a Line Plan}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{15:1--15:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.15},
  URN =		{urn:nbn:de:0030-drops-97204},
  doi =		{10.4230/OASIcs.ATMOS.2018.15},
  annote =	{Keywords: Vehicle scheduling, integrated railway planning, (fractional) matching, treewidth}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2018

Refine by Author
1 Bouman, Paul C.
1 van Lieshout, Rolf N.
1 van Lieshout, Rolf Nelson
1 van Rossum, Bartholomeüs Theodorus Cornelis

Refine by Series/Journal
2 OASIcs

Refine by Classification
2 Applied computing → Transportation
2 Mathematics of computing → Graph algorithms
1 Mathematics of computing → Combinatorial algorithms

Refine by Keyword
1 (fractional) matching
1 Cyclic scheduling
1 Fairness
1 Traveling Salesman Problem
1 Vehicle scheduling
Show More...

2 Search Results for "van Lieshout, Rolf N."

The Fair Periodic Assignment Problem

Abstract

Cite as

Vehicle Scheduling Based on a Line Plan

Abstract

Cite as

Thanks for your feedback!

Could not send message