Refine
Year of publication
- 2005 (10) (remove)
Language
- English (10) (remove)
Application Area
- B (10) (remove)
We consider the design of a logical network topology, together with node hardware, link capacities, and a survivable routing of demands. In addition to all single node failures, the routing must also survive multiple logical link failures caused by single failures in the underlying physical network. Furthermore, the number of logical links supported by a physical link is bounded. We propose an integer linear programming model for this design problem, together with a branch-and-cut based solution approach combined with column generation. The model and algorithm are tested on three real-world test instances, and preliminary results are given.
We consider the problem of designing a network that employs a non-bifurcated shortest path routing
protocol. The network's nodes and the set of potential links are given together with a set of forecasted endto-
end traffc demands. All relevant hardware components installable at links or nodes are considered. The
goal is to simultaneously choose the network's topology, to decide which hardware components to install
on which links and nodes, and to find appropriate routing weights such that the overall network cost is
minimized.
In this paper, we present a mathematical optimization model for this problem and an algorithmic solution
approach based on a Lagrangian relaxation. Computational results achieved with this approach for several
real-world network planning problems are reported.
In diesem Artikel werden die Optimierungsmodelle und -verfahren beschrieben, die bei der Pla-
nung des Kernnetzes und der Zugangsinfrastruktur des X-WiN verwendet wurden. Bis spätestens Januar 2006 wird das
G-WiN als technische Plattform des Deutschen Forschungsnetzes durch das Nachfolgenetz X-WiN abgelöst. Bei der Pla-
nung des X-WiN müssen zahlreiche Entscheidungen getroffen werden, um ein
funktionstüchtiges, qualitativ hochwertiges und wirtschaftliches Netz zu erhalten. Die Auswahl der Kernnetzstandorte
ist dabei von besonderer Bedeutung, da
diese Entscheidung langfristige und große Auswirkungen auf den Netzbetrieb
sowie alle nachfolgenden Planungsschritte hat.
Die dabei zu berücksichtigenden technischen und organisatorischen Alternativen
und Randbedingungen sind jedoch so vielfältig und komplex, dass eine manuelle
Planung mit großen methodischen Unzulänglichkeiten behaftet wäre. Nur durch
den Einsatz mathematisch fundierter Lösungsansätze und weitgehend automatisierter
Verfahren können eine hohe Planungsqualität und -sicherheit gewährleistet und
die vorhandenen Optimierungspotentiale voll ausgeschöpft werden.
The line planning problem is one of the fundamental problems in strategic
planning of public and rail transport. It consists in finding lines
and corresponding frequencies in a transport network such that a given
travel demand can be satisfied. There are (at least) two objectives. The
transport company wishes to minimize operating costs, the passengers
want to minimize travel times. We propose a new multi-commodity
ow model for line planning. Its main features, in comparison to existing
models, are that the passenger paths can be freely routed and
that the lines are generated dynamically. We discuss properties of this
model and investigate its complexity. Results with data for the city of
Potsdam, Germany, are reported.
In this paper we introduce the fare planning problem for public
transport which consists in designing a system of fares maximizing
revenue. We propose a new simple general model for this problem.
It is based on a demand function and constraints for the different
fares. The constraints define the structure of the fare system, e.g.,
distance dependent fares or zone fares. We discuss a simple example
with a quadratic demand function and distance dependent fares. Then
we introduce a more realistic discrete choice model in which passengers
choose between different alternatives depending on the number
of trips per month. We demonstrate the examples by computational
experiments.
Can OR methods help the public transport industry to break even?
How would you build a public transport system? For example, have a look at
Berlin. The BVG, Berlin's public transport company, maintains a network
of 2,423 km, operates 197 lines with 3,286 stops, using 1,554 busses, 1,391
subway cars, and 599 trams from 12 depots, and has 13,409 employees [7].
The BVG currently transports about 800 million passengers per year and
covers about 40% of the total non-pedestrian traffic volume of the city [18].
Does Berlin have a "reasonable" public transportation network? Does
the BVG run a "good" transportation system? Is it "efficient"?
These are difficult questions. In fact, politicians, transportation managers,
customers, taxpayers, etc. frequently employ judgments such as "good"
and "efficient", but nobody can give a defiition what this exactly means.
Since almost every public transportation system in the world is in the red,
the cheapest system is no public transportation at all. On the other hand,
the most convenient system for the passenger - a stop in front of every house
with direct connections to everywhere - is much too expensive. What is the
right compromise? Operations Research has no good answer either - so far.
But OR can improve aspects of public transportation significantly, as we
want to demonstrate in the following.
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.
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.