Volume
OASIcs, Volume 96
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Publication Details
- published at: 2021-09-27
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-213-6
- DBLP: db/conf/atmos/atmos2021
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
OASIcs, Volume 96, ATMOS 2021, Complete Volume
Abstract
OASIcs, Volume 96, ATMOS 2021, Complete Volume
Cite as
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 1-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@Proceedings{mullerhannemann_et_al:OASIcs.ATMOS.2021,
title = {{OASIcs, Volume 96, ATMOS 2021, Complete Volume}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {1--304},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021},
URN = {urn:nbn:de:0030-drops-148685},
doi = {10.4230/OASIcs.ATMOS.2021},
annote = {Keywords: OASIcs, Volume 96, ATMOS 2021, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{mullerhannemann_et_al:OASIcs.ATMOS.2021.0,
author = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {0:i--0:x},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.0},
URN = {urn:nbn:de:0030-drops-148690},
doi = {10.4230/OASIcs.ATMOS.2021.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes
Abstract
Vehicle routing and scheduling problems with interdependent routes arise when some services must be performed by at least two vehicles and temporal synchronization is thus required between the starting times of these services. These problems are often coupled with time window constraints in order to model various real-world applications such as pickup and delivery with transfers, cross-docking and home care scheduling. Interdependent routes in these applications can lead to large idle times for some drivers, unnecessarily lengthening their working hours. To remedy this unfairness, it is necessary to balance the duration of the drivers' routes. However, quickly evaluating duration-based equity functions for interdependent vehicle routes with time windows poses a significant computational challenge, particularly when the departure time of routes is flexible. This paper introduces models and algorithms to compute two well-known equity functions in flexible departure time settings: min-max and range minimization. We explore the challenges and algorithmic complexities of evaluating these functions both from a theoretical and an experimental viewpoint. The results of this paper enable the development of new heuristic methods to balance the workload of interdependent vehicle routes with time windows.
Cite as
Carlo S. Sartori, Pieter Smet, and Greet Vanden Berghe. Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{sartori_et_al:OASIcs.ATMOS.2021.1,
author = {Sartori, Carlo S. and Smet, Pieter and Vanden Berghe, Greet},
title = {{Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {1:1--1:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.1},
URN = {urn:nbn:de:0030-drops-148703},
doi = {10.4230/OASIcs.ATMOS.2021.1},
annote = {Keywords: Vehicle scheduling, Workload balancing, Route duration, Interdependent routes, Time windows}
}
Document
Forward Cycle Bases and Periodic Timetabling
Abstract
Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance R1L1 of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.
Cite as
Niels Lindner, Christian Liebchen, and Berenike Masing. Forward Cycle Bases and Periodic Timetabling. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{lindner_et_al:OASIcs.ATMOS.2021.2,
author = {Lindner, Niels and Liebchen, Christian and Masing, Berenike},
title = {{Forward Cycle Bases and Periodic Timetabling}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {2:1--2:14},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.2},
URN = {urn:nbn:de:0030-drops-148719},
doi = {10.4230/OASIcs.ATMOS.2021.2},
annote = {Keywords: Periodic Timetabling, Cycle Bases, Mixed Integer Programming}
}
Document
Towards Improved Robustness of Public Transport by a Machine-Learned Oracle
Abstract
The design and optimization of public transport systems is a highly complex and challenging process. Here, we focus on the trade-off between two criteria which shall make the transport system attractive for passengers: their travel time and the robustness of the system. The latter is time-consuming to evaluate. A passenger-based evaluation of robustness requires a performance simulation with respect to a large number of possible delay scenarios, making this step computationally very expensive.
For optimizing the robustness, we hence apply a machine-learned oracle from previous work which approximates the robustness of a public transport system. We apply this oracle to bi-criteria optimization of integrated public transport planning (timetabling and vehicle scheduling) in two ways: First, we explore a local search based framework studying several variants of neighborhoods. Second, we evaluate a genetic algorithm. Computational experiments with artificial and close to real-word benchmark datasets yield promising results. In all cases, an existing pool of solutions (i.e., public transport plans) can be significantly improved by finding a number of new non-dominated solutions, providing better and different trade-offs between robustness and travel time.
Cite as
Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Towards Improved Robustness of Public Transport by a Machine-Learned Oracle. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{mullerhannemann_et_al:OASIcs.ATMOS.2021.3,
author = {M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schiewe, Alexander and Sch\"{o}bel, Anita},
title = {{Towards Improved Robustness of Public Transport by a Machine-Learned Oracle}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {3:1--3:20},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.3},
URN = {urn:nbn:de:0030-drops-148721},
doi = {10.4230/OASIcs.ATMOS.2021.3},
annote = {Keywords: Public Transportation, Timetabling, Machine Learning, Robustness}
}
Document
Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) Problem with Uncertainties
Abstract
The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategic fleet-sizing, tactical assignment, operational vehicle routing and scheduling problems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a stochastic mixed-integer linear programming model for the H-SARA problem. Additionally, a reduced deterministic version is introduced which allows to solve small-scale instances to optimality with two acceleration approaches. For larger instances, we develop a tailored two-stage decision support system that provides high-quality and in-time solutions based on information revealed at different stages. Our solution method aims to reduce various costs under stochasticity, to create reasonable routes with balanced workload and team-based customer service zones, and to increase customer satisfaction by introducing a two-stage appointment notification system updated at different time stages before the actual service. Our two-stage heuristic is competitive to CPLEX’s exact solution methods in providing time and cost-effective decisions and can update previously-made decisions based on an increased level of information. Results show that our two-stage heuristic is able to tackle reasonable-size instances and provides good-quality solutions using less time compared to the deterministic and stochastic models on the same set of simulated instances.
Cite as
Syu-Ning Johnn, Yiran Zhu, Andrés Miniguano-Trujillo, and Akshay Gupte. Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) Problem with Uncertainties. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{johnn_et_al:OASIcs.ATMOS.2021.4,
author = {Johnn, Syu-Ning and Zhu, Yiran and Miniguano-Trujillo, Andr\'{e}s and Gupte, Akshay},
title = {{Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) Problem with Uncertainties}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {4:1--4:21},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.4},
URN = {urn:nbn:de:0030-drops-148737},
doi = {10.4230/OASIcs.ATMOS.2021.4},
annote = {Keywords: Home Health Care, Mixed-Integer Linear Programming, Two-stage Stochastic, Uncertainties A Priori Optimisation, Adaptive Large Neighbourhood Search, Monte-Carlo Simulation}
}
Document
On the Bike Spreading Problem
Abstract
A free-floating bike-sharing system (FFBSS) is a dockless rental system where an individual can borrow a bike and returns it anywhere, within the service area. To improve the rental service, available bikes should be distributed over the entire service area: a customer leaving from any position is then more likely to find a near bike and then to use the service. Moreover, spreading bikes among the entire service area increases urban spatial equity since the benefits of FFBSS are not a prerogative of just a few zones. For guaranteeing such distribution, the FFBSS operator can use vans to manually relocate bikes, but it incurs high economic and environmental costs. We propose a novel approach that exploits the existing bike flows generated by customers to distribute bikes. More specifically, by envisioning the problem as an Influence Maximization problem, we show that it is possible to position batches of bikes on a small number of zones, and then the daily use of FFBSS will efficiently spread these bikes on a large area. We show that detecting these zones is NP-complete, but there exists a simple and efficient 1-1/e approximation algorithm; our approach is then evaluated on a dataset of rides from the free-floating bike-sharing system of the city of Padova.
Cite as
Elia Costa and Francesco Silvestri. On the Bike Spreading Problem. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{costa_et_al:OASIcs.ATMOS.2021.5,
author = {Costa, Elia and Silvestri, Francesco},
title = {{On the Bike Spreading Problem}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {5:1--5:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.5},
URN = {urn:nbn:de:0030-drops-148746},
doi = {10.4230/OASIcs.ATMOS.2021.5},
annote = {Keywords: Mobility data, bike sharing, bike relocation, influence maximization, NP-completeness, approximation algorithm}
}
Document
A Phase I Simplex Method for Finding Feasible Periodic Timetables
Abstract
The periodic event scheduling problem (PESP) with various applications in timetabling or traffic light scheduling is known to be challenging to solve. In general, it is already NP-hard to find a feasible solution. However, depending on the structure of the underlying network and the values of lower and upper bounds on activities, this might also be an easy task.
In this paper we make use of this property and suggest phase I approaches (similar to the well-known phase I of the simplex algorithm) to find a feasible solution to PESP. Given an instance of PESP, we define an auxiliary instance for which a feasible solution can easily be constructed, and whose solution determines a feasible solution of the original instance or proves that the original instance is not feasible. We investigate different possibilities on how such an auxiliary instance can be defined theoretically and experimentally. Furthermore, in our experiments we compare different solution approaches for PESP and their behavior in the phase I approach. The results show that this approach can be especially helpful if the instance admits a feasible solution, while it is generally outperformed by classic mixed-integer programming formulations when the instance is infeasible.
Cite as
Marc Goerigk, Anita Schöbel, and Felix Spühler. A Phase I Simplex Method for Finding Feasible Periodic Timetables. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{goerigk_et_al:OASIcs.ATMOS.2021.6,
author = {Goerigk, Marc and Sch\"{o}bel, Anita and Sp\"{u}hler, Felix},
title = {{A Phase I Simplex Method for Finding Feasible Periodic Timetables}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {6:1--6:13},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.6},
URN = {urn:nbn:de:0030-drops-148753},
doi = {10.4230/OASIcs.ATMOS.2021.6},
annote = {Keywords: train timetable optimization, periodic event scheduling problem, modulo simplex}
}
Document
Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data
Abstract
We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.
Cite as
Niels Lindner, Pedro Maristany de las Casas, and Philine Schiewe. Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{lindner_et_al:OASIcs.ATMOS.2021.7,
author = {Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine},
title = {{Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {7:1--7:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.7},
URN = {urn:nbn:de:0030-drops-148767},
doi = {10.4230/OASIcs.ATMOS.2021.7},
annote = {Keywords: Preprocessing Shortest Path Problems, Interval Data, Graph Algorithms}
}
Document
Solving the Dynamic Dial-a-Ride Problem Using a Rolling-Horizon Event-Based Graph
Abstract
In many ridepooling applications transportation requests arrive throughout the day and have to be answered and integrated into the existing (and operated) vehicle routing. To solve this dynamic dial-a-ride problem we present a rolling-horizon algorithm that dynamically updates the current solution by solving an MILP formulation. The MILP model is based on an event-based graph with nodes representing pick-up and drop-off events associated with feasible user allocations in the vehicles. The proposed solution approach is validated on a set of real-word instances with more than 500 requests. In 99.5% of all iterations the rolling-horizon algorithm returned optimal insertion positions w.r.t. the current schedule in a time-limit of 30 seconds. On average, incoming requests are answered within 2.8 seconds.
Cite as
Daniela Gaul, Kathrin Klamroth, and Michael Stiglmayr. Solving the Dynamic Dial-a-Ride Problem Using a Rolling-Horizon Event-Based Graph. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{gaul_et_al:OASIcs.ATMOS.2021.8,
author = {Gaul, Daniela and Klamroth, Kathrin and Stiglmayr, Michael},
title = {{Solving the Dynamic Dial-a-Ride Problem Using a Rolling-Horizon Event-Based Graph}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {8:1--8:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.8},
URN = {urn:nbn:de:0030-drops-148776},
doi = {10.4230/OASIcs.ATMOS.2021.8},
annote = {Keywords: Dial-a-Ride Problem, Ridepooling, Event-Based MILP, Rolling-Horizon, Dynamic Requests}
}
Document
Solving the Periodic Scheduling Problem: An Assignment Approach in Non-Periodic Networks
Abstract
The periodic event scheduling problem (PESP) is a well researched problem used for finding good periodic timetables in public transport. While it is based on a periodic network consisting of events and activities which are repeated every period, we propose a new periodic timetabling model using a non-periodic network. This is a first step towards the goal of integrating periodic timetabling with other planning steps taking place in the aperiodic network, e.g. passenger assignment or delay management. In this paper, we develop the new model, show how we can reduce its size and prove its equivalence to PESP. We also conduct computational experiments on close-to real-world data from Lower Saxony, a region in northern Germany, and see that the model can be solved in a reasonable amount of time.
Cite as
Vera Grafe and Anita Schöbel. Solving the Periodic Scheduling Problem: An Assignment Approach in Non-Periodic Networks. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{grafe_et_al:OASIcs.ATMOS.2021.9,
author = {Grafe, Vera and Sch\"{o}bel, Anita},
title = {{Solving the Periodic Scheduling Problem: An Assignment Approach in Non-Periodic Networks}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {9:1--9:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.9},
URN = {urn:nbn:de:0030-drops-148780},
doi = {10.4230/OASIcs.ATMOS.2021.9},
annote = {Keywords: Public Transport, Periodic Timetabling, PESP, Integer Programming}
}
Document
Fast Map Matching with Vertex-Monotone Fréchet Distance
Abstract
We study a generalization for map matching algorithms that includes both geometric approaches such as the Fréchet distance and global weight approaches such as those typically used by Hidden Markov Models. Through this perspective, we discovered an efficient map matching algorithm with respect to the vertex-monotone Fréchet distance while using a heuristic tie-breaker inspired by global weight methods. While the classical Fréchet distance requires parameterizations to be monotone, the vertex-monotone Fréchet distance allows backtracking within edges. Our analysis and experimental evaluations show that relaxing the monotonicity constraint enables significantly faster algorithms without significantly altering the resulting map matched paths.
Cite as
Daniel Chen, Christian Sommer, and Daniel Wolleb. Fast Map Matching with Vertex-Monotone Fréchet Distance. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:OASIcs.ATMOS.2021.10,
author = {Chen, Daniel and Sommer, Christian and Wolleb, Daniel},
title = {{Fast Map Matching with Vertex-Monotone Fr\'{e}chet Distance}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {10:1--10:20},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.10},
URN = {urn:nbn:de:0030-drops-148794},
doi = {10.4230/OASIcs.ATMOS.2021.10},
annote = {Keywords: Fr\'{e}chet distance, map matching, minimum bottleneck path}
}
Document
Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles
Abstract
Electric Vehicle routing is often modeled as a Shortest Feasible Path Problem (SFPP), which minimizes total travel time while maintaining a non-zero State of Charge (SoC) along the route. However, the problem assumes perfect information about energy consumption and charging stations, which are difficult to even estimate in practice. Further, drivers might have varying risk tolerances for different trips. To overcome these limitations, we propose two generalizations to the SFPP; they compute the shortest feasible path for any initial SoC and, respectively, for every possible minimum SoC threshold. We present algorithmic solutions for each problem, and provide two constructs: Starting Charge Maps and Buffer Maps, which represent the tradeoffs between robustness of feasible routes and their travel times. The two constructs are useful in many ways, including presenting alternate routes or providing charging prompts to users. We evaluate the performance of our algorithms on realistic input instances.
Cite as
Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J. West, Dennis Schieferdecker, and Daniel Delling. Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{rajan_et_al:OASIcs.ATMOS.2021.11,
author = {Rajan, Payas and Baum, Moritz and Wegner, Michael and Z\"{u}ndorf, Tobias and West, Christian J. and Schieferdecker, Dennis and Delling, Daniel},
title = {{Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {11:1--11:18},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.11},
URN = {urn:nbn:de:0030-drops-148807},
doi = {10.4230/OASIcs.ATMOS.2021.11},
annote = {Keywords: Electric Vehicles, Route Planning}
}
Document
A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals
Abstract
We study last-mile delivery with the option of crowd shipping, where a company makes use of occasional drivers to complement its vehicle’s fleet in the activity of delivering products to its customers. We model it as a data-driven distributionally robust optimization approach to the capacitated vehicle routing problem. We assume the marginals of the defined uncertainty vector are known, but the joint distribution is difficult to estimate. The presence of customers and available occasional drivers can be random. We adopt a strategic planning perspective, where an optimal a priori solution is calculated before the uncertainty is revealed. Therefore, without the need for online resolution performance, we can experiment with exact solutions. Solving the problem defined above is challenging: not only the first-stage problem is already NP-Hard, but also the uncertainty and potentially the second-stage decisions are binary of high dimension, leading to non-convex optimization formulations that are complex to solve. We propose a branch-price-and-cut algorithm taking into consideration measures that exploit the intrinsic characteristics of our problem and reduce the complexity to solve it.
Cite as
Marco Silva, João Pedro Pedroso, Ana Viana, and Xenia Klimentova. A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{silva_et_al:OASIcs.ATMOS.2021.12,
author = {Silva, Marco and Pedroso, Jo\~{a}o Pedro and Viana, Ana and Klimentova, Xenia},
title = {{A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {12:1--12:20},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.12},
URN = {urn:nbn:de:0030-drops-148811},
doi = {10.4230/OASIcs.ATMOS.2021.12},
annote = {Keywords: Last-mile delivery, Stochastic Vehicle Routing Problem, Crowd shipping, Distributionally Robust Optimization, Data-driven Optimization}
}
Document
Locating Evacuation Centers Optimally in Path and Cycle Networks
Abstract
We present dynamic flow algorithms to solve the k-sink problem whose aim is to locate k sinks (evacuation centers) in such a way that the evacuation time of the last evacuee is minimized. In the confluent model, the evacuees originating from or passing through a vertex must evacuate to the same sink, and most known results on the k-sink problem adopt the confluent model. When the edge capacities are uniform (resp. general), our algorithms for non-confluent flow in the path networks run in O(n + k² log² n) (resp. O(n log(n) + k² log⁵ n)) time, where n is the number of vertices. Our algorithms for cycle networks run in O(k²n log² n) (resp. O(k²n log⁵ n)) time, when the edge capacities are uniform (resp. general).
Cite as
Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, and Junichi Teruyama. Locating Evacuation Centers Optimally in Path and Cycle Networks. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{benkoczi_et_al:OASIcs.ATMOS.2021.13,
author = {Benkoczi, Robert and Bhattacharya, Binay and Higashikawa, Yuya and Kameda, Tsunehiko and Katoh, Naoki and Teruyama, Junichi},
title = {{Locating Evacuation Centers Optimally in Path and Cycle Networks}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {13:1--13:19},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.13},
URN = {urn:nbn:de:0030-drops-148825},
doi = {10.4230/OASIcs.ATMOS.2021.13},
annote = {Keywords: Efficient algorithms, facility location, minmax sink, evacuation problem, dynamic flow in network}
}
Document
Distance-Based Solution of Patrolling Problems with Individual Waiting Times
Abstract
In patrolling problems, robots (or other vehicles) must perpetually visit certain points without exceeding given individual waiting times. Some obvious applications are monitoring, maintenance, and periodic fetching of resources. We propose a new generic formulation of the problem. As its main advantage, it enables a reduction of the multi-robot case to the one-robot case in a certain graph/hypergraph pair, which also relates the problem to some classic path problems in graphs: NP-hardness is shown by a reduction from the Hamiltonian cycle problem, and on the positive side, the formulation allows solution heuristics using distances in the mentioned graph. We demonstrate this approach for the case of two robots patrolling on a line, a problem whose complexity status is open, apart from approximation results. Specifically, we solve all instances with up to 6 equidistant points, and we find some surprising effects, e.g., critical problem instances (which are feasible instances that become infeasible when any waiting time is diminished) may contain rather large individual waiting times.
Cite as
Peter Damaschke. Distance-Based Solution of Patrolling Problems with Individual Waiting Times. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{damaschke:OASIcs.ATMOS.2021.14,
author = {Damaschke, Peter},
title = {{Distance-Based Solution of Patrolling Problems with Individual Waiting Times}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {14:1--14:14},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.14},
URN = {urn:nbn:de:0030-drops-148838},
doi = {10.4230/OASIcs.ATMOS.2021.14},
annote = {Keywords: Patrolling, Periodic scheduling, Shortest path, Well-quasi ordering}
}
Document
Transfer Customization with the Trip-Based Public Transit Routing Algorithm
Abstract
In the context of routing in public transit networks, we consider the issue of the customization of walking transfer times, which is incompatible with the preprocessing required by many state-of-the-art algorithms. We propose to extend one of those, the Trip-Based Public Transit Routing algorithm, to take into account at query time user defined transfer speed and maximum transfer duration. The obtained algorithm is optimal for the bicriteria problem of optimizing minimum arrival time and number of transfers. It is tested on two large data sets and the query times are compatible with real-time queries in a production context.
Cite as
Vassilissa Lehoux-Lebacque and Christelle Loiodice. Transfer Customization with the Trip-Based Public Transit Routing Algorithm. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{lehouxlebacque_et_al:OASIcs.ATMOS.2021.15,
author = {Lehoux-Lebacque, Vassilissa and Loiodice, Christelle},
title = {{Transfer Customization with the Trip-Based Public Transit Routing Algorithm}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {15:1--15:17},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.15},
URN = {urn:nbn:de:0030-drops-148845},
doi = {10.4230/OASIcs.ATMOS.2021.15},
annote = {Keywords: Public transit, Route planning, Algorithms, Customization}
}
Document
An Improved Scheduling Algorithm for Traveling Tournament Problem with Maximum Trip Length Two
Abstract
The Traveling Tournament Problem(TTP) is a combinatorial optimization problem where we have to give a scheduling algorithm which minimizes the total distance traveled by all the participating teams of a double round-robin tournament maintaining given constraints. Most of the instances of this problem with more than ten teams are still unsolved. By definition of the problem the number of teams participating has to be even. There are different variants of this problem depending on the constraints. In this problem, we consider the case where number of teams is a multiple of four and a team can not play more than two consecutive home or away matches. Our scheduling algorithm gives better result than the existing best result for number of teams less or equal to 32.
Cite as
Diptendu Chatterjee and Bimal Kumar Roy. An Improved Scheduling Algorithm for Traveling Tournament Problem with Maximum Trip Length Two. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{chatterjee_et_al:OASIcs.ATMOS.2021.16,
author = {Chatterjee, Diptendu and Roy, Bimal Kumar},
title = {{An Improved Scheduling Algorithm for Traveling Tournament Problem with Maximum Trip Length Two}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {16:1--16:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.16},
URN = {urn:nbn:de:0030-drops-148850},
doi = {10.4230/OASIcs.ATMOS.2021.16},
annote = {Keywords: Traveling Tournament Problem, Double Round-robin, Scheduling, Approximation}
}
Document
Short Paper
Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper)
Abstract
In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.
Cite as
Güvenç Şahin, Amin Ahmadi Digehsara, and Ralf Borndörfer. Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper). In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 17:1-17:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{sahin_et_al:OASIcs.ATMOS.2021.17,
author = {\c{S}ahin, G\"{u}ven\c{c} and Ahmadi Digehsara, Amin and Bornd\"{o}rfer, Ralf},
title = {{Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {17:1--17:6},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.17},
URN = {urn:nbn:de:0030-drops-148863},
doi = {10.4230/OASIcs.ATMOS.2021.17},
annote = {Keywords: public transportation, line planning, multi-period planning, local branching, constraint propagation}
}
Document
Short Paper
An Integrated Model for Rapid and Slow Transit Network Design (Short Paper)
Abstract
Usually, when a rapid transit line is planned a less efficient system already partially covers the demand of the new line. Thus, when the rapid transit starts its regular services, the slow mode (e.g. bus lines) have to be cancelled or their routes modified. Usually this process is planned according to a sequential way. Firstly, the rapid transit line is designed taking into account private and public flows, and possibly surveys on mobility in order to predict the future utilization of the new infrastructure and/or other criteria. Then, in a second stage, the bus route network is redesigned. However, this sequential process can lead to a suboptimal solution, for which reason in this paper a cooperative model for rapid and slow transit network design is studied. The aim is to design simultaneously both networks and the objective is to maximize the number of passengers captured by both public modes against the private mode. We present a mathematical programming formulation and solve the problem by an improved Benders decomposition approach.
Cite as
Natividad González-Blanco, Antonio J. Lozano, Vladimir Marianov, and Juan A. Mesa. An Integrated Model for Rapid and Slow Transit Network Design (Short Paper). In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 18:1-18:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{gonzalezblanco_et_al:OASIcs.ATMOS.2021.18,
author = {Gonz\'{a}lez-Blanco, Natividad and Lozano, Antonio J. and Marianov, Vladimir and Mesa, Juan A.},
title = {{An Integrated Model for Rapid and Slow Transit Network Design}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {18:1--18:6},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.18},
URN = {urn:nbn:de:0030-drops-148871},
doi = {10.4230/OASIcs.ATMOS.2021.18},
annote = {Keywords: Network Design, Rapid Transit, Benders decomposition}
}
Document
Short Paper
A Column Generation-Based Heuristic for the Line Planning Problem with Service Levels (Short Paper)
Abstract
This paper addresses the line planning problem by the combination of existing models reinforced with realistic characteristics like lines frequencies intervals or maximum number of lines, useful for public transportation companies. The problem is solved by an innovative, easily implementable, heuristic combining column generation and elementary column enumeration methods. In this paper, the operator’s exploitation costs are minimized while respecting new quality of service parameters addressed to passengers. Furthermore, a case study based on a real network is performed and described in this paper to prove the efficiency of our method.
Cite as
Hector Gatt, Jean-Marie Freche, Fabien Lehuédé, and Thomas G. Yeung. A Column Generation-Based Heuristic for the Line Planning Problem with Service Levels (Short Paper). In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 19:1-19:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{gatt_et_al:OASIcs.ATMOS.2021.19,
author = {Gatt, Hector and Freche, Jean-Marie and Lehu\'{e}d\'{e}, Fabien and Yeung, Thomas G.},
title = {{A Column Generation-Based Heuristic for the Line Planning Problem with Service Levels}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {19:1--19:6},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.19},
URN = {urn:nbn:de:0030-drops-148885},
doi = {10.4230/OASIcs.ATMOS.2021.19},
annote = {Keywords: Line Planning, Network Design, Column Generation, Service Performance}
}