24 Search Results for "Mesa, Juan A."


Volume

OASIcs, Volume 7

7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)

ATMOS 2007, November 15-16, 2007, Sevilla, Spain

Editors: Ravindra K. Ahuja, Christian Liebchen, and Juan A. Mesa

Document
Short Paper
An Integrated Model for Rapid and Slow Transit Network Design (Short Paper)

Authors: Natividad González-Blanco, Antonio J. Lozano, Vladimir Marianov, and Juan A. Mesa

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)


Abstract
Usually, when a rapid transit line is planned a less efficient system already partially covers the demand of the new line. Thus, when the rapid transit starts its regular services, the slow mode (e.g. bus lines) have to be cancelled or their routes modified. Usually this process is planned according to a sequential way. Firstly, the rapid transit line is designed taking into account private and public flows, and possibly surveys on mobility in order to predict the future utilization of the new infrastructure and/or other criteria. Then, in a second stage, the bus route network is redesigned. However, this sequential process can lead to a suboptimal solution, for which reason in this paper a cooperative model for rapid and slow transit network design is studied. The aim is to design simultaneously both networks and the objective is to maximize the number of passengers captured by both public modes against the private mode. We present a mathematical programming formulation and solve the problem by an improved Benders decomposition approach.

Cite as

Natividad González-Blanco, Antonio J. Lozano, Vladimir Marianov, and Juan A. Mesa. An Integrated Model for Rapid and Slow Transit Network Design (Short Paper). In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 18:1-18:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{gonzalezblanco_et_al:OASIcs.ATMOS.2021.18,
  author =	{Gonz\'{a}lez-Blanco, Natividad and Lozano, Antonio J. and Marianov, Vladimir and Mesa, Juan A.},
  title =	{{An Integrated Model for Rapid and Slow Transit Network Design}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{18:1--18:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.18},
  URN =		{urn:nbn:de:0030-drops-148871},
  doi =		{10.4230/OASIcs.ATMOS.2021.18},
  annote =	{Keywords: Network Design, Rapid Transit, Benders decomposition}
}
Document
Simultaneous frequency and capacity setting for rapid transit systems with a competing mode and capacity constraints

Authors: Alicia De-Los-Santos, Gilbert Laporte, Juan A. Mesa, and Federico Perea

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)


Abstract
The railway planning problem consists of several consecutive phases: network design, line planning, timetabling, personnel assignment and rolling stocks planning. In this paper we will focus on the line planning process. Traditionally, the line planning problem consists of determining a set of lines and their frequencies optimizing a certain objective. In this work we will focus on the line planning problem context taking into account aspects related to rolling stock and crew operating costs. We assume that the number of possible vehicles is limited, that is, the problem that we are considering is a capacitated problem and the line network can be a crowding network. The main novelty in this paper is the consideration of the size of vehicles and frequencies as variables as well as the inclusion of a congestion function measuring the level of in-vehicle crowding. Concretely, we present the problem and an algorithm to solve it, which are tested via a computational experience.

Cite as

Alicia De-Los-Santos, Gilbert Laporte, Juan A. Mesa, and Federico Perea. Simultaneous frequency and capacity setting for rapid transit systems with a competing mode and capacity constraints. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 107-121, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{delossantos_et_al:OASIcs.ATMOS.2014.107,
  author =	{De-Los-Santos, Alicia and Laporte, Gilbert and Mesa, Juan A. and Perea, Federico},
  title =	{{Simultaneous frequency and capacity setting for rapid transit systems with a competing mode and capacity constraints}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{107--121},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.107},
  URN =		{urn:nbn:de:0030-drops-47563},
  doi =		{10.4230/OASIcs.ATMOS.2014.107},
  annote =	{Keywords: Line planning, railway, capacity, frequency, congestion}
}
Document
Complete Volume
OASIcs, Volume 7, ATMOS'07, Complete Volume

Authors: Christian Liebchen, Ravindra K. Ahuja, and Juan A. Mesa

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
OASIcs, Volume 7, ATMOS'07, Complete Volume

Cite as

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


Copy BibTex To Clipboard

@Proceedings{liebchen_et_al:OASIcs.ATMOS.2007,
  title =	{{OASIcs, Volume 7, ATMOS'07, Complete Volume}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007},
  URN =		{urn:nbn:de:0030-drops-35695},
  doi =		{10.4230/OASIcs.ATMOS.2007},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
ATMOS 2007 Preface -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Authors: Ravindra K. Ahuja, Christian Liebchen, and Juan A. Mesa

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
Proceedings of the 7thWorkshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, held on No- vember 15 and November 16, 2007 in Sevilla, Spain.

Cite as

Ravindra K. Ahuja, Christian Liebchen, and Juan A. Mesa. ATMOS 2007 Preface -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{ahuja_et_al:OASIcs.ATMOS.2007.1237,
  author =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  title =	{{ATMOS 2007 Preface -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{1--7},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1237},
  URN =		{urn:nbn:de:0030-drops-12373},
  doi =		{10.4230/OASIcs.ATMOS.2007.1237},
  annote =	{Keywords: Operations research, scheduled transport, railway optimization}
}
Document
Front Matter
ATMOS 2007 Abstracts Collection -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Authors: Ravindra K. Ahuja, Christian Liebchen, and Juan A. Mesa

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
Proceedings of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, held on November 15 and November 16, 2007 in Sevilla, Spain.

Cite as

7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. i-xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{ahuja_et_al:OASIcs.ATMOS.2007.1184,
  author =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  title =	{{ATMOS 2007 Abstracts Collection -- 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{i--xi},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1184},
  URN =		{urn:nbn:de:0030-drops-11840},
  doi =		{10.4230/OASIcs.ATMOS.2007.1184},
  annote =	{Keywords: Operations research, scheduled transport, railway optimization}
}
Document
01. A new concept of robustness

Authors: Ricardo García, Ángel Marín, Juan A. Mesa, Federico Perea, and Doroteo Verastegui

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
In this paper a new concept of robustness is introduced and the corresponding optimization problem is stated. This new concept is applied to transportation network designs in which the set of scenarios arising from the uncertainty of the parameters follows a probability distribution. The $p$-robustness concept is aimed to problems where the feasibility of the solutions is not affected by the uncertainty of the parameters. In order to compare the solution with those of other already known concepts of robustness, some computational experiments with real data are included.

Cite as

Ricardo García, Ángel Marín, Juan A. Mesa, Federico Perea, and Doroteo Verastegui. 01. A new concept of robustness. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{garcia_et_al:OASIcs.ATMOS.2007.1177,
  author =	{Garc{\'\i}a, Ricardo and Mar{\'\i}n, \'{A}ngel and Mesa, Juan A. and Perea, Federico and Verastegui, Doroteo},
  title =	{{01. A new concept of robustness}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1177},
  URN =		{urn:nbn:de:0030-drops-11779},
  doi =		{10.4230/OASIcs.ATMOS.2007.1177},
  annote =	{Keywords: }
}
Document
02. Applied Railway Optimization in Production Planning at DSB S-tog - tasks, tools and challenges

Authors: Jens Clausen

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
Efficient public transportation is becoming increasingly vital for modern capitals. DSB S-tog a/s is the major supplier of rail traffic on the infrastructure of the city-rail network in Copenhagen. S-tog has experienced a demand for increasing volume and quality of the transportation offered to the customers, and has concurrently been met with demands for higher efficiency in the daily operation. The plans of timetable, rolling stock and crew must hence allow for a high level of customer service, be efficient, and be robust against disturbances of operations. It is a highly non-trivial task to meet these conflicting goals. S-tog has therefore on the strategic level decided to use software with optimization capabilities in the planning processes. We describe the current status for each activity using optimization or simulation as a tool: Timetable evaluation, rolling stock planning, and crew scheduling. In addition we describe on-going efforts in using mathematical models in activities such as timetable design and work-force planning. We also identify some organizatorial key factors, which have paved the way for extended use of optimization methods in railway production planning.

Cite as

Jens Clausen. 02. Applied Railway Optimization in Production Planning at DSB S-tog - tasks, tools and challenges. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 15-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{clausen:OASIcs.ATMOS.2007.1181,
  author =	{Clausen, Jens},
  title =	{{02. Applied Railway Optimization in Production Planning at DSB S-tog - tasks, tools and challenges}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{15--29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1181},
  URN =		{urn:nbn:de:0030-drops-11819},
  doi =		{10.4230/OASIcs.ATMOS.2007.1181},
  annote =	{Keywords: Operations research, urban railways, timetabling, crew, disruption management}
}
Document
03. Disruption Management in PassengerTransportation - from Air to Tracks

Authors: Jens Clausen

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
Over the last 10 years there has been a tremendous growth in air transportation of passengers. Both airports and airspace are close to saturation with respect to capacity, leading to delays caused by disruptions. At the same time the amount of vehicular traffic around and in all larger cities of the world has show a dramatic increase as well. Public transportation by e.g. rail has come into focus, and hence also the service level provided by suppliers ad public transportation. These transportation systems are likewise very vulnerable to disruptions. In the airline industry there is a long tradition for using advanced mathematical models as the basis for planning of resources as aircraft and crew. These methods are now also coming to use in the process of handling disruptions, and robustness of plans has received much interest. Commercial IT-systems supplying decision support for recovery of disrupted operations are becoming available. The use of advanced planning and recovery methods in the railway industry currently gains momentum. The current paper gives a short overview over the methods used for planning and disruption management in the airline industry. The situation regarding railway optimization is then described and discussed. The issue of robustness of timetables and plans for rolling stock and crew is also addressed.

Cite as

Jens Clausen. 03. Disruption Management in PassengerTransportation - from Air to Tracks. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 30-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{clausen:OASIcs.ATMOS.2007.1183,
  author =	{Clausen, Jens},
  title =	{{03. Disruption Management in PassengerTransportation - from Air to Tracks}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{30--47},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1183},
  URN =		{urn:nbn:de:0030-drops-11836},
  doi =		{10.4230/OASIcs.ATMOS.2007.1183},
  annote =	{Keywords: }
}
Document
04. Solution of the Train Platforming Problem

Authors: Alberto Caprara, Laura Galli, and Paolo Toth

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
In this paper we study a general formulation of the train platforming problem, which contains as special cases all the versions previously considered in the literature as well as a case study from the Italian Infrastructure manager that we addressed. In particular, motivated by our case study, we consider a general quadratic objective function, and propose a new way to linearize it by using a small number of new variables along with a set of constraints that can be separated efficiently by solving an appropriate linear program. The resulting integer linear programming formulation has a continuous relaxation that leads to strong bounds on the optimal value. For the instances in our case study, we show that a simple diving heuristic based on this relaxation produces solutions that are much better than those produced by a simple heuristic currently in use, and that often turn out to be (nearly-) optimal.

Cite as

Alberto Caprara, Laura Galli, and Paolo Toth. 04. Solution of the Train Platforming Problem. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 49-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{caprara_et_al:OASIcs.ATMOS.2007.1174,
  author =	{Caprara, Alberto and Galli, Laura and Toth, Paolo},
  title =	{{04. Solution of the Train Platforming Problem}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{49--61},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1174},
  URN =		{urn:nbn:de:0030-drops-11741},
  doi =		{10.4230/OASIcs.ATMOS.2007.1174},
  annote =	{Keywords: Train Platforming, Train Routing, Branch-and-Cut-and-Price, Quadratic Objective Function, Linearization}
}
Document
05. Models for Railway Track Allocation

Authors: Ralf Borndörfer and Thomas Schlechte

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
The optimal track allocation problem (OPTRA) is to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations for this problem: a standard formulation that models block conflicts in terms of packing constraints, and a novel formulation of the `extended' type that is based on additional `configuration' variables. The packing constraints in the standard formulation stem from an interval graph and can therefore be separated in polynomial time. It follows that the LP-relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the LP-relaxation of the extended formulation can also be solved in polynomial time, and that it produces the same LP-bound. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view. It features a constant number of rows and is amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hanover-Fulda-Kassel region of the German long distance railway network are reported.

Cite as

Ralf Borndörfer and Thomas Schlechte. 05. Models for Railway Track Allocation. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 62-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2007.1170,
  author =	{Bornd\"{o}rfer, Ralf and Schlechte, Thomas},
  title =	{{05. Models for Railway Track Allocation}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{62--78},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1170},
  URN =		{urn:nbn:de:0030-drops-11701},
  doi =		{10.4230/OASIcs.ATMOS.2007.1170},
  annote =	{Keywords: Track allocation, train timetabling,integer programming, column generation}
}
Document
06. Solving a Real-World Train Unit Assignment Problem

Authors: Valentina Cacchiani, Alberto Caprara, and Paolo Toth

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
INVALID Windows-1252: We face a real-world train unit assignment problem for an operator running trains in a regional area. 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 an assignment of the train units to trips, possibly combining more than one train unit for a given trip, that fulfills the seat requests. With respect to analogous case studies previously faced in the literature, ours is characterized by the fairly large number of distinct train unit types available (in addition to the fairly large number of trips to be covered). As a result, although there is a wide margin of improvement over the solution used by the practitioners (as our results show), even only finding a solution of the same value is challenging in practice. We present a successful approach, based on an ILP formulation in which the seat requirement constraints are stated in a “strong” form, derived from the description of the convex hull of the variant of the knapsack polytope arising when the sum of the variables is restricted not to exceed two, illustrating computational results on our case study.

Cite as

Valentina Cacchiani, Alberto Caprara, and Paolo Toth. 06. Solving a Real-World Train Unit Assignment Problem. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 79-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2007.1172,
  author =	{Cacchiani, Valentina and Caprara, Alberto and Toth, Paolo},
  title =	{{06. Solving a Real-World Train Unit Assignment Problem}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{79--95},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1172},
  URN =		{urn:nbn:de:0030-drops-11726},
  doi =		{10.4230/OASIcs.ATMOS.2007.1172},
  annote =	{Keywords: }
}
Document
07. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning

Authors: Erwin Abbink, Joel Van't Wout, and Dennis Huisman

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
This paper deals with large-scale crew scheduling problems arising at the Dutch railway operator, Netherlands Railways (NS). We discuss several methods to partition large instances into several smaller ones. These smaller instances are then solved with the commercially available crew scheduling algorithm TURNI. In this paper, we compare several partitioning methods with each other. Moreover, we report some results where we applied different partitioning methods after each other. With this approach, we were able to cut crew costs with 2\% (about 6 million euro per year).

Cite as

Erwin Abbink, Joel Van't Wout, and Dennis Huisman. 07. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 96-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{abbink_et_al:OASIcs.ATMOS.2007.1168,
  author =	{Abbink, Erwin and Van't Wout, Joel and Huisman, Dennis},
  title =	{{07. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{96--106},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1168},
  URN =		{urn:nbn:de:0030-drops-11686},
  doi =		{10.4230/OASIcs.ATMOS.2007.1168},
  annote =	{Keywords: Crew scheduling, large-scale optimization, partitioning}
}
Document
08. Branching Strategies to Improve Regularity of Crew Schedules in Ex-Urban Public Transit

Authors: Ingmar Steinzen, Leena Suhl, and Natalia Kliewer

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
We discuss timetables in ex-urban bus traffic that consist of many trips serviced every day together with some exceptions that do not repeat daily. Traditional optimization methods for vehicle and crew scheduling in such cases usually produce schedules that contain irregularities which are not desirable especially from the point of view of the bus drivers. We propose a solution method which improves regularity while partially integrating the vehicle and crew scheduling problems. The approach includes two phases: first we solve the LP relaxation of a set partitioning formulation, using column generation together with Lagrangean relaxation techniques. In a second phase we generate integer solutions using a new combination of local branching and various versions of follow-on branching. Numerical tests with artificial and real instances show that regularity can be improved significantly with no or just a minor increase of costs.

Cite as

Ingmar Steinzen, Leena Suhl, and Natalia Kliewer. 08. Branching Strategies to Improve Regularity of Crew Schedules in Ex-Urban Public Transit. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 107-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{steinzen_et_al:OASIcs.ATMOS.2007.1167,
  author =	{Steinzen, Ingmar and Suhl, Leena and Kliewer, Natalia},
  title =	{{08. Branching Strategies to Improve Regularity of Crew Schedules in Ex-Urban Public Transit}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{107--123},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1167},
  URN =		{urn:nbn:de:0030-drops-11674},
  doi =		{10.4230/OASIcs.ATMOS.2007.1167},
  annote =	{Keywords: }
}
Document
09. Periodic Railway Timetabling with Event Flexibility

Authors: Gabrio Curzio Caimi, Martin Fuchsberger, Marco Laumanns, and Kaspar Schüpbach

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
This paper addresses the problem of generating conflict-free periodic train schedules for large railway networks. We follow a two level approach, where a simplified track topology is used to obtain a macro level schedule and the detailed topology is considered locally on the micro level. To increase the solution space in the interface of the two levels, we propose an extension of the well-known Periodic Event Scheduling Problem (PESP) such that it allows to generate flexible time slots for the departure and arrival times instead of exact times. This Flexible Periodic Event Scheduling Problem (FPESP) formulation considerably increases the chance to obtain feasible solutions (exact train routings) subsequently on the micro level, in particular for stations with dense peak traffic. Total trip time and the time slot sizes are used as multiple objectives and weighted and/or constrained to allocate the flexibility where it is most useful. Tests on an instance of the 2007 service intention of the Swiss Federal Railways demonstrate the advantage of the FPESP model, while it only moderate increases its solution time in most cases.

Cite as

Gabrio Curzio Caimi, Martin Fuchsberger, Marco Laumanns, and Kaspar Schüpbach. 09. Periodic Railway Timetabling with Event Flexibility. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 124-141, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{caimi_et_al:OASIcs.ATMOS.2007.1173,
  author =	{Caimi, Gabrio Curzio and Fuchsberger, Martin and Laumanns, Marco and Sch\"{u}pbach, Kaspar},
  title =	{{09. Periodic Railway Timetabling with Event Flexibility}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{124--141},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1173},
  URN =		{urn:nbn:de:0030-drops-11735},
  doi =		{10.4230/OASIcs.ATMOS.2007.1173},
  annote =	{Keywords: }
}
  • Refine by Author
  • 7 Mesa, Juan A.
  • 4 Ahuja, Ravindra K.
  • 3 Liebchen, Christian
  • 2 Caprara, Alberto
  • 2 Cicerone, Serafino
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Transportation

  • Refine by Keyword
  • 3 Operations research
  • 2 railway optimization
  • 2 scheduled transport
  • 1 Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications
  • 1 Benders decomposition
  • Show More...

  • Refine by Type
  • 23 document
  • 1 volume

  • Refine by Publication Year
  • 20 2007
  • 1 2006
  • 1 2012
  • 1 2014
  • 1 2021

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