22 Search Results for "D'Emidio, Mattia"


Volume

OASIcs, Volume 106

22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

ATMOS 2022, September 8-9, 2022, Potsdam, Germany

Editors: Mattia D'Emidio and Niels Lindner

Artifact
Software
D-hash/ShortestBeerDistanceQueries

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


Abstract

Cite as

David Coudert, Andrea D'Ascenzo, Mattia D'Emidio. D-hash/ShortestBeerDistanceQueries (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22461,
   title = {{D-hash/ShortestBeerDistanceQueries}}, 
   author = {Coudert, David and D'Ascenzo, Andrea and D'Emidio, Mattia},
   note = {Software (visited on 2024-11-28)},
   url = {https://github.com/D-hash/ShortestBeerDistanceQueries},
   doi = {10.4230/artifacts.22461},
}
Document
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
Indexing Graphs for Shortest Beer Path Queries

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

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


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

Cite as

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


Copy BibTex To Clipboard

@InProceedings{coudert_et_al:OASIcs.ATMOS.2024.2,
  author =	{Coudert, David and D'Ascenzo, Andrea and D'Emidio, Mattia},
  title =	{{Indexing Graphs for Shortest Beer Path Queries}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{2:1--2:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.2},
  URN =		{urn:nbn:de:0030-drops-211907},
  doi =		{10.4230/OASIcs.ATMOS.2024.2},
  annote =	{Keywords: Graph Algorithms, Indexing Schemes, Beer Distances, Algorithms Engineering}
}
Document
Complete Volume
OASIcs, Volume 106, ATMOS 2022, Complete Volume

Authors: Mattia D'Emidio and Niels Lindner

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


Abstract
OASIcs, Volume 106, ATMOS 2022, Complete Volume

Cite as

22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 1-240, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@Proceedings{demidio_et_al:OASIcs.ATMOS.2022,
  title =	{{OASIcs, Volume 106, ATMOS 2022, Complete Volume}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{1--240},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022},
  URN =		{urn:nbn:de:0030-drops-171036},
  doi =		{10.4230/OASIcs.ATMOS.2022},
  annote =	{Keywords: OASIcs, Volume 106, ATMOS 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Mattia D'Emidio and Niels Lindner

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


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

Cite as

22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{demidio_et_al:OASIcs.ATMOS.2022.0,
  author =	{D'Emidio, Mattia and Lindner, Niels},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{0:i--0:x},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.0},
  URN =		{urn:nbn:de:0030-drops-171040},
  doi =		{10.4230/OASIcs.ATMOS.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles

Authors: Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas

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


Abstract
The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A* heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances.

Cite as

Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas. An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2022.1,
  author =	{Blanco, Marco and Bornd\"{o}rfer, Ralf and Maristany de las Casas, Pedro},
  title =	{{An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{1:1--1:15},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.1},
  URN =		{urn:nbn:de:0030-drops-171052},
  doi =		{10.4230/OASIcs.ATMOS.2022.1},
  annote =	{Keywords: shortest path problem, a-star algorithm, flight trajectory optimization, flight planning, heuristics}
}
Document
A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization

Authors: Ralf Borndörfer, Fabian Danecker, and Martin Weiser

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


Abstract
We present an efficient algorithm that finds a globally optimal solution to the 2D Free Flight Trajectory Optimization Problem (aka Zermelo Navigation Problem) up to arbitrary precision in finite time. The algorithm combines a discrete and a continuous optimization phase. In the discrete phase, a set of candidate paths that densely covers the trajectory space is created on a directed auxiliary graph. Then Yen’s algorithm provides a promising set of discrete candidate paths which subsequently undergo a locally convergent refinement stage. Provided that the auxiliary graph is sufficiently dense, the method finds a path that lies within the convex domain around the global minimizer. From this starting point, the second stage will converge rapidly to the optimum. The density of the auxiliary graph depends solely on the wind field, and not on the accuracy of the solution, such that the method inherits the superior asymptotic convergence properties of the optimal control stage.

Cite as

Ralf Borndörfer, Fabian Danecker, and Martin Weiser. A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2022.2,
  author =	{Bornd\"{o}rfer, Ralf and Danecker, Fabian and Weiser, Martin},
  title =	{{A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{2:1--2:13},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.2},
  URN =		{urn:nbn:de:0030-drops-171068},
  doi =		{10.4230/OASIcs.ATMOS.2022.2},
  annote =	{Keywords: shortest path, flight planning, free flight, discretization error bounds, optimal control, discrete optimization, global optimization}
}
Document
Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling

Authors: Enrico Bortoletto, Niels Lindner, and Berenike Masing

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


Abstract
Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [Borndörfer et al., 2020]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [Bortoletto et al., 2022]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances.

Cite as

Enrico Bortoletto, Niels Lindner, and Berenike Masing. Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bortoletto_et_al:OASIcs.ATMOS.2022.3,
  author =	{Bortoletto, Enrico and Lindner, Niels and Masing, Berenike},
  title =	{{Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{3:1--3:19},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.3},
  URN =		{urn:nbn:de:0030-drops-171075},
  doi =		{10.4230/OASIcs.ATMOS.2022.3},
  annote =	{Keywords: Periodic Timetabling, Tropical Geometry, Neighborhood Search, Mixed-Integer Programming}
}
Document
Greedy Algorithms for the Freight Consolidation Problem

Authors: Zuguang Gao, John R. Birge, Richard Li-Yang Chen, and Maurice Cheung

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


Abstract
We define and study the (ocean) freight consolidation problem (FCP), which plays a crucial role in solving today’s supply chain crisis. Roughly speaking, every day and every hour, a freight forwarder sees a set of shipments and a set of containers at the origin port. There is a shipment cost associated with assigning each shipment to each container. If a container is assigned any shipment, there is also a procurement cost for that container. The FCP aims to minimize the total cost of fulfilling all the shipments, subject to capacity constraints of the containers. In this paper, we show that no constant factor approximation exists for FCP, and propose a series of greedy based heuristics for solving the problem. We also test our heuristics with simulated data and show that our heuristics achieve small optimality gaps.

Cite as

Zuguang Gao, John R. Birge, Richard Li-Yang Chen, and Maurice Cheung. Greedy Algorithms for the Freight Consolidation Problem. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{gao_et_al:OASIcs.ATMOS.2022.4,
  author =	{Gao, Zuguang and Birge, John R. and Chen, Richard Li-Yang and Cheung, Maurice},
  title =	{{Greedy Algorithms for the Freight Consolidation Problem}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{4:1--4:19},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.4},
  URN =		{urn:nbn:de:0030-drops-171086},
  doi =		{10.4230/OASIcs.ATMOS.2022.4},
  annote =	{Keywords: Freight consolidation, heuristics, greedy algorithm}
}
Document
A Bilevel Model for the Frequency Setting Problem

Authors: Hector Gatt, Jean-Marie Freche, Arnaud Laurent, and Fabien Lehuédé

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


Abstract
Based on a partnership between IMT Atlantique and the French company Lumiplan, this work is part of a process of strengthening the Heurès software currently offered by Lumiplan to public transport operators to support their bus and driver scheduling operations. This work addresses the frequency setting problem which aims at defining the frequencies of the bus lines of a network for different time periods of a day. This operation complements a study on line planning with more accurate estimations of the demand, necessary bus types and passengers behaviors. In this paper, the operator’s exploitation costs are minimized while respecting service-levels constraints, based on the predictions of the path choice made by the passengers. The problem is solved by an easily implementable process and a case study based on a real network is presented to show the efficiency of our method.

Cite as

Hector Gatt, Jean-Marie Freche, Arnaud Laurent, and Fabien Lehuédé. A Bilevel Model for the Frequency Setting Problem. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 5:1-5:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{gatt_et_al:OASIcs.ATMOS.2022.5,
  author =	{Gatt, Hector and Freche, Jean-Marie and Laurent, Arnaud and Lehu\'{e}d\'{e}, Fabien},
  title =	{{A Bilevel Model for the Frequency Setting Problem}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{5:1--5:8},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.5},
  URN =		{urn:nbn:de:0030-drops-171091},
  doi =		{10.4230/OASIcs.ATMOS.2022.5},
  annote =	{Keywords: Frequency Setting, Service Performance, Bilevel, Passenger Assignment}
}
Document
Dynamic Traffic Assignment for Electric Vehicles

Authors: Lukas Graf, Tobias Harks, and Prashant Palkar

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


Abstract
We initiate the study of dynamic traffic assignment for electrical vehicles addressing the specific challenges such as range limitations and the possibility of battery recharge at predefined charging locations. We pose the dynamic equilibrium problem within the deterministic queueing model of Vickrey and as our main result, we establish the existence of an energy-feasible dynamic equilibrium. There are three key modeling-ingredients for obtaining this existence result: 1) We introduce a walk-based definition of dynamic traffic flows which allows for cyclic routing behavior as a result of recharging events en route. 2) We use abstract convex feasibility sets in an appropriate function space to model the energy-feasibility of used walks. 3) We introduce the concept of capacitated dynamic equilibrium walk-flows which generalize the former unrestricted dynamic equilibrium path-flows. Viewed in this framework, we show the existence of an energy-feasible dynamic equilibrium by applying an infinite dimensional variational inequality, which in turn requires a careful analysis of continuity properties of the network loading as a result of injecting flow into walks. We complement our theoretical results by a computational study in which we design a fixed-point algorithm computing energy-feasible dynamic equilibria. We apply the algorithm to standard real-world instances from the traffic assignment community illustrating the complex interplay of resulting travel times, energy consumption and prices paid at equilibrium.

Cite as

Lukas Graf, Tobias Harks, and Prashant Palkar. Dynamic Traffic Assignment for Electric Vehicles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{graf_et_al:OASIcs.ATMOS.2022.6,
  author =	{Graf, Lukas and Harks, Tobias and Palkar, Prashant},
  title =	{{Dynamic Traffic Assignment for Electric Vehicles}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{6:1--6:15},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.6},
  URN =		{urn:nbn:de:0030-drops-171104},
  doi =		{10.4230/OASIcs.ATMOS.2022.6},
  annote =	{Keywords: Electromobility, Dynamic Traffic Assignment, Dynamic Flows, Fixed Point Algorithm}
}
Document
Delay Management with Integrated Decisions on the Vehicle Circulations

Authors: Vera Grafe, Alexander Schiewe, and Anita Schöbel

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


Abstract
The task of delay management in public transport is to decide whether a vehicle should wait for a delayed vehicle in order to maintain the connection for transferring passengers. So far, the vehicle circulations are often ignored in the optimization process, although they have an influence on the propagation of the delay through the network. In this paper we consider different ways from literature to incorporate vehicle circulations in the delay management stage of public transport planning. Since the IP formulation for the integrated problem is hard to solve, we investigate bounds and develop several heuristics for the integrated problem. Our experiments on close-to real-world instances show that integrating delay management and decisions on vehicle circulations may reduce the overall delay by up to 39 percent. We also compare the runtimes and objective function values of the different heuristics. We conclude that we can find competitive solutions in a reasonable amount of time.

Cite as

Vera Grafe, Alexander Schiewe, and Anita Schöbel. Delay Management with Integrated Decisions on the Vehicle Circulations. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{grafe_et_al:OASIcs.ATMOS.2022.7,
  author =	{Grafe, Vera and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Delay Management with Integrated Decisions on the Vehicle Circulations}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{7:1--7:18},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.7},
  URN =		{urn:nbn:de:0030-drops-171119},
  doi =		{10.4230/OASIcs.ATMOS.2022.7},
  annote =	{Keywords: Public Transport, Delay Management, Vehicle Circulations, Integer Programming}
}
Document
Algorithms and Hardness for Non-Pool-Based Line Planning

Authors: Irene Heinrich, Philine Schiewe, and Constantin Seebach

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


Abstract
Line planning, i.e. choosing paths which are operated by one vehicle end-to-end, is an important aspect of public transport planning. While there exist heuristic procedures for generating lines from scratch, most theoretical observations consider the problem of choosing lines from a predefined line pool. In this paper, we consider the complexity of the line planning problem when all simple paths can be used as lines. Depending on the cost structure, we show that the problem can be NP-hard even for paths and stars, and that no polynomial time approximation of sub-linear performance is possible. Additionally, we identify polynomially solvable cases and present a pseudo-polynomial solution approach for trees.

Cite as

Irene Heinrich, Philine Schiewe, and Constantin Seebach. Algorithms and Hardness for Non-Pool-Based Line Planning. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{heinrich_et_al:OASIcs.ATMOS.2022.8,
  author =	{Heinrich, Irene and Schiewe, Philine and Seebach, Constantin},
  title =	{{Algorithms and Hardness for Non-Pool-Based Line Planning}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{8:1--8:21},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.8},
  URN =		{urn:nbn:de:0030-drops-171124},
  doi =		{10.4230/OASIcs.ATMOS.2022.8},
  annote =	{Keywords: line planning, public transport, discrete optimization, complexity, algorithm design}
}
Document
The Edge Investment Problem: Upgrading Transit Line Segments with Multiple Investing Parties

Authors: Rowan Hoogervorst, Evelien van der Hurk, Philine Schiewe, Anita Schöbel, and Reena Urban

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


Abstract
Bus Rapid Transit (BRT) systems can provide a fast and reliable service to passengers at lower costs compared to tram, metro and train systems. Therefore, they can be of great value to attract more passengers to use public transport, which is vital in reaching the Paris Agreement Targets. However, the main advantage of BRT systems, namely their flexible implementation, also leads to the risk that the system is only implemented partially to save costs. This paper focuses therefore on the Edge Investment Problem: Which edges (segments) of a bus line should be upgraded to full-level BRT? Motivated by the construction of a new BRT line around Copenhagen, we consider a setting in which multiple parties are responsible for different segments of the line. Each party has a limited budget and can adjust its investments according to the benefits provided to its passengers. We suggest two ways to determine the number of newly attracted passengers, prove that the corresponding problems are NP-hard and identify special cases that can be solved in polynomial time. In addition, problem relaxations are presented that yield dual bounds. Moreover, we perform an extensive numerical comparison in which we evaluate the extent to which these two ways of modeling demand impact the computational performance and the choice of edges to be upgraded.

Cite as

Rowan Hoogervorst, Evelien van der Hurk, Philine Schiewe, Anita Schöbel, and Reena Urban. The Edge Investment Problem: Upgrading Transit Line Segments with Multiple Investing Parties. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hoogervorst_et_al:OASIcs.ATMOS.2022.9,
  author =	{Hoogervorst, Rowan and van der Hurk, Evelien and Schiewe, Philine and Sch\"{o}bel, Anita and Urban, Reena},
  title =	{{The Edge Investment Problem: Upgrading Transit Line Segments with Multiple Investing Parties}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{9:1--9:19},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.9},
  URN =		{urn:nbn:de:0030-drops-171137},
  doi =		{10.4230/OASIcs.ATMOS.2022.9},
  annote =	{Keywords: Network Design, Public Transport, Bus Rapid Transit, Modeling}
}
  • Refine by Author
  • 7 D'Emidio, Mattia
  • 3 D'Ascenzo, Andrea
  • 3 Lindner, Niels
  • 2 Borndörfer, Ralf
  • 2 Coudert, David
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Public Transport
  • 2 Timetabling
  • 2 discrete optimization
  • 2 flight planning
  • 2 heuristics
  • Show More...

  • Refine by Type
  • 20 document
  • 1 artifact
  • 1 volume

  • Refine by Publication Year
  • 18 2022
  • 3 2024
  • 1 2014

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