Refine
Language
- English (12)
Keywords
- approximation algorithms (1)
- cycle basis (1)
- graph algorithms (1)
- metric approximation (1)
- periodic timetable (1)
- public transport (1)
- trip timetable (1)
Application Area
- B (11)
Cyclic timetabling for public transportation companies is usually modeled by the periodic
event scheduling problem. To deduce a mixed-integer programming formulation, artificial integer
variables have to be introduced. There are many ways to define these integer variables.
We show that the minimal number of integer variables required to encode an instance is
achieved by introducing an integer variable for each element of some integral cycle basis. An
integral cycle basis consists of |A|-|V|+1 oriented cycles of a directed graph D = (V;A) that
enable any oriented cycle of the directed graph to be expressed as an integer linear combination.
The solution times for the originating application vary extremely with different integral
cycle bases. However, our computational studies show that the width of integral cycle bases
is a good empirical measure for the solution time of the MIP. Clearly, integral cycle bases
permit a much wider choice than the former standard approach, in which integer variables are
associated with the co-tree arcs of some spanning tree. Hence, to formulate better solvable
integer programs, we present algorithms that construct integral cycle bases of small width.
To that end, we investigate classes of directed cycle bases that are closely related to integral
cycle bases, namely (generalized) fundamental and undirected cycle bases. This gives rise to
both, a compact classification of directed cycle bases and notable reductions of running times
for cyclic timetabling.
Periodic timetabling for railway networks is usually modeled by the Periodic Event Scheduling
Problem (PESP). This model permits to express many requirements that practitioners impose
on periodic railway timetables. We discuss a requirement practitioners are asking for, but which,
so far, has not been the topic of mathematical studies: the concept of symmetry.
Several motivations why symmetric timetables might seem promising will be given. However,
we provide examples showing that symmetry leads to suboptimality.
To integrate symmetry into the graph model of the PESP, there are many obstacles to overcome.
Nevertheless, adding symmetry requirements to mixed-integer programming formulations
explicitly, enables MIP solvers such as CPLEX
to terminate earlier with good solutions.
During the last 15 years, there have been proposed many solution methods
for the important task of constructing periodic timetables for public transportation
companies. We first point out the importance of an objective function, where we
observe that in particular a linear objective function turns out to be a good compromise
between essential practical requirements and computational tractability. Then,
we enter into a detailed empirical analysis of various Mixed Integer Programming
procedures { such using nodes variables and such using arcs variables { genetic algorithms,
simulated annealing and constraint programming. To our knowledge, this
is the first comparison of five conceptually different solution approaches.
On rather small instances, an arc-based MIP formulation behaves best, when
refined by additional valid inequalities. On bigger instances, the solutions obtained
by a genetic algorithm are competitive to the solutions CPLEX was investigating
until it reached a time or memory limit. For Deutsche Bahn AG, the genetic algorithm
was most convincing on their various data sets, and it will become the first
automated timetable optimization software in use.
In the planning process of railway companies, we propose to integrate important
decisions of network planning, line planning, and vehicle scheduling into the task of periodic
timetabling. From such an integration, we expect to achieve an additional potential for
optimization.
Models for periodic timetabling are commonly based on the Periodic Event Scheduling
Problem (PESP). We show that, for our purpose of this integration, the PESP has to be extended
by only two features, namely a linear objective function and a symmetry requirement.
These extensions of the PESP do not really impose new types of constraints, because practitioners
have already required them even when only planning timetables autonomously without
interaction with other planning steps.
Given a directed graph D = (V;A), we consider its cycle space CD, i.e. the vector
subspace of Q|A| spanned by the incidence vectors of the oriented cycles of D. An
oriented cycle of D is just any cycle of the underlying undirected graph of D along
with an orientation; its incidence vector is 0 on the arcs not included, while, for the
included arcs, it is +1 on the arcs oriented according to the orientation and -1 on
the arcs going backward. Assume a nonnegative weight wa ? R+ is associated to
each arc a of D. We can extend the weighting w to subsets F of A and to families F
of such subsets by dening w(F) := ?f?F w(f) and w(F) := ?F?F w(F). Given
the pair (D;w), we are interested in computing a minimum weight basis of CD.
This problem is strongly related to the classical problem of computing a minimum
cycle basis of an undirected graph. In 1987, Horton developed the first polynomial
time algorithm for computing a minimum cycle basis of an undirected graph. As for
directed graphs, the first algorithm for computing a minimum directed cycle basis
is due to Kavitha and Mehlhorn. Its asymptotic complexity is ~O (m4n).
In this paper, we show how the original approach of Horton can be actually pursued
also in the context of directed graphs, while retaining its simplicity. This both
allows for a practical ~O(m4n) adaptation of Horton's original algorithm requiring
only minor modifications in the actual code and for a more involved ~O(mw+1n)
solution. At the end, we discuss the applicability of this approach to more specialized
classes of directed cycle bases, namely, integral cycle bases and generalized
fundamental cycle bases.
Classes of Cycle Bases
(2005)
In the last years, new variants of the minimum cycle basis (MCB)
problem and new classes of cycle bases have been introduced, as motivated
by several applications from disparate areas of scientific and technological
inquiries. At present, the complexity status of the MCB problem has been
settled only for undirected, directed, and strictly fundamental cycle bases.
In this paper, we over an unitary classification accommodating these
3 classes and further including the following 4 relevant classes: 2-bases (or
planar bases), weakly fundamental cycle bases, totally unimodular cycle
bases, and integral cycle bases. The classification is complete in that, for
each ordered pair (A;B) of classes considered, we either prove that A ? B
holds for every graph or provide a counterexample graph for which A ? B.
The seven notions of cycle bases are distinct (either A ? B or B ? A is
exhibited for each pair (A;B)).
All counterexamples proposed have been designed to be ultimately effective
in separating the various algorithmic variants of the MCB problem
naturally associated to each one of these seven classes. We even provide
a linear time algorithm for computing a minimum 2-basis of a graph. Finally,
notice that the resolution of the complexity status of some of the
remaining three classes would have an immediate impact on practical applications,
as for instance in periodic railway timetabling, only integral
cycle bases are of direct use.
We consider the problem of satisfying the maximum number of constraints
of an instance of the Periodic Event Scheduling Problem (PESP). This is
a key issue in periodic railway timetable construction, and has many other applications,
e.g. for traffic light scheduling.
We generalize two (in-) approximability results, which are known for MAXIMUM-
K-COLORABLE-SUBGRAPH. Moreover, we present a deterministic combinatorial
polynomial time algorithm. Its output violates only very few constraints
for five real-world instances.
Tree spanner problems have important applications in network design, e.g. in the telecommunications industry. Mathematically, there have been considered quite a number of maxstretch tree spanner problems and of average stretch tree spanner problems. We propose a unified notation for 20 tree spanner problems, which we investigate for graphs with general positive weights, with metric weights, and with unit weights. This covers several prominent problems of combinatorial optimization. Having this notation at hand, we can clearly identify which problems coincide. In the case of unweighted graphs, the formally 20 problems collapse to only five different problems. Moreover, our systematic notation for tree spanner problems enables us to identify a tree spanner problem whose complexity status has not been solved so far. We are able to provide an NP-hardness proof. Furthermore, due to our new notation of tree spanner problems, we are able to detect that an inapproximability result that is due to Galbiati (2001, 2003) in fact applies to the classical max-stretch tree spanner problem. We conclude that the inapproximability factor for this problem thus is 2-ε, instead of only (1+sqrt(5))/2 ~ 1.618 according to Peleg and Reshef (1999).
Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length O(n2) for any unweighted graph, whence proving the conjecture of Deo et al. (1982).
For weighted graphs, we construct cycle bases of length O(W log(n) log(log(n))), where W denotes the sum of the weights of the edges. This improves the upper bound that follows from the result of Elkin et al. (2005) by a logarithmic factor and, for comparison from below, some natural classes of large girth graphs are known to exhibit minimum cycle bases of length Ω(W log(n)).
We achieve this bound for weighted graphs by not restricting ourselves to strictly fundamental cycle bases - as it is inherent to the approach of Elkin et al. - but rather also considering weakly fundamental cycle bases in our construction. This way we profit from some nice properties of Hierarchically Well-Separated Trees that were introduced by Bartal (1998).
In the Minimum Strictly Fundamental Cycle Basis (MSFCB) problem one is looking for a spanning tree such that the sum of the lengths of its induced fundamental circuits is minimum.
We identify square planar grid graphs as being very challenging testbeds for the MSFCB. The best lower and upper bounds for this problem are due to Alon, Karp, Peleg, and West (1995) and to Amaldi et~al. (2004).
We improve significantly their bounds, both empirically and asymptotically. Ideally, these new benchmarks will serve as a reference for the performance of any new heuristic for the MSFCB problem which will be designed only in the future.
In the past, much research had been dedicated to compute optimum railway timetables. A typical objective was the minimization of passenger waiting times. But only the planned nominal waiting times were addressed, whereas delays, as they occur in daily operation, were neglected. Rather, conceptually, delays were treated mainly in an online-context, and solved as a separate optimization problem, called delay management.
We provide the first computational study which aims at computing delay resistant periodic timetables. In particular we assess the delay resistancy of a timetable by evaluating it subject to several delay scenarios, to which optimum delay management will be applied.
We arrive at computing delay resistant timetables by selecting a new objective function which we design to be in the middle of the traditional simple timetabling objective and the sophisticated delay management objective. This is a slight extension of the concept of "Light Robustness", as it was proposed by Fischetti and Monaci (2006). Moreover, in our application we are able to provide accurate interpretations for the ingredients of Light Robustness.
We apply this new technique to real-world data of a part of the German railway network of Deutsche Bahn AG. Our computational results suggest that a significant decrease of passenger delays could be obtained at a relatively small price of robustness.
The timetable is the essence of the service offered by any provider
of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the
timetable has a major impact on both operating costs and on passenger
comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two
strategies with respect to vehicle operation costs. It turns out that
for short time horizons, periodic timetabling can be suboptimal; for
sufficiently long time horizons, however, periodic timetabling can
always be done in an optimal way'.