22 Search Results for "Kontogiannis, Spyros"

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.2022.12
REX: A Realistic Time-Dependent Model for Multimodal Public Transport

Authors: Spyros Kontogiannis, Paraskevi-Maria-Malevi Machaira, Andreas Paraskevopoulos, and Christos Zaroliagis

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract
We present the non-FIFO time-dependent graph model with REalistic vehicle eXchange times (REX) for schedule-based multimodal public transport, along with a novel query algorithm called TRIP-based LAbel-correction propagation (TRIPLA) algorithm that efficiently solves the realistic earliest-arrival routing problem. The REX model possesses all strong features of previous time-dependent graph models without suffering from their deficiencies. It handles non-negligible exchanges from one vehicle to another, as well as supports non-FIFO instances which are typical in public transport, without compromising space efficiency. We conduct a thorough experimental evaluation with real-world data which demonstrates that TRIPLA significantly outperforms all state-of-the-art query algorithms for multimodal earliest-arrival routing in schedule-based public transport.
Cite as

Spyros Kontogiannis, Paraskevi-Maria-Malevi Machaira, Andreas Paraskevopoulos, and Christos Zaroliagis. REX: A Realistic Time-Dependent Model for Multimodal Public Transport. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2022.12,
  author =	{Kontogiannis, Spyros and Machaira, Paraskevi-Maria-Malevi and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{REX: A Realistic Time-Dependent Model for Multimodal Public Transport}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{12:1--12:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.12},
  URN =		{urn:nbn:de:0030-drops-171164},
  doi =		{10.4230/OASIcs.ATMOS.2022.12},
  annote =	{Keywords: multimodal journey planning, REX model, TRIPLA query algorithm, schedule-based timetables}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.8
Time-Dependent Alternative Route Planning

Authors: Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos D. Zaroliagis

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
We present a new method for computing a set of alternative origin-to-destination routes in road networks with an underlying time-dependent metric. The resulting set is aggregated in the form of a time-dependent alternative graph and is characterized by minimum route overlap, small stretch factor, small size and low complexity. To our knowledge, this is the first work that deals with the time-dependent setting in the framework of alternative routes. Based on preprocessed minimum travel-time information between a small set of nodes and all other nodes in the graph, our algorithm carries out a collection phase for candidate alternative routes, followed by a pruning phase that cautiously discards uninteresting or low-quality routes from the candidate set. Our experimental evaluation on real time-dependent road networks demonstrates that the new algorithm performs much better (by one or two orders of magnitude) than existing baseline approaches. In particular, the entire alternative graph can be computed in less than 0.384sec for the road network of Germany, and in less than 1.24sec for that of Europe. Our approach provides also "quick-and-dirty" results of decent quality, in about 1/300 of the above mentioned query times for continental-size instances.
Cite as

Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos D. Zaroliagis. Time-Dependent Alternative Route Planning. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2020.8,
  author =	{Kontogiannis, Spyros and Paraskevopoulos, Andreas and Zaroliagis, Christos D.},
  title =	{{Time-Dependent Alternative Route Planning}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{8:1--8:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.8},
  URN =		{urn:nbn:de:0030-drops-131441},
  doi =		{10.4230/OASIcs.ATMOS.2020.8},
  annote =	{Keywords: time-dependent shortest path, alternative routes, travel-time oracle, plateau and penalty methods}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.9
Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations

Authors: Spyros Kontogiannis, Anastasios Papadopoulos, Andreas Paraskevopoulos, and Christos Zaroliagis

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
We aim at exploiting parallelism in shared-memory multiprocessing systems, in order to speed up the execution time with as small redundancy in work as possible, for an elementary task that comes up frequently as a subroutine in the daily maintenance of large-scale time-dependent graphs representing real-world relationships or technological networks: the many-to-all time-dependent shortest paths (MATDSP) problem. MATDSP requires the computation of one time-dependent shortest-path tree (TDSPT) per origin-vertex and departure-time, from an arbitrary collection of pairs of origins and departure-times, towards all reachable destinations in the graph. Our goal is to explore the potential and highlight the limitations of amorphous data parallelism, when dealing with MATDSP in multicore computing environments with a given amount of processing elements and a shared memory to exploit. Apart from speeding-up execution time, consumption of resources (and energy) is also critical. Therefore, we aim at limiting the work overhead for solving a MATDSP instance, as measured by the overall number of arc relaxations in shortest-path computations, while trying to minimize the overall execution time. Towards this direction, we provide several algorithmic engineering interventions for solving MATDSP concerning: (i) the compact representation of the instance; (ii) the choice and the improvement of the time-dependent single-source shortest path algorithm that is used as a subroutine; (iii) the way according to which the overall work is allocated to the processing elements; (iv) the adoption of the amorphous data parallelism rationale, in order to avoid costly synchronization among the processing elements while doing their own part of the work. Our experimental evaluations, both on real-world and on synthetic benchmark instances of time-dependent road networks, provide insight how one should organize heavy MATDSP computations, depending on the application scenario. This insight is in some cases rather unexpected. For instance, it is not always the case that pure data parallelism (among otherwise totally independent processors) is the best choice for minimizing execution times. In certain cases it may be worthwhile to limit the level of data parallelism in favor of algorithmic parallelism, in order to achieve more efficient MATDSP computations.
Cite as

Spyros Kontogiannis, Anastasios Papadopoulos, Andreas Paraskevopoulos, and Christos Zaroliagis. Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2019.9,
  author =	{Kontogiannis, Spyros and Papadopoulos, Anastasios and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{Exploiting Amorphous Data Parallelism to Speed-Up Massive Time-Dependent Shortest-Path Computations}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{9:1--9:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.9},
  URN =		{urn:nbn:de:0030-drops-114210},
  doi =		{10.4230/OASIcs.ATMOS.2019.9},
  annote =	{Keywords: amorphous data parallelism, delta-stepping algorithm, travel-time oracle, many-to-all shortest paths, time-dependent road networks}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.4
Improved Oracles for Time-Dependent Road Networks

Authors: Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
A novel landmark-based oracle (CFLAT) is presented, which provides earliest-arrival-time route plans in time-dependent road networks. To our knowledge, this is the first oracle that preprocesses combinatorial structures (collections of time-stamped min-travel-time-path trees) rather than travel-time functions. The preprocessed data structure is exploited by a new query algorithm (CFCA) which also computes (and pays for it) the actual connecting path that preserves the theoretical approximation guarantees. To make it practical and tackle the main burden of landmark-based oracles (the large preprocessing requirements), CFLAT is extensively engineered. A thorough experimental evaluation on two real-world benchmark instances shows that CFLAT achieves a significant improvement on preprocessing, approximation guarantees and query-times, in comparison to previous landmark-based oracles. It also achieves competitive query-time performance compared to state-of-art speedup heuristics for time-dependent road networks, whose query-times in most cases do not account for path construction.
Cite as

Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis. Improved Oracles for Time-Dependent Road Networks. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2017.4,
  author =	{Kontogiannis, Spyros and Papastavrou, Georgia and Paraskevopoulos, Andreas and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Improved Oracles for Time-Dependent Road Networks}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{4:1--4:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.4},
  URN =		{urn:nbn:de:0030-drops-78954},
  doi =		{10.4230/OASIcs.ATMOS.2017.4},
  annote =	{Keywords: Time-dependent shortest paths, FIFO property, Distance oracles}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.47
Hierarchical Time-Dependent Oracles

Authors: Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study networks obeying time-dependent min-cost path metrics, and present novel oracles for them which provably achieve two unique features: (i) subquadratic preprocessing time and space, independent of the metric’s amount of disconcavity; (ii) sublinear query time, in either the network size or the actual Dijkstra-Rank of the query at hand.
Cite as

Spyros Kontogiannis, Dorothea Wagner, and Christos Zaroliagis. Hierarchical Time-Dependent Oracles. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:LIPIcs.ISAAC.2016.47,
  author =	{Kontogiannis, Spyros and Wagner, Dorothea and Zaroliagis, Christos},
  title =	{{Hierarchical Time-Dependent Oracles}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.47},
  URN =		{urn:nbn:de:0030-drops-68170},
  doi =		{10.4230/LIPIcs.ISAAC.2016.47},
  annote =	{Keywords: Time-dependent shortest paths, FIFO property, Distance oracles}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2011
OASIcs, Volume 20, ATMOS'11, Complete Volume

Authors: Alberto Caprara and Spyros Kontogiannis

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
OASIcs, Volume 20, ATMOS'11, Complete Volume
Cite as

11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{caprara_et_al:OASIcs.ATMOS.2011,
  title =	{{OASIcs, Volume 20, ATMOS'11, Complete Volume}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011},
  URN =		{urn:nbn:de:0030-drops-35824},
  doi =		{10.4230/OASIcs.ATMOS.2011},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2011.i
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Alberto Caprara and Spyros Kontogiannis

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Frontmatter, Table of contents, Preface, Workshop Organization
Cite as

11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. i-ix, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{caprara_et_al:OASIcs.ATMOS.2011.i,
  author =	{Caprara, Alberto and Kontogiannis, Spyros},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{i--ix},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.i},
  URN =		{urn:nbn:de:0030-drops-32618},
  doi =		{10.4230/OASIcs.ATMOS.2011.i},
  annote =	{Keywords: Frontmatter, Table of contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.1
Real-time traffic control in railway systems

Authors: Carlo Manino

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Despite the constantly increasing demand of passengers and goods transport in Europe, the share of railway traffic is decreasing. One major reason appears to be congestion, which in turn results in frequent delays and in a general unreliability of the system. This fact has triggered the study of efficient ways to manage railway traffic, both off-line and real-time, by means of optimization and mathematical programming techniques. And yet, to our knowledge, there are only a few fully automated real-time traffic control systems which are actually in operation in the European railway system; in most cases such systems only control very simple lines and actually they only support the activity of human dispatchers. We describe here two recent optimization based applications to real-time traffic control which have actually been put into operation in the Italian railways. One such system has been able to fully control the trains in the terminal stations of Milano metro system. The other one will be fully operative by the end of 2012, when it will control the trains on several Italian single-track railways. Both systems heavily rely on mixed integer programming techniques to elaborate good quality timetables in real time.
Cite as

Carlo Manino. Real-time traffic control in railway systems. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{manino:OASIcs.ATMOS.2011.1,
  author =	{Manino, Carlo},
  title =	{{Real-time traffic control in railway systems}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.1},
  URN =		{urn:nbn:de:0030-drops-32623},
  doi =		{10.4230/OASIcs.ATMOS.2011.1},
  annote =	{Keywords: Railway systems, traffic control}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.15
A bilevel rescheduling framework for optimal inter-area train coordination

Authors: Francesco Corman, Andrea D'Ariano, Dario Pacciarelli, and Marco Pranzo

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Railway dispatchers reschedule trains in real-time in order to limit the propagation of disturbances and to regulate traffic in their respective dispatching areas by minimizing the deviation from the off-line timetable. However, the decisions taken in one area may influence the quality and even the feasibility of train schedules in the other areas. Regional control centers coordinate the dispatchers' work for multiple areas in order to regulate traffic at the global level and to avoid situations of global infeasibility. Differently from the dispatcher problem, the coordination activity of regional control centers is still underinvestigated, even if this activity is a key factor for effective traffic management. This paper studies the problem of coordinating several dispatchers with the objective of driving their behavior towards globally optimal solutions. With our model, a coordinator may impose constraints at the border of each dispatching area. Each dispatcher must then schedule trains in its area by producing a locally feasible solution compliant with the border constraints imposed by the coordinator. The problem faced by the coordinator is therefore a bilevel programming problem in which the variables controlled by the coordinator are the border constraints. We demonstrate that the coordinator problem can be solved to optimality with a branch and bound procedure. The coordination algorithm has been tested on a large real railway network in the Netherlands with busy traffic conditions. Our experimental results show that a proven optimal solution is frequently found for various network divisions within computation times compatible with real-time operations.
Cite as

Francesco Corman, Andrea D'Ariano, Dario Pacciarelli, and Marco Pranzo. A bilevel rescheduling framework for optimal inter-area train coordination. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 15-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{corman_et_al:OASIcs.ATMOS.2011.15,
  author =	{Corman, Francesco and D'Ariano, Andrea and Pacciarelli, Dario and Pranzo, Marco},
  title =	{{A bilevel rescheduling framework for optimal inter-area train coordination}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{15--26},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.15},
  URN =		{urn:nbn:de:0030-drops-32636},
  doi =		{10.4230/OASIcs.ATMOS.2011.15},
  annote =	{Keywords: Train Delay Minimization, Schedule Coordination, Bilevel Programming}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.27
The Lockmaster's problem

Authors: Sofie Coene and Frits C. R. Spieksma

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Inland waterways form a natural network that is an existing, congestion free infrastructure with capacity for more traffic. The European commission promotes the transportation of goods by ship as it is a reliable, efficient and environmental friendly way of transport. A bottleneck for transportation over water are the locks that manage the water level. The lockmaster's problem concerns the optimal strategy for operating such a lock. In the lockmaster's problem we are given a lock, a set of ships coming from downstream that want to go upstream, and another set of ships coming from upstream that want to go downstream. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper a dynamic programming algorithm (DP) is proposed that solves the lockmaster's problem in polynomial time. We extend this DP to different generalizations that consider weights, water usage, capacity, and (a fixed number of) multiple chambers. Finally, we prove that the problem becomes strongly NP-hard when the number of chambers is part of the input.
Cite as

Sofie Coene and Frits C. R. Spieksma. The Lockmaster's problem. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 27-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{coene_et_al:OASIcs.ATMOS.2011.27,
  author =	{Coene, Sofie and Spieksma, Frits C. R.},
  title =	{{The Lockmaster's problem}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{27--37},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.27},
  URN =		{urn:nbn:de:0030-drops-32647},
  doi =		{10.4230/OASIcs.ATMOS.2011.27},
  annote =	{Keywords: lock scheduling, batch scheduling, dynamic programming, complexity}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.38
Track Allocation in Freight-Train Classification with Mixed Tracks

Authors: Markus Bohlin, Holger Flier, Jens Maue, and Matús Mihalák

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
We consider the process of forming outbound trains from cars of inbound trains at rail-freight hump yards. Given the arrival and departure times as well as the composition of the trains, we study the problem of allocating classification tracks to outbound trains such that every outbound train can be built on a separate classification track. We observe that the core problem can be formulated as a special list coloring problem in interval graphs, which is known to be NP-complete. We focus on an extension where individual cars of different trains can temporarily be stored on a special subset of the tracks. This problem induces several new variants of the list-coloring problem, in which the given intervals can be shortened by cutting off a prefix of the interval. We show that in case of uniform and sufficient track lengths, the corresponding coloring problem can be solved in polynomial time, if the goal is to minimize the total cost associated with cutting off prefixes of the intervals. Based on these results, we devise two heuristics as well as an integer program to tackle the problem. As a case study, we consider a real-world problem instance from the Hallsberg Rangerbangard hump yard in Sweden. Planning over horizons of seven days, we obtain feasible solutions from the integer program in all scenarios, and from the heuristics in most scenarios.
Cite as

Markus Bohlin, Holger Flier, Jens Maue, and Matús Mihalák. Track Allocation in Freight-Train Classification with Mixed Tracks. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 38-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{bohlin_et_al:OASIcs.ATMOS.2011.38,
  author =	{Bohlin, Markus and Flier, Holger and Maue, Jens and Mihal\'{a}k, Mat\'{u}s},
  title =	{{Track Allocation in Freight-Train Classification with Mixed Tracks}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{38--51},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.38},
  URN =		{urn:nbn:de:0030-drops-32658},
  doi =		{10.4230/OASIcs.ATMOS.2011.38},
  annote =	{Keywords: algorithms, complexity, graph theory, railways, scheduling, shunting, train classification, train marshalling, transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.52
Faster Batched Shortest Paths in Road Networks

Authors: Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
We study the problem of computing batched shortest paths in road networks efficiently. Our focus is on computing paths from a single source to multiple targets (one-to-many queries). We perform a comprehensive experimental comparison of several approaches, including new ones. We conclude that a new extension of PHAST (a recent one-to-all algorithm), called RPHAST, has the best performance in most cases, often by orders of magnitude. When used to compute distance tables (many-to-many queries), RPHAST often outperforms all previous approaches.
Cite as

Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Faster Batched Shortest Paths in Road Networks. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 52-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2011.52,
  author =	{Delling, Daniel and Goldberg, Andrew V. and Werneck, Renato F.},
  title =	{{Faster Batched Shortest Paths in Road Networks}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{52--63},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.52},
  URN =		{urn:nbn:de:0030-drops-32663},
  doi =		{10.4230/OASIcs.ATMOS.2011.52},
  annote =	{Keywords: shortest paths, contraction hierarchies, many-to-many, one-to-many}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.64
UniALT for regular language contrained shortest paths on a multi-modal transportation network

Authors: Dominik Kirchler, Leo Liberti, Thomas Pajor, and Roberto Wolfler Calvo

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Shortest paths on road networks can be efficiently calculated using Dijkstra's algorithm (D). In addition to roads, multi-modal transportation networks include public transportation, bicycle lanes, etc. For paths on this type of network, further constraints, e.g., preferences in using certain modes of transportation, may arise. The regular language constrained shortest path problem deals with this kind of problem. It uses a regular language to model the constraints. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (D_RegLC). In this paper we propose an adaption of the speed-up technique uniALT, in order to accelerate D_RegLC. We call our algorithm SDALT. We provide experimental results on a realistic multi-modal public transportation network including time-dependent cost functions on arcs. The experiments show that our algorithm performs well, with speed-ups of a factor 2 to 20.
Cite as

Dominik Kirchler, Leo Liberti, Thomas Pajor, and Roberto Wolfler Calvo. UniALT for regular language contrained shortest paths on a multi-modal transportation network. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 64-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kirchler_et_al:OASIcs.ATMOS.2011.64,
  author =	{Kirchler, Dominik and Liberti, Leo and Pajor, Thomas and Wolfler Calvo, Roberto},
  title =	{{UniALT for regular language contrained shortest paths on a multi-modal transportation network}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{64--75},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.64},
  URN =		{urn:nbn:de:0030-drops-32670},
  doi =		{10.4230/OASIcs.ATMOS.2011.64},
  annote =	{Keywords: time-dependency, ALT, regular language, shortest path, multi-modal}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.76
The Price of Robustness in Timetable Information

Authors: Marc Goerigk, Martin Knoth, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
In timetable information in public transport the goal is to search for a good passenger's path between an origin and a destination. Usually, the travel time and the number of transfers shall be minimized. In this paper, we consider robust timetable information, i.e. we want to identify a path which will bring the passenger to the planned destination even in the case of delays. The classic notion of strict robustness leads to the problem of identifying those changing activities which will never break in any of the expected delay scenarios. We show that this is in general a strongly NP-hard problem. Therefore, we propose a conservative heuristic which identifies a large subset of these robust changing activities in polynomial time by dynamic programming and so allows us to find strictly robust paths efficiently. We also transfer the notion of light robustness, originally introduced for timetabling, to timetable information. In computational experiments we then study the price of strict and light robustness: How much longer is the travel time of a robust path than of a shortest one according to the published schedule? Based on the schedule of high-speed trains within Germany of 2011, we quantitatively explore the trade-off between the level of guaranteed robustness and the increase in travel time. Strict robustness turns out to be too conservative, while light robustness is promising: a modest level of guarantees is achievable at a reasonable price for the majority of passengers.
Cite as

Marc Goerigk, Martin Knoth, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel. The Price of Robustness in Timetable Information. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 76-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{goerigk_et_al:OASIcs.ATMOS.2011.76,
  author =	{Goerigk, Marc and Knoth, Martin and M\"{u}ller-Hannemann, Matthias and Schmidt, Marie and Sch\"{o}bel, Anita},
  title =	{{The Price of Robustness in Timetable Information}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{76--87},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.76},
  URN =		{urn:nbn:de:0030-drops-32680},
  doi =		{10.4230/OASIcs.ATMOS.2011.76},
  annote =	{Keywords: strict and light robustness, delay scenarios, experimental study}
}
  • Refine by Author
  • 8 Kontogiannis, Spyros
  • 5 Zaroliagis, Christos
  • 4 Paraskevopoulos, Andreas
  • 2 Caprara, Alberto
  • 2 Müller-Hannemann, Matthias
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Shared memory algorithms
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 2 Distance oracles
  • 2 FIFO property
  • 2 Time-dependent shortest paths
  • 2 complexity
  • 2 travel-time oracle
  • Show More...

  • Refine by Type
  • 21 document
  • 1 volume

  • Refine by Publication Year
  • 15 2011
  • 1 2008
  • 1 2012
  • 1 2016
  • 1 2017
  • Show More...

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 Imprint Privacy Contact