Refine
Keywords
- integer programming (6)
- line planning (3)
- symmetry breaking (3)
- Pseudo-Boolean (2)
- branch-and-cut (2)
- computational complexity (2)
- demand function (2)
- fare planning (2)
- orbitopes (2)
- public transport (2)
The fare planning problem for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a discrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands.
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 network such that a giv en demand can be satisfied. There are two objectives. passengers want to minimize travel times, the transport company wishes to minimize operating costs. We investigate three variants of a multi-commo dity flow model for line planning that differ with respect to passenger routings. The first model allows arbitrary routings, the second only unsplittable routings, and the third only shortest path rou tings with respect to the network. We compare these models theoretically and computationally on data for the city of Potsdam.
We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the
columns. Special cases are packing and partitioning orbitopes, which
arise from restrictions to matrices with at most or exactly one 1-entry
in each row, respectively. The goal of investigating these polytopes is to
gain insight into ways of breaking certain symmetries in integer programs
by adding constraints, e.g., for a well-known formulation of the graph
coloring problem.
We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns
is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining
inequalities. For the cyclic group case, the descriptions turn out to be
totally unimodular, while for the symmetric group case both the description and the proof are more involved. Nevertheless, the associated
separation problem can be solved in linear time also in this case.
A new concept is introduced for the adaptive finite element discretization of partial differential equations that have a sparsely
representable solution. Motivated by recent work on compressed sensing, a recursive mesh refinement procedure is presented that uses linear programming to find a good approximation to the sparse solution on a given refinement level. Then only those parts of the mesh are refined that belong to nonzero expansion coefficients. Error estimates for this procedure are refined and the behavior of the procedure is demonstrated via some simple elliptic model problems.
Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment
structure.
We investigate the detection of symmetries appearing in this approach.
We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear
time if the assignment structure is known.
The line planning problem is one of the fundamental problems in strategic
planning of public and rail transport. It consists of finding lines
and corresponding frequencies in a public transport network such that
a given travel demand can be satisfied. There are (at least) two objectives.
The transport company wishes to minimize its operating cost;
the passengers request short travel times. We propose two new multicommodity
ow models for line planning. Their main features, in comparison
to existing models, are that the passenger paths can be freely
routed and that the lines are generated dynamically.
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.
In this paper, we empirically investigate the NP-hard problem of finding sparsest solutions to linear equation systems, i.e., solutions with as few nonzeros as possible. This problem has received considerable interest in the sparse approximation and signal processing literature, recently. We use a branch-and-cut approach via the maximum feasible subsystem problem to compute optimal solutions for small instances and investigate the uniqueness of the optimal solutions. We furthermore discuss five (modifications of) heuristics for this problem that appear in different parts of the literature. For small instances, the exact optimal solutions allow us to evaluate the quality of the heuristics, while for larger instances we compare their relative performance. One outcome is that the so-called basis pursuit heuristic performs worse, compared to the other methods. Among the best heuristics are a method due to Mangasarian and a bilinear approach.