### Refine

#### Year of publication

#### Document Type

- ZIB-Report (5)
- Article (3)
- Book chapter (3)
- In Proceedings (3)
- Doctoral Thesis (1)

#### Language

- English (15)

#### Is part of the Bibliography

- no (15)

#### Keywords

- Steiner tree packing (2)
- Integer Programming (1)
- Steiner connectivity (1)
- Steiner tree (1)
- Ticket prices (1)
- cost allocation game (1)
- grid graphs (1)

#### Institute

The Steiner tree packing problem (STPP) in graphs is a long studied
problem in combinatorial optimization. In contrast to many other problems,
where there have been tremendous advances in practical problem
solving, STPP remains very difficult. Most heuristics schemes are ineffective
and even finding feasible solutions is already NP-hard. What makes
this problem special is that in order to reach the overall optimal solution
non-optimal solutions to the underlying NP-hard Steiner tree problems
must be used. Any non-global approach to the STPP is likely to fail.
Integer programming is currently the best approach for computing optimal
solutions. In this paper we review some “classical” STPP instances
which model the underlying real world application only in a reduced form.
Through improved modelling, including some new cutting planes, and by
emplyoing recent advances in solver technology we are for the first time
able to solve those instances in the original 3D grid graphs to optimimality.

Ticket pricing in public transport usually takes a welfare or mnemonics maximization point of view. These approaches do not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and integer programming. An application to pricing railway tickets for the intercity network of the Netherlands demonstrates that, in this sense, prices that are much fairer than standard ones can be computed in this way.

Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.

Ticket pricing in public transport usually takes a welfare maximization point of view. Such an approach, however, does not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and linear and integer programming. The ticket pricing problem is considered to be a constrained cost allocation game, which is a generalization of cost allocation games that allows to deal with constraints on output prices and on the formation of coalitions. An application to pricing railway tickets for the intercity network of the Netherlands is presented. The results demonstrate that the fairness of prices can be improved substantially in this way.
A preliminary version of this paper appeared in the Proceedings of HPSC 2009 (Borndörfer and Hoang 2012). This journal article introduces better model and algorithms.

We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions. The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs. We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs) algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs.

We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions.
The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs.
In this paper, we provide a comprehensive analysis of the problem. In particular,
we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.