### Filtern

#### Schlagworte

- Grid Graphs (1)
- Minkowski space (1)
- Optimierung (1)
- Standorttheorie (1)
- Verkehsplanung (1)
- activity-based model (1)
- center and median problems (1)
- center hyperplane (1)
- centrally symmetric polytope (1)
- common transversal (1)
- consecutive ones property (1)
- delay management problem (1)
- hyperplane transversal (1)
- location theory (1)
- locational analysis (1)
- never-meet property (1)
- optimization (1)
- polyhedral norm (1)
- scaled translates (1)
- set covering (1)
- stop location (1)
- traffic planning (1)
- variable cardinality case (1)

#### Fachbereich / Organisatorische Einheit

- Fachbereich Mathematik (15)
- Fraunhofer (ITWM) (1)

We consider the problem of locating a line or a line segment in three- dimensional space, such that the sum of distances from the linear facility to a given set of points is minimized. An example is planning the drilling of a mine shaft, with access to ore deposits through horizontal tunnels connecting the deposits and the shaft. Various models of the problem are developed and analyzed, and effcient solution methods are given.

We consider the problem of locating a line with respect to some existing facilities in 3-dimensional space, such that the sum of weighted distances between the line and the facilities is minimized. Measuring distance using the l_p norm is discussed, along with the special cases of Euclidean and rectangular norms. Heuristic solution procedures for finding a local minimum are outlined.

Given a railway network together with information on the population and their use of the railway infrastructure, we are considering the e ffects of introducing new train stops in the existing railway network. One e ffect concerns the accessibility of the railway infrastructure to the population, measured in how far people live from their nearest train stop. The second effect we study is the change in travel time for the railway customers that is induced by new train stops. Based on these two models, we introduce two combinatorial optimization problems and give NP-hardness results for them. We suggest an algorithmic approach for the model based on travel time and give first experimental results.

The problem of finding an optimal location X* minimizing the maximum Euclidean distance to existing facilities is well solved by e.g. the Elzinga-Hearn algorithm. In practical situations X* will however often not be feasible. We therefore suggest in this note a polynomial algorithm which will find an optimal location X^F in a feasible subset F of the plane R^2

Finding "good" cycles in graphs is a problem of great interest in graph theory as well as in locational analysis. We show that the center and median problems are NP hard in general graphs. This result holds both for the variable cardinality case (i.e. all cycles of the graph are considered) and the fixed cardinality case (i.e. only cycles with a given cardinality p are feasible). Hence it is of interest to investigate special cases where the problem is solvable in polynomial time. In grid graphs, the variable cardinality case is, for instance, trivially solvable if the shape of the cycle can be chosen freely. If the shape is fixed to be a rectangle one can analyse rectangles in grid graphs with, in sequence, fixed dimension, fixed cardinality, and variable cardinality. In all cases a com plete characterization of the optimal cycles and closed form expressions of the optimal objective values are given, yielding polynomial time algorithms for all cases of center rectangle problems. Finally, it is shown that center cycles can be chosen as rectangles for small cardinalities such that the center cycle problem in grid graphs is in these cases completely solved.

In this paper we consider the problem of optimizing a piecewise-linear objective function over a non-convex domain. In particular we do not allow the solution to lie in the interior of a prespecified region R. We discuss the geometrical properties of this problems and present algorithms based on combinatorial arguments. In addition we show how we can construct quite complicated shaped sets R while maintaining the combinatorial properties.

Stop Location Design in Public Transportation Networks: Covering and Accessibility Objectives
(2006)

In StopLoc we consider the location of new stops along the edges of an existing public transportation network. Examples of StopLoc include the location of bus stops along some given bus routes or of railway stations along the tracks in a railway system. In order to measure the ''convenience'' of the location decision for potential customers in given demand facilities, two objectives are proposed. In the first one, we give an upper bound on reaching a closest station from any of the demand facilities and minimize the number of stations. In the second objective, we fix the number of new stations and minimize the sum of the distances between demand facilities and stations. The resulting two problems CovStopLoc and AccessStopLoc are solved by a reduction to a classical set covering and a restricted location problem, respectively. We implement the general ideas in two different environments - the plane, where demand facilities are represented by coordinates and in networks, where they are nodes of a graph.

In this paper we consider set covering problems with a coefficient matrix almost having the consecutive ones property, i.e., in many rows of the coefficient matrix, the ones appear consecutively. If this property holds for all rows it is well known that the set covering problem can be solved efficiently. For our case of almost consecutive ones we present a reformulation exploiting the consecutive ones structure to develop bounds and a branching scheme. Our approach has been tested on real-world data as well as on theoretical problem instances.

In this paper we deal with locating a line in the plane. If d is a distance measure our objective is to find a straight line l which minimizes f(l) of g(l) (see the paper for the definition of these functions). We show that for all distance measures d derived from norms, one of the lines minimizing f(l) contains at least two of the existing facilities. For the center objective we always get an optimal line which is at maximum distance from at least three of the existing facilities. If all weights are equal, there is an optimal line which is parallel to one facet of the convex hull of the existing facilities.