22 Search Results for "Bouman, Paul C."

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

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.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}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.7
Improved Algorithms for the Capacitated Team Orienteering Problem

Authors: Gianlorenzo D'Angelo, Mattia D'Emidio, Esmaeil Delfaraz, and Gabriele Di Stefano

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

Abstract
We study the Capacitated Team Orienteering Problem, where a fleet of vehicles with capacities have to meet customers with known demands and prizes for a single commodity. The objective is to maximize the total prize and to assign a sequence of customers to each vehicle while keeping the total distance traveled within a given budget and such that the total demand served by each vehicle does not exceed its capacity. The problem has been widely studied both from a theoretical and a practical point of view. The contribution of this paper is twofold: (1) We advance the theoretical knowledge on the problem by providing new approximation algorithms that achieve, under some natural assumption, improved approximation ratios compared to the current best algorithms; (2) We propose four efficient heuristics that outperform the current state-of-the-art practical methods in the sense that they compute solutions that collect nearly the same prize in a significantly smaller running time. We also experimentally test the scalability of the new heuristics, showing that their running time increases approximately linearly with the size of the input, allowing us to process large graphs which were not possible to analyze before.
Cite as

Gianlorenzo D'Angelo, Mattia D'Emidio, Esmaeil Delfaraz, and Gabriele Di Stefano. Improved Algorithms for the Capacitated Team Orienteering Problem. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dangelo_et_al:OASIcs.ATMOS.2024.7,
  author =	{D'Angelo, Gianlorenzo and D'Emidio, Mattia and Delfaraz, Esmaeil and Di Stefano, Gabriele},
  title =	{{Improved Algorithms for the Capacitated Team Orienteering Problem}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{7:1--7: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.7},
  URN =		{urn:nbn:de:0030-drops-211957},
  doi =		{10.4230/OASIcs.ATMOS.2024.7},
  annote =	{Keywords: Vehicle Routing, Approximation algorithms, Algorithm Engineering}
}
Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2024.8
New Bounds on the Performance of SBP for the Dial-a-Ride Problem with Revenues (Short Paper)

Authors: Barbara M. Anthony, Christine Chung, Ananya Das, and David Yuen

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

Abstract
We revisit the Segmented Best Path (sbp) algorithm for online DARP in an offline setting with revenues and a time limit. The goal is to find a subset of the inputted ride requests that can be served within the time limit while maximizing the total revenue earned. sbp divides the time into segments and greedily chooses the highest-revenue path of requests to serve within each time segment. We show that sbp’s performance has an upper bound of 5. Further, while sbp is a tight 4-approximation in the uniform-revenue case, we find that with non-uniform revenues, the approximation ratio of sbp has a lower bound strictly greater than 4; in particular, we provide a lower bound of (√e + 1)/(√e - 1) ≈ 4.08299, which we show can be generalized to instances with ratio greater than 4.278.
Cite as

Barbara M. Anthony, Christine Chung, Ananya Das, and David Yuen. New Bounds on the Performance of SBP for the Dial-a-Ride Problem with Revenues (Short Paper). In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 8:1-8:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anthony_et_al:OASIcs.ATMOS.2024.8,
  author =	{Anthony, Barbara M. and Chung, Christine and Das, Ananya and Yuen, David},
  title =	{{New Bounds on the Performance of SBP for the Dial-a-Ride Problem with Revenues}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{8:1--8:6},
  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.8},
  URN =		{urn:nbn:de:0030-drops-211964},
  doi =		{10.4230/OASIcs.ATMOS.2024.8},
  annote =	{Keywords: Dial-a-Ride problems, Lower bounds, Vehicle routing}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.9
Online Vehicle Routing with Pickups and Deliveries Under Time-Dependent Travel-Time Constraints

Authors: Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos Zaroliagis

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

Abstract
The Vehicle Routing Problem with pickups, deliveries and spatiotemporal service constraints (VRP_PDSTC) is a quite challenging algorithmic problem that can be dealt with in either an offline or an online fashion. In this work, we focus on a generalization, called VRP_PDSTCtd, in which the travel-time metric is time-dependent: the traversal-time per road segment (represented as a directed arc) is determined by some function of the departure-time from its tail towards its head. Time-dependence makes things much more complicated, even for the simpler problem of computing earliest-arrival-time paths which is a crucial subroutine to be solved (numerous times) by VRP_PDSTCtd schedulers. We propose two online schedulers of requests to workers, one which is a time-dependent variant of the classical Plain-Insertion heuristic, and an extension of it trying to digest some sort of forecasts for future demands for service. We enrich these two online schedulers with two additional heuristics, one targeting for distance-balanced assignments of work loads to the workers and another that makes local-search-improvements to the produced solutions. We conduct a careful experimental evaluation of the proposed algorithms on a real-world instance, with or without these heuristics, and compare their quality with human-curated assignments provided by professional experts (human operators at actual pickup-and-delivery control centers), and also with feasible solutions constructed from a relaxed MILP formulation of VRP_PDSTCtd, which is also introduced in this paper. Our findings are quite encouraging, demonstrating that the proposed algorithms produce solutions which (i) are significant improvements over the human-curated assignments, and (ii) have overall quality pretty close to that of the (extremely time-consuming) solutions provided by an exact solver for the MILP formulation.
Cite as

Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos Zaroliagis. Online Vehicle Routing with Pickups and Deliveries Under Time-Dependent Travel-Time Constraints. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2024.9,
  author =	{Kontogiannis, Spyros and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{Online Vehicle Routing with Pickups and Deliveries Under Time-Dependent Travel-Time Constraints}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{9:1--9:20},
  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.9},
  URN =		{urn:nbn:de:0030-drops-211972},
  doi =		{10.4230/OASIcs.ATMOS.2024.9},
  annote =	{Keywords: transport optimization heuristics, vehicle routing with pickups and deliveries, time-dependent travel-times}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.10
Periodic Timetabling: Travel Time vs. Regenerative Energy

Authors: Sven Jäger, Sarah Roth, and Anita Schöbel

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

Abstract
While it is important to provide attractive public transportation to the passengers allowing short travel times, it should also be a major concern to reduce the amount of energy used by the public transport system. Electrical trains can regenerate energy when braking, which can be used by a nearby accelerating train. Therefore, apart from the minimization of travel times, the maximization of brake-traction overlaps of nearby trains is an important objective in periodic timetabling. Recently, this has been studied in a model allowing small modifications of a nominal timetable. We investigate the problem of finding periodic timetables that are globally good in both objective functions. We show that the general problem is NP-hard, even restricted to a single transfer station and if only travel time is to be minimized, and give an algorithm with an additive error bound for maximizing the brake-traction overlap on this small network. Moreover, we identify special cases in which the problem is solvable in polynomial time. Finally, we demonstrate the trade-off between the two objective functions in an experimental study.
Cite as

Sven Jäger, Sarah Roth, and Anita Schöbel. Periodic Timetabling: Travel Time vs. Regenerative Energy. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jager_et_al:OASIcs.ATMOS.2024.10,
  author =	{J\"{a}ger, Sven and Roth, Sarah and Sch\"{o}bel, Anita},
  title =	{{Periodic Timetabling: Travel Time vs. Regenerative Energy}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{10:1--10:20},
  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.10},
  URN =		{urn:nbn:de:0030-drops-211983},
  doi =		{10.4230/OASIcs.ATMOS.2024.10},
  annote =	{Keywords: periodic timetabling, regenerative braking}
}
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.2024.12
Towards an Optimization Pipeline for the Design of Train Control Systems with Hybrid Train Detection (Short Paper)

Authors: Stefan Engels and Robert Wille

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

Abstract
Increasing the capacity of our railway infrastructure will become more and more essential in coping with the need for sustainable transportation. This can be achieved by intelligently implementing train control systems on specific railway networks. Methods that automate and optimize parts of this planning process are of great interest. For control systems based on hybrid train detection, such optimization tasks simultaneously involve routing and block layout generation. These tasks are already complex on their own; hence, a joint consideration often becomes infeasible. This work-in-progress paper proposes an idea to tackle the corresponding complexity. To this end, we present a pipeline that allows to sequentially handle corresponding optimization tasks in a less complex fashion while generating results that remain (close to) optimal. Results from an initial case study showcase that this approach is, indeed, promising. A prototypical implementation is included in the open-source Munich Train Control Toolkit available at https://github.com/cda-tum/mtct.
Cite as

Stefan Engels and Robert Wille. Towards an Optimization Pipeline for the Design of Train Control Systems with Hybrid Train Detection (Short Paper). In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 12:1-12:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{engels_et_al:OASIcs.ATMOS.2024.12,
  author =	{Engels, Stefan and Wille, Robert},
  title =	{{Towards an Optimization Pipeline for the Design of Train Control Systems with Hybrid Train Detection}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{12:1--12:6},
  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.12},
  URN =		{urn:nbn:de:0030-drops-212002},
  doi =		{10.4230/OASIcs.ATMOS.2024.12},
  annote =	{Keywords: ETCS, MILP, Design Automation, Hybrid Train Detection}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2024.13
A Bayesian Rolling Horizon Approach for Rolling Stock Rotation Planning with Predictive Maintenance

Authors: Felix Prause and Ralf Borndörfer

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

Abstract
We consider the rolling stock rotation planning problem with predictive maintenance (RSRP-PdM), where a timetable given by a set of trips must be operated by a fleet of vehicles. Here, the health states of the vehicles are assumed to be random variables, and their maintenance schedule should be planned based on their predicted failure probabilities. Utilizing the Bayesian update step of the Kalman filter, we develop a rolling horizon approach for RSRP-PdM, in which the predicted health state distributions are updated as new data become available. This approach reduces the uncertainty of the health states and thus improves the decision-making basis for maintenance planning. To solve the instances, we employ a local neighborhood search, which is a modification of a heuristic for RSRP-PdM, and demonstrate its effectiveness. Using this solution algorithm, the presented approach is compared with the results of common maintenance strategies on test instances derived from real-world timetables. The obtained results show the benefits of the rolling horizon approach.
Cite as

Felix Prause and Ralf Borndörfer. A Bayesian Rolling Horizon Approach for Rolling Stock Rotation Planning with Predictive Maintenance. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{prause_et_al:OASIcs.ATMOS.2024.13,
  author =	{Prause, Felix and Bornd\"{o}rfer, Ralf},
  title =	{{A Bayesian Rolling Horizon Approach for Rolling Stock Rotation Planning with Predictive Maintenance}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{13:1--13:19},
  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.13},
  URN =		{urn:nbn:de:0030-drops-212013},
  doi =		{10.4230/OASIcs.ATMOS.2024.13},
  annote =	{Keywords: Rolling stock rotation planning, Predictive maintenance, Rolling horizon approach, Bayesian inference, Local neighborhood search}
}
  • Refine by Author
  • 3 Bouman, Paul C.
  • 2 Borndörfer, Ralf
  • 2 D'Emidio, Mattia
  • 2 Jäger, Sven
  • 2 Kontogiannis, Spyros C.
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Public transport
  • 2 traffic assignment
  • 1 (fractional) matching
  • 1 Algorithm Engineering
  • 1 Algorithms Engineering
  • Show More...

  • Refine by Type
  • 21 document
  • 1 volume

  • Refine by Publication Year
  • 21 2024
  • 1 2018

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