18 Search Results for "Liberti, Leo"

Volume

OASIcs, Volume 25

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

ATMOS 2012, September 13, 2012, Ljubljana, Slovenia

Editors: Daniel Delling and Leo Liberti

Document
DOI: 10.4230/LIPIcs.SEA.2022.21
Practical Performance of Random Projections in Linear Programming

Authors: Leo Liberti, Benedetto Manca, and Pierre-Louis Poirion

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
The use of random projections in mathematical programming allows standard solution algorithms to solve instances of much larger sizes, at least approximately. Approximation results have been derived in the relevant literature for many specific problems, as well as for several mathematical programming subclasses. Despite the theoretical developments, it is not always clear that random projections are actually useful in solving mathematical programs in practice. In this paper we provide a computational assessment of the application of random projections to linear programming.
Cite as

Leo Liberti, Benedetto Manca, and Pierre-Louis Poirion. Practical Performance of Random Projections in Linear Programming. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 21:1-21:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liberti_et_al:LIPIcs.SEA.2022.21,
  author =	{Liberti, Leo and Manca, Benedetto and Poirion, Pierre-Louis},
  title =	{{Practical Performance of Random Projections in Linear Programming}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.21},
  URN =		{urn:nbn:de:0030-drops-165550},
  doi =		{10.4230/LIPIcs.SEA.2022.21},
  annote =	{Keywords: Linear Programming, Johnson-Lindenstrauss Lemma, Computational testing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.5
The Isomap Algorithm in Distance Geometry

Authors: Leo Liberti and Claudia D'Ambrosio

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
The fundamental problem of distance geometry consists in finding a realization of a given weighted graph in a Euclidean space of given dimension, in such a way that vertices are realized as points and edges as straight segments having the same lengths as their given weights. This problem arises in structural proteomics, wireless sensor networks, and clock synchronization protocols to name a few applications. The well-known Isomap method is a dimensionality reduction heuristic which projects finite but high dimensional metric spaces into the "most significant" lower dimensional ones, where significance is measured by the magnitude of the corresponding eigenvalues. We start from a simple observation, namely that Isomap can also be used to provide approximate realizations of weighted graphs very efficiently, and then derive and benchmark six new heuristics.
Cite as

Leo Liberti and Claudia D'Ambrosio. The Isomap Algorithm in Distance Geometry. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 5:1-5:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{liberti_et_al:LIPIcs.SEA.2017.5,
  author =	{Liberti, Leo and D'Ambrosio, Claudia},
  title =	{{The Isomap Algorithm in Distance Geometry}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.5},
  URN =		{urn:nbn:de:0030-drops-76079},
  doi =		{10.4230/LIPIcs.SEA.2017.5},
  annote =	{Keywords: distance geometry problem, protein conformation, heuristics}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2012
OASIcs, Volume 25, ATMOS'12, Complete Volume

Authors: Daniel Delling and Leo Liberti

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
OASIcs, Volume 25, ATMOS'12, Complete Volume
Cite as

Daniel Delling and Leo Liberti. OASIcs, Volume 25, ATMOS'12, Complete Volume. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

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

Authors: Daniel Delling and Leo Liberti

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

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

Daniel Delling and Leo Liberti. Frontmatter, Table of Contents, Preface, Workshop Organization. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. i-xi, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{delling_et_al:OASIcs.ATMOS.2012.i,
  author =	{Delling, Daniel and Liberti, Leo},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{i--xi},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.i},
  URN =		{urn:nbn:de:0030-drops-36980},
  doi =		{10.4230/OASIcs.ATMOS.2012.i},
  annote =	{Keywords: Frontmatter, Table of contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.1
A Fast Heuristic Algorithm for the Train Unit Assignment Problem

Authors: Valentina Cacchiani, Alberto Caprara, and Paolo Toth

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
In this paper we study a railway optimization problem known as the Train Unit Assignment Problem. A train unit consists of a self-contained train with an engine and a set of wagons with passenger seats. Given a set of timetabled train trips, each with a required number of passenger seats, and a set of train units, each with a given number of available seats, the problem calls for the best assignment of the train units to the trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. We propose a heuristic algorithm based on the computation of a lower bound obtained by solving an Integer Linear Programming model that gives the optimal solution in a "peak period" of the day. The performance of the heuristic algorithm is computationally evaluated on real-world instances provided by a regional Italian Train Operator. The results are compared with those of existing methods from the literature, showing that the new method is able to obtain solutions of good quality in much shorter computing times.
Cite as

Valentina Cacchiani, Alberto Caprara, and Paolo Toth. A Fast Heuristic Algorithm for the Train Unit Assignment Problem. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 1-9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2012.1,
  author =	{Cacchiani, Valentina and Caprara, Alberto and Toth, Paolo},
  title =	{{A Fast Heuristic Algorithm for the Train Unit Assignment Problem}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.1},
  URN =		{urn:nbn:de:0030-drops-36971},
  doi =		{10.4230/OASIcs.ATMOS.2012.1},
  annote =	{Keywords: Train Unit Assignment, Heuristic Algorithm, ILP model, Real-world instances}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.10
Optimal Freight Train Classification using Column Generation

Authors: Markus Bohlin, Florian Dahms, Holger Flier, and Sara Gestrelius

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
We consider planning of freight train classification at hump yards using integer programming. The problem involves the formation of departing freight trains from arriving trains subject to scheduling and capacity constraints. To increase yard capacity, we allow the temporary storage of early freight cars on specific mixed-usage tracks. The problem has previously been modeled using a direct integer programming model, but this approach did not yield lower bounds of sufficient quality to prove optimality. In this paper, we formulate a new extended integer programming model and design a column generation approach based on branch-and-price to solve problem instances of industrial size. We evaluate the method on historical data from the Hallsberg hump yard in Sweden, and compare the results with previous approaches. The new method managed to find optimal solutions in all of the 192 problem instances tried. Furthermore, no instance took more than 13 minutes to solve to optimality using fairly standard computer hardware.
Cite as

Markus Bohlin, Florian Dahms, Holger Flier, and Sara Gestrelius. Optimal Freight Train Classification using Column Generation. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 10-22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bohlin_et_al:OASIcs.ATMOS.2012.10,
  author =	{Bohlin, Markus and Dahms, Florian and Flier, Holger and Gestrelius, Sara},
  title =	{{Optimal Freight Train Classification using Column Generation}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{10--22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.10},
  URN =		{urn:nbn:de:0030-drops-36997},
  doi =		{10.4230/OASIcs.ATMOS.2012.10},
  annote =	{Keywords: Column generation, integer programming, scheduling, shunting, classification, marshalling, transportation, railways}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.23
Real Time Railway Traffic Management Modeling Track-Circuits

Authors: Paola Pellegrini, Grégory Marlière, and Joaquin Rodriguez

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
The real time railway traffic management seeks for the train routing and scheduling that minimize delays after an unexpected event perturbs the operations. In this paper, we propose a mixed-integer linear programming formulation for tackling this problem, modeling the infrastructure in terms of track-circuits, which are the basic components for train detection. This formulation considers all possible alternatives for train rerouting in the infrastructure and all rescheduling alternatives for trains along these routes. To the best of our knowledge, we present the first formulation that solves this problem to optimality. We tested the proposed formulation on real perturbation instances representing traffic in a control area including the Lille Flandres station (France), achieving very good performance in terms of computation time.
Cite as

Paola Pellegrini, Grégory Marlière, and Joaquin Rodriguez. Real Time Railway Traffic Management Modeling Track-Circuits. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 23-34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{pellegrini_et_al:OASIcs.ATMOS.2012.23,
  author =	{Pellegrini, Paola and Marli\`{e}re, Gr\'{e}gory and Rodriguez, Joaquin},
  title =	{{Real Time Railway Traffic Management Modeling Track-Circuits}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{23--34},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.23},
  URN =		{urn:nbn:de:0030-drops-37004},
  doi =		{10.4230/OASIcs.ATMOS.2012.23},
  annote =	{Keywords: real time railway traffic management, mixed-integer linear programming, track-circuit, complex junction}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.35
Reliability and Delay Distributions of Train Connections

Authors: Mohammad H. Keyhani, Mathias Schnee, Karsten Weihe, and Hans-Peter Zorn

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
Finding reliable train connections is a considerable issue in timetable information since train delays perturb the timetable daily. We present an effective probabilistic approach for estimating the reliability of connections in a large train network. Experiments on real customer queries and real timetables for all trains in Germany show that our approach can be implemented to deliver good results at the expense of only little processing time. Based on probability distributions for train events in connections, we estimate the reliability of connections. We have analyzed our computed reliability ratings by validating our predictions against real delay data from German Railways. This study shows that we are able to predict the feasibility of connections very well. In essence, our predictions are slightly optimistic for connections with a high rating and pretty accurate for connections with a medium rating. Only for the rare cases of a very low rating, we are too pessimistic. Our probabilistic approach already delivers good results, still has improvement potential, and offers a new perspective in the search for more reliable connections in order to bring passengers safely to their destinations even in case of delays.
Cite as

Mohammad H. Keyhani, Mathias Schnee, Karsten Weihe, and Hans-Peter Zorn. Reliability and Delay Distributions of Train Connections. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 35-46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{keyhani_et_al:OASIcs.ATMOS.2012.35,
  author =	{Keyhani, Mohammad H. and Schnee, Mathias and Weihe, Karsten and Zorn, Hans-Peter},
  title =	{{Reliability and Delay Distributions of Train Connections}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{35--46},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.35},
  URN =		{urn:nbn:de:0030-drops-37014},
  doi =		{10.4230/OASIcs.ATMOS.2012.35},
  annote =	{Keywords: Stochastic Delay Propagation, Timetable Information, Connection Reliability}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.47
A Direct Connection Approach to Integrated Line Planning and Passenger Routing

Authors: Ralf Borndörfer and Marika Karbstein

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.
Cite as

Ralf Borndörfer and Marika Karbstein. A Direct Connection Approach to Integrated Line Planning and Passenger Routing. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 47-57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2012.47,
  author =	{Bornd\"{o}rfer, Ralf and Karbstein, Marika},
  title =	{{A Direct Connection Approach to Integrated Line Planning and Passenger Routing}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{47--57},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.47},
  URN =		{urn:nbn:de:0030-drops-37027},
  doi =		{10.4230/OASIcs.ATMOS.2012.47},
  annote =	{Keywords: combinatorial optimization, line planning, transfers, passenger routing}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.58
Multi-Dimensional Commodity Covering for Tariff Selection in Transportation

Authors: Felix G. König, Jannik Matuschke, and Alexander Richter

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
In this paper, we study a multi-dimensional commodity covering problem, which we encountered as a subproblem in optimizing large scale transportation networks in logistics. The problem asks for a selection of containers for transporting a given set of commodities, each commodity having different extensions of properties such as weight or volume. Each container can be selected multiple times and is specified by a fixed charge and capacities in the relevant properties. The task is to find a cost minimal collection of containers and a feasible assignment of the demand to all selected containers. From theoretical point of view, by exploring similarities to the well known SetCover problem, we derive NP-hardness and see that the non-approximability result known for set cover also carries over to our problem. For practical applications we need very fast heuristics to be integrated into a meta-heuristic framework that - depending on the context - either provide feasible near optimal solutions or only estimate the cost value of an optimal solution. We develop and analyze a flexible family of greedy algorithms that meet these challenges. In order to find best-performing configurations for different requirements of the meta-heuristic framework, we provide an extensive computational study on random and real world instance sets obtained from our project partner 4flow AG. We outline a trade-off between running times and solution quality and conclude that the proposed methods achieve the accuracy and efficiency necessary for serving as a key ingredient in more complex meta-heuristics enabling the optimization of large-scale networks.
Cite as

Felix G. König, Jannik Matuschke, and Alexander Richter. Multi-Dimensional Commodity Covering for Tariff Selection in Transportation. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 58-70, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{konig_et_al:OASIcs.ATMOS.2012.58,
  author =	{K\"{o}nig, Felix G. and Matuschke, Jannik and Richter, Alexander},
  title =	{{Multi-Dimensional Commodity Covering for Tariff Selection in Transportation}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{58--70},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.58},
  URN =		{urn:nbn:de:0030-drops-37034},
  doi =		{10.4230/OASIcs.ATMOS.2012.58},
  annote =	{Keywords: Covering, Heuristics, Transportation, Tariff Selection}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.71
On the Complexity of Partitioning Graphs for Arc-Flags

Authors: Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
Precomputation of auxiliary data in an additional off-line step is a common approach towards improving the performance of shortest-path queries in large-scale networks. One such technique is the arc-flags algorithm, where the preprocessing involves computing a partition of the input graph. The quality of this partition significantly affects the speed-up observed in the query phase. It is evaluated by considering the search-space size of subsequent shortest-path queries, in particular its maximum or its average over all queries. In this paper, we substantially strengthen existing hardness results of Bauer et al. and show that optimally filling this degree of freedom is NP-hard for trees with unit-length edges, even if we bound the height or the degree. On the other hand, we show that optimal partitions for paths can be computed efficiently and give approximation algorithms for cycles and trees.
Cite as

Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner. On the Complexity of Partitioning Graphs for Arc-Flags. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 71-82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.ATMOS.2012.71,
  author =	{Bauer, Reinhard and Baum, Moritz and Rutter, Ignaz and Wagner, Dorothea},
  title =	{{On the Complexity of Partitioning Graphs for Arc-Flags}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{71--82},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.71},
  URN =		{urn:nbn:de:0030-drops-37048},
  doi =		{10.4230/OASIcs.ATMOS.2012.71},
  annote =	{Keywords: shortest paths, arc-flags, search space, preprocessing, complexity}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.83
Speedup Techniques for the Stochastic on-time Arrival Problem

Authors: Samitha Samaranayake, Sebastien Blandin, and Alex Bayen

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
We consider the stochastic on-time arrival (SOTA) routing problem of finding a routing policy that maximizes the probability of reaching a given destination within a pre-specified time budget in a road network with probabilistic link travel-times. The goal of this work is to provide a theoretical understanding of the SOTA problem and present efficient computational techniques to enable the development of practical applications for stochastic routing. We present multiple speedup techniques that include a label-setting algorithm based on the existence of a minimal link travel-time on each road link, advanced convolution methods centered on the Fast Fourier Transform and the idea of zero-delay convolution, and localization techniques for determining an optimal order of policy computation. We describe the algorithms for each speedup technique and analyze their impact on computation time. We also analyze the behavior of the algorithms as a function of the network topology and present numerical results to demonstrate this. Finally, experimental results are provided for the San Francisco Bay Area arterial road network to show how the algorithms would work in an operational setting.
Cite as

Samitha Samaranayake, Sebastien Blandin, and Alex Bayen. Speedup Techniques for the Stochastic on-time Arrival Problem. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 83-96, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{samaranayake_et_al:OASIcs.ATMOS.2012.83,
  author =	{Samaranayake, Samitha and Blandin, Sebastien and Bayen, Alex},
  title =	{{Speedup Techniques for the Stochastic on-time Arrival Problem}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{83--96},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.83},
  URN =		{urn:nbn:de:0030-drops-37050},
  doi =		{10.4230/OASIcs.ATMOS.2012.83},
  annote =	{Keywords: Stochastic routing, Dynamic programming, Traffic information systems}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.97
Optimal Algorithms for Train Shunting and Relaxed List Update Problems

Authors: Tim Nonner and Alexander Souza

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
This paper considers a Train Shunting problem which occurs in cargo train organizations: We have a locomotive travelling along a track segment and a collection of n cars, where each car has a source and a target. Whenever the train passes the source of a car, it needs to be added to the train, and on the target, the respective car needs to be removed. Any such operation at the end of the train incurs low shunting cost, but adding or removing truly in the interior requires a more complex shunting operation and thus yields high cost. The objective is to schedule the adding and removal of cars as to minimize the total cost. This problem can also be seen as a relaxed version of the well-known List Update problem, which may be of independent interest. We derive polynomial time algorithms for Train Shunting by reducing this problem to finding independent sets in bipartite graphs. This allows us to treat several variants of the problem in a generic way. Specifically, we obtain an algorithm with running time O(n^{5/2}) for the uniform case, where all low costs and all high costs are identical, respectively. Furthermore, for the non-uniform case we have running time of O(n^3). Both versions translate to a symmetric variant, where it is also allowed to add and remove cars at the front of the train at low cost. In addition, we formulate a dynamic program with running time O(n^4), which exploits the special structure of the graph. Although the running time is worse, it allows us to solve many extensions, e.g., prize-collection, economies of scale, and dependencies between consecutive stations.
Cite as

Tim Nonner and Alexander Souza. Optimal Algorithms for Train Shunting and Relaxed List Update Problems. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 97-107, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{nonner_et_al:OASIcs.ATMOS.2012.97,
  author =	{Nonner, Tim and Souza, Alexander},
  title =	{{Optimal Algorithms for Train Shunting and Relaxed List Update Problems}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{97--107},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.97},
  URN =		{urn:nbn:de:0030-drops-37066},
  doi =		{10.4230/OASIcs.ATMOS.2012.97},
  annote =	{Keywords: Train shunting, optimal algorithm, independent set, dynamic programming}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2012.108
A Dynamic Row/Column Management Algorithm for Freight Train Scheduling

Authors: Brigitte Jaumard, Thai H. Le, Huaining Tian, Ali Akgunduz, and Peter Finnie

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract
We propose a new dynamic row/column management algorithm for freight train scheduling in a single track railway system. While many papers have already been devoted to train scheduling, previously published optimization models still suffer from scalability issues, even for single track railway systems. Moreover, very few of them take into account the capacity constraints, i.e., the number of alternate tracks in the railway stations/sidings in order for the trains to meet/bypass. We propose an optimization model which takes such constraints into account, while still handling efficiently the other meaningful constraints. We design an original solution scheme with iterative additions/removals of constraints/variables in order to remain with a manageable sized mixed integer linear program at each iteration, without threatening to reach the optimal solution. Numerical results are presented on several data instances of CPR (Canadian Pacific Railway) on the Vancouver-Calgary corridor, one of the most busy corridor in their railway system. Therein, the proposed model and algorithm are used as a planning tool to evaluate the network capacity, i.e., how much the number of trains can be increased without impacting significantly the average travel times between the source and destination stations of the various trains in the corridor. Larger data instances than those previously published are solved accurately (epsilon-optimal solutions) for the schedule of freight trains.
Cite as

Brigitte Jaumard, Thai H. Le, Huaining Tian, Ali Akgunduz, and Peter Finnie. A Dynamic Row/Column Management Algorithm for Freight Train Scheduling. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 108-119, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{jaumard_et_al:OASIcs.ATMOS.2012.108,
  author =	{Jaumard, Brigitte and Le, Thai H. and Tian, Huaining and Akgunduz, Ali and Finnie, Peter},
  title =	{{A Dynamic Row/Column Management Algorithm for Freight Train Scheduling}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{108--119},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.108},
  URN =		{urn:nbn:de:0030-drops-37074},
  doi =		{10.4230/OASIcs.ATMOS.2012.108},
  annote =	{Keywords: Railway optimization, Train scheduling, Single track}
}
  • Refine by Author
  • 5 Liberti, Leo
  • 2 Delling, Daniel
  • 1 Akgunduz, Ali
  • 1 Atkin, Jason
  • 1 Bauer, Reinhard
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Mathematical optimization
  • 1 Theory of computation → Random projections and metric embeddings

  • Refine by Keyword
  • 1 ALT
  • 1 Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications
  • 1 Column generation
  • 1 Computational testing
  • 1 Connection Reliability
  • Show More...

  • Refine by Type
  • 17 document
  • 1 volume

  • Refine by Publication Year
  • 15 2012
  • 1 2011
  • 1 2017
  • 1 2022

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact