48 Search Results for "Kontogiannis, Spyros"

Volume

OASIcs, Volume 123

24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

ATMOS 2024, September 5-6, 2024, Royal Holloway, London, United Kingdom

Editors: Paul C. Bouman and Spyros C. Kontogiannis

Volume

OASIcs, Volume 20

11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems

ATMOS 2011, September 8, 2011, Saarbrücken, Germany

Editors: Alberto Caprara and Spyros Kontogiannis

Document
DOI: 10.4230/OASIcs.ATMOS.2025.11
Design of Distance Tariffs in Public Transport

Authors: Philine Schiewe, Anita Schöbel, and Reena Urban

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

Abstract
Setting the ticket prices is a crucial decision in public transport. Its basis, relevant for all related questions, such as dynamic prices or prices for different passenger groups, is the underlying fare strategy. Popular fare strategies are based on zones or on distances. Transitions from one fare strategy to another occur frequently, e.g., if public transport operators are joined to a larger association, or if structural decisions in a region have taken place. In this paper we report practically relevant issues when a fare structure should be changed to a distance tariff, a problem frequently arising when a ticket system based on mobile devices is introduced. We present mixed-integer linear programs for finding the parameters of a distance tariff, analyze rounding properties, and reflect how the change in revenue for the operator and the number of highly affected passengers can be controlled. Additionally, we evaluate the developed models experimentally.
Cite as

Philine Schiewe, Anita Schöbel, and Reena Urban. Design of Distance Tariffs in Public Transport. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schiewe_et_al:OASIcs.ATMOS.2025.11,
  author =	{Schiewe, Philine and Sch\"{o}bel, Anita and Urban, Reena},
  title =	{{Design of Distance Tariffs in Public Transport}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-247670},
  doi =		{10.4230/OASIcs.ATMOS.2025.11},
  annote =	{Keywords: public transport, fare strategy, distance tariff}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.14
Using A* for Optimal Train Routing on Moving Block Systems

Authors: Stefan Engels and Robert Wille

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

Abstract
Modern control systems based on Moving Block allow for shorter headways and higher capacity on existing railway infrastructure. At the same time, few algorithms for optimal routing on networks equipped with such modern control systems exist. Previous methods rely on Mixed Integer Linear Programming (MILP) and face a trade-off between model size and accuracy, especially considering comparably complex and nonlinear headway constraints as well as train dynamics. With this work, we propose a complementary approach based on A*. Under a reasonable and easy assumption on train driver behavior, we propose a solution encoding and state space that is flexible concerning the choice of search algorithm and the modeling detail. The applicability is showcased on a small benchmark set. The implementation is available open-source as part of the Munich Train Control Toolkit (MTCT) on GitHub at https://github.com/cda-tum/mtct.
Cite as

Stefan Engels and Robert Wille. Using A* for Optimal Train Routing on Moving Block Systems. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{engels_et_al:OASIcs.ATMOS.2025.14,
  author =	{Engels, Stefan and Wille, Robert},
  title =	{{Using A* for Optimal Train Routing on Moving Block Systems}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{14:1--14:18},
  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.14},
  URN =		{urn:nbn:de:0030-drops-247701},
  doi =		{10.4230/OASIcs.ATMOS.2025.14},
  annote =	{Keywords: ETCS, Train Routing, Moving Block, A*, Munich Train Control Toolkit}
}
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.2025.6
VRP-Inspired Techniques for Discrete Dynamic Berth Allocation and Scheduling

Authors: Konstantinos Karathanasis, Spyros Kontogiannis, Asterios Pegos, Vasileios Sofianos, and Christos Zaroliagis

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

Abstract
The Berth Allocation and Scheduling Problem (BASP) is a critical optimization challenge in maritime logistics, aiming to assign arriving vessels to berths efficiently, while adhering to practical constraints. Exploiting the connection of BASP with the Heterogeneous Vehicle Routing Problem with Time Windows (HVRPTW), we propose a mixed integer linear programming (MILP) formulation for a variant of BASP which is of utmost importance in real-world scenarios: the Dynamic Discrete Berth Allocation and Scheduling Problem with Time Windows (DDBASPTW). Consequently, inspired by the wealth of constructive and improvement heuristics for VRP, we design, implement and experimentally evaluate three constructive heuristics, Nearest Neighbour (NN), Insertion (INS), a quick-and-dirty variant of Insertion (qd-INS), as well as two improvement heuristics, Swap and Reinsert, taking into consideration both the online and the offline scenario with respect to vessel arrivals. Finally, we propose, implement and experimentally evaluate, custom-tailored variants for DDBASPTW of a single-solution metaheuristic, the Adaptive Large Neighborhood Search (ALNS), and of two population-based metaheuristics, the Genetic Algorithm (GA) and the Cuckoo Search Algorithm (CSA), which are aimed to solve the offline version of the problem. An extensive experimental evaluation compares these techniques against a generic state-of-the-art MILP solver. Results demonstrate that certain variants of INS not only are extremely fast and deliver competitive solutions, achieving a practical trade-off between execution times and quality of solutions. The improvement heuristics further refine the initial solutions, especially for weaker constructive approaches, offering a lightweight yet effective enhancement mechanism. The metaheuristics consistently yield high-quality solutions with significantly lower computational times compared to the exact MILP solver, making them well-suited for use in real-time or large-scale operational environments.
Cite as

Konstantinos Karathanasis, Spyros Kontogiannis, Asterios Pegos, Vasileios Sofianos, and Christos Zaroliagis. VRP-Inspired Techniques for Discrete Dynamic Berth Allocation and Scheduling. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{karathanasis_et_al:OASIcs.ATMOS.2025.6,
  author =	{Karathanasis, Konstantinos and Kontogiannis, Spyros and Pegos, Asterios and Sofianos, Vasileios and Zaroliagis, Christos},
  title =	{{VRP-Inspired Techniques for Discrete Dynamic Berth Allocation and Scheduling}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{6:1--6:21},
  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.6},
  URN =		{urn:nbn:de:0030-drops-247625},
  doi =		{10.4230/OASIcs.ATMOS.2025.6},
  annote =	{Keywords: Berth Allocation and Scheduling, Heuristics, Metaheuristics, Mixed Integer Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.59
Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets

Authors: Konstantinos Karathanasis, Spyros Kontogiannis, and Christos Zaroliagis

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A key task in multi-objective optimization is to compute the Pareto frontier (a.k.a. Pareto subset) P of a given d-dimensional objective space F; that is, a maximal subset P ⊆ F such that every element in P is non-dominated (i.e., it is better in at least one criterion, against any other point) within F. This process, called dominance-filtering, often involves handling objective spaces derived from either the union or the Minkowski sum of two given partial objective spaces which are Pareto sets themselves, and constitutes a major bottleneck in several multi-objective optimization techniques. In this work, we introduce three new data structures, ND^{+}-trees, QND^{+}-trees and TND^{+}-trees, which are designed for efficiently indexing non-dominated objective vectors and performing dominance-checks. We also devise three new algorithms that efficiently filter out dominated objective vectors from the union or the Minkowski sum of two Pareto sets. An extensive experimental evaluation on both synthetically generated and real-world data sets reveals that our new algorithms outperform state-of-art techniques for dominance-filtering of unions and Minkowski sums of Pareto sets, and scale well w.r.t. the number of d ≥ 3 criteria and the sets' sizes.
Cite as

Konstantinos Karathanasis, Spyros Kontogiannis, and Christos Zaroliagis. Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{karathanasis_et_al:LIPIcs.ESA.2025.59,
  author =	{Karathanasis, Konstantinos and Kontogiannis, Spyros and Zaroliagis, Christos},
  title =	{{Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.59},
  URN =		{urn:nbn:de:0030-drops-245277},
  doi =		{10.4230/LIPIcs.ESA.2025.59},
  annote =	{Keywords: Multi-Objective Optimization, Multi-Dimensional Data Structures, Pareto Sets, Algorithm Engineering}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2024
OASIcs, Volume 123, ATMOS 2024, Complete Volume

Authors: Paul C. Bouman and Spyros C. Kontogiannis

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

Abstract
OASIcs, Volume 123, ATMOS 2024, Complete Volume
Cite as

24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 1-316, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{bouman_et_al:OASIcs.ATMOS.2024,
  title =	{{OASIcs, Volume 123, ATMOS 2024, Complete Volume}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{1--316},
  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},
  URN =		{urn:nbn:de:0030-drops-211873},
  doi =		{10.4230/OASIcs.ATMOS.2024},
  annote =	{Keywords: OASIcs, Volume 123, ATMOS 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Paul C. Bouman and Spyros C. Kontogiannis

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bouman_et_al:OASIcs.ATMOS.2024.0,
  author =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{0:i--0:xii},
  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.0},
  URN =		{urn:nbn:de:0030-drops-211882},
  doi =		{10.4230/OASIcs.ATMOS.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.1
Landmark Hub Labeling: Improved Bounds and Faster Query Answering

Authors: Justine Cauvi, Ruoying Li, and Sabine Storandt

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

Abstract
Hub Labeling (HL) is a state-of-the-art method for answering shortest-distance queries between node pairs in weighted graphs. It provides very fast query times but also requires considerable additional space to store the label information. Recently, a generalization of HL, called Landmark Hub Labeling (LHL), has been proposed, that conceptionally allows a storage of fewer label information without compromising the optimality of the query result. However, query answering with LHL was shown to be slower than with HL, both in theory and practice. Furthermore, it was not clear whether there are graphs with a substantial space reduction when using LHL instead of HL. In this paper, we describe a new way of storing label information of an LHL such that query times are significantly reduced and then asymptotically match those of HL. Thus, we alleviate the so far greatest shortcoming of LHL compared to HL. Moreover, we show that for the practically relevant hierarchical versions (HHL and HLHL), there are graphs in which the label size of an optimal HLHL is a factor of Θ(√ n) smaller than that of an optimal HHL. We establish further novel bounds between different labeling variants. Additionally, we provide a comparative experimental study between approximation algorithms for HL and LHL. We demonstrate that label sizes in an LHL are consistently smaller than those of HL across diverse benchmark graphs, including road networks.
Cite as

Justine Cauvi, Ruoying Li, and Sabine Storandt. Landmark Hub Labeling: Improved Bounds and Faster Query Answering. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cauvi_et_al:OASIcs.ATMOS.2024.1,
  author =	{Cauvi, Justine and Li, Ruoying and Storandt, Sabine},
  title =	{{Landmark Hub Labeling: Improved Bounds and Faster Query Answering}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{1:1--1:17},
  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.1},
  URN =		{urn:nbn:de:0030-drops-211892},
  doi =		{10.4230/OASIcs.ATMOS.2024.1},
  annote =	{Keywords: Route Planning, Shortest Path, Hub Labeling}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.2
Indexing Graphs for Shortest Beer Path Queries

Authors: David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio

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

Abstract
A beer graph is an edge-weighted graph G = (V,E,ω) with beer vertices B ⊆ V. A beer path between two vertices s and t of a beer graph is a path that connects s and t and visits at least one vertex in B. The beer distance between two vertices is the weight of a shortest beer path, i.e. a beer path having minimum total weight. A graph indexing scheme is a two-phase method that constructs an index data structure by a one-time preprocessing of an input graph and then exploits it to compute (or accelerate the computation of) answers to queries on structures of the graph dataset. In the last decade, such indexing schemes have been designed to perform, effectively, many relevant types of queries, e.g. on reachability, and have gained significant popularity in essentially all data-intensive application domains where large number of queries have to be routinely answered (e.g. journey planners), since they have been shown, through many experimental studies, to offer extremely low query times at the price of limited preprocessing time and space overheads. In this paper, we showcase that an indexing scheme, to efficiently execute queries on beer distances or shortest beer paths for pairs of vertices of a beer graph, can be obtained by adapting the highway labeling, a recently introduced indexing method to accelerate the computation of classical shortest paths. We design a preprocessing algorithm to build a whl index, i.e. a weighted highway labeling of a beer graph, and show how it can be queried to compute beer distances and shortest beer paths. Through extensive experimentation on real networks, we empirically demonstrate its practical effectiveness and superiority, in terms of offered trade-off between preprocessing time, space overhead and query time, with respect to the state-of-the-art.
Cite as

David Coudert, Andrea D'Ascenzo, and Mattia D'Emidio. Indexing Graphs for Shortest Beer Path Queries. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coudert_et_al:OASIcs.ATMOS.2024.2,
  author =	{Coudert, David and D'Ascenzo, Andrea and D'Emidio, Mattia},
  title =	{{Indexing Graphs for Shortest Beer Path Queries}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{2:1--2:18},
  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.2},
  URN =		{urn:nbn:de:0030-drops-211907},
  doi =		{10.4230/OASIcs.ATMOS.2024.2},
  annote =	{Keywords: Graph Algorithms, Indexing Schemes, Beer Distances, Algorithms Engineering}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.3
Pricing for the EVRPTW with Piecewise Linear Charging by a Bounding-Based Labeling Algorithm

Authors: Jenny Enerbäck, Lukas Eveborn, and Elina Rönnberg

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

Abstract
The elementary shortest path problem with resource constraints (ESPPRC) is a common problem that often arises as a pricing problem when solving vehicle routing problems with a column generation approach. One way of solving the ESPPRC is to use a labeling algorithm. In this paper, we focus on how different bounding strategies for labeling algorithms can be adapted and strengthened for the ESPPRC that arises from the Electric Vehicle Routing Problem with Time Windows and Piecewise Linear Recharging function (EVRPTW-PLR). We present a new completion bound method that takes charging times into account, and show how the completion bound can be combined with ng-routes. Computational experiments show that the new completion bound combined with ng-routes significantly improves the performance compared to a basic labeling algorithm.
Cite as

Jenny Enerbäck, Lukas Eveborn, and Elina Rönnberg. Pricing for the EVRPTW with Piecewise Linear Charging by a Bounding-Based Labeling Algorithm. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{enerback_et_al:OASIcs.ATMOS.2024.3,
  author =	{Enerb\"{a}ck, Jenny and Eveborn, Lukas and R\"{o}nnberg, Elina},
  title =	{{Pricing for the EVRPTW with Piecewise Linear Charging by a Bounding-Based Labeling Algorithm}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{3:1--3:18},
  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.3},
  URN =		{urn:nbn:de:0030-drops-211911},
  doi =		{10.4230/OASIcs.ATMOS.2024.3},
  annote =	{Keywords: ESPPRC, EVRP, Bounding, Labeling Algorithm}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.4
Periodic Event Scheduling with Flexible Infrastructure Assignment

Authors: Enrico Bortoletto, Rolf Nelson van Lieshout, Berenike Masing, and Niels Lindner

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

Abstract
We present novel extensions of the Periodic Event Scheduling Problem (PESP) that integrate the assignment of activities to infrastructure elements. An application of this is railway timetabling, as station and platform capacities are limited and need to be taken into account. We show that an assignment of activities to platforms can always be made periodic, and that it can be beneficial to allow larger periods for the assignment than for the timetable. We present mixed-integer programming formulations for the general problem, as well as for the practically relevant case when multiple platforms can be considered equivalent, for which we present a bipartite matching approach. We finally test and compare these models on real-world instances.
Cite as

Enrico Bortoletto, Rolf Nelson van Lieshout, Berenike Masing, and Niels Lindner. Periodic Event Scheduling with Flexible Infrastructure Assignment. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bortoletto_et_al:OASIcs.ATMOS.2024.4,
  author =	{Bortoletto, Enrico and van Lieshout, Rolf Nelson and Masing, Berenike and Lindner, Niels},
  title =	{{Periodic Event Scheduling with Flexible Infrastructure Assignment}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{4:1--4:18},
  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.4},
  URN =		{urn:nbn:de:0030-drops-211929},
  doi =		{10.4230/OASIcs.ATMOS.2024.4},
  annote =	{Keywords: Periodic Event Scheduling, Periodic Timetabling, Railway Timetabling, Matchings, Infrastructure Assignments, Platform Assignments, Station Capacities}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.5
Balanced Assignments of Periodic Tasks

Authors: Héloïse Gachet and Frédéric Meunier

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

Abstract
This work deals with a problem of assigning periodic tasks to employees in such a way that each employee performs each task with the same frequency in the long term. The motivation comes from a collaboration with the main French railway company, the SNCF. An almost complete solution is provided under the form of a necessary and sufficient condition that can be checked in polynomial time. A complementary discussion about possible extensions is also proposed.
Cite as

Héloïse Gachet and Frédéric Meunier. Balanced Assignments of Periodic Tasks. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gachet_et_al:OASIcs.ATMOS.2024.5,
  author =	{Gachet, H\'{e}lo\"{i}se and Meunier, Fr\'{e}d\'{e}ric},
  title =	{{Balanced Assignments of Periodic Tasks}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{5:1--5:12},
  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.5},
  URN =		{urn:nbn:de:0030-drops-211938},
  doi =		{10.4230/OASIcs.ATMOS.2024.5},
  annote =	{Keywords: Fair schedule, Eulerian digraph, Markov chain, interval graph}
}
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}
}
  • Refine by Type
  • 46 Document/PDF
  • 5 Document/HTML
  • 2 Volume

  • Refine by Publication Year
  • 5 2025
  • 21 2024
  • 1 2022
  • 1 2020
  • 1 2019
  • Show More...

  • Refine by Author
  • 11 Kontogiannis, Spyros
  • 8 Zaroliagis, Christos
  • 5 Paraskevopoulos, Andreas
  • 5 Schöbel, Anita
  • 3 Borndörfer, Ralf
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 44 OASIcs

  • Refine by Classification
  • 19 Applied computing → Transportation
  • 4 Mathematics of computing → Graph algorithms
  • 4 Theory of computation → Design and analysis of algorithms
  • 3 Mathematics of computing → Combinatorics
  • 3 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 2 Algorithm Engineering
  • 2 Distance oracles
  • 2 ETCS
  • 2 FIFO property
  • 2 Preface
  • 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