KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Mon, 24 Apr 2006 19:02:34 +0200Mon, 24 Apr 2006 19:02:34 +0200Stop Location Design in Public Transportation Networks: Covering and Accessibility Objectives
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1727
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.Dwi Retnani Poetranto; Horst. W. Hamacher; Simone Horn; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1727Mon, 24 Apr 2006 19:02:34 +0200Integer programming approaches for solving the delay management problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1522
In the delay management problem we decide how to react in case of delays in public transportation. More specific, the question is if connecting vehicles should wait for delayed feeder vehicles or if it is better to depart in time. As objective we consider the convenience over all customers, expressed as the average delay of a customer when arriving at his destination.We present path-based and activity-based integer programming models for the delay management problem and show the equivalence of these formulations. Based on these, we present a simplification of the (cubic) activity-based model which results in an integer linear program. We identify cases in which this linearization is correct, namely if the so-called never-meet property holds. Fortunately, this property is often almost satisfied in our practical data. Finally, we show how to find an optimal solution in linear time in case of the never-meet property.Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1522Wed, 10 Mar 2004 13:23:47 +0100Set Covering With Almost Consecutive Ones Property
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1448
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.Nikolaus Ruf; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1448Tue, 11 Nov 2003 14:13:43 +0100Locating stops along bus or railway lines - a bicriterial problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1371
In this paper we consider the location of stops along the edges of an already existing public transportation network, as introduced in [SHLW02]. This can be the introduction of bus stops along some given bus routes, or of railway stations along the tracks in a railway network. The goal is to achieve a maximal covering of given demand points with a minimal number of stops. This bicriterial problem is in general NP-hard. We present a nite dominating set yielding an IP-formulation as a bicriterial set covering problem. We use this formulation to observe that along one single straight line the bicriterial stop location problem can be solved in polynomial time and present an e cient solution approach for this case. It can be used as the basis of an algorithm tackling real-world instances.Anita Schöbelreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1371Thu, 23 Jan 2003 10:59:07 +0100Properties of 3-dimensional line location models
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1283
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.Jack Brimberg; Henrik Juel; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1283Thu, 21 Mar 2002 00:00:00 +0100Locating New Stops in a Railway Network
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1209
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.Horst W. Hamacher; Annegret Liebers; Anita Schöbel; Dorothea Wagner; Frank Wagnerpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1209Thu, 10 May 2001 00:00:00 +0200Anchored hyperplane location problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1145
The anchored hyperplane location problem is to locate a hyperplane passing through some given points P IR^n and minimizing either the sum of weighted distances (median problem), or the maximum weighted distance (center problem) to some other points Q IR^n . If the distances are measured by a norm, it will be shown that in the median case there exists an optimal hyperplane that passes through at least n - k affinely independent points of Q, if k is the maximum number of affinely independent points of P. In the center case, there exists an optimal hyperplane which isatmaximum distance to at least n - k + 1 affinely independent points of Q. Furthermore, if the norm is a smooth norm, all optimal hyperplanes satisfy these criteria. These new results generalize known results about unrestricted hyperplane location problems.Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1145Thu, 08 Feb 2001 00:00:00 +0100Hyperplane transversals of homothetical, centrally symmetric polytopes
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1136
Let P c R^n, n >= 2, be a centrally symmetric, convex n-polytope with 2r vertices, and P be a family of m >= n + 1 homothetical copies of P. We show that a hyperplane transversal of all members of P (it it exists) can be found in O(rm) time.Horst Martini; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1136Wed, 30 Aug 2000 00:00:00 +0200Linear Facility Location in Three Dimensions - Models and Solution Methods
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1131
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.Jack Brimberg; Henrik Juel; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1131Tue, 29 Aug 2000 00:00:00 +0200Locating Least-Distance Lines in the Plane
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/503
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.Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/503Mon, 03 Apr 2000 00:00:00 +0200Solving restricted line location problems via a dual interpretation
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/506
In line location problems the objective is to find a straight line which minimizes the sum of distances, or the maximum distance, respectively to a given set of existing facilities in the plane. These problems have well solved. In this paper we deal with restricted line location problems, i.e. we have given a set in the plane where the line is not allowed to pass through. With the help of a geometric duality we solve such problems for the vertical distance and then extend these results to block norms and some of them even to arbitrary norms. For all norms we give a finite candidate set for the optimal line.Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/506Mon, 03 Apr 2000 00:00:00 +0200Median hyperplanes in normed spaces - a survey -
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/510
In this survey we deal with the location of hyperplanes in n-dimensional normed spaces, i.e., we present all known results and a unifying approach to the so-called median hyperplane problem in Minkowski spaces. We describe how to find a hyperplane H minimizing the weighted sum f(H) of distances to a given, finite set of demand points. In robust statistics and operations research such an optimal hyperplane is called a median hyperplane.After summarizing the known results for the Euclidean and rectangular situation, we show that for all distance measures d derived from norms one of the hyperplanes minimizing f(H) is the affine hull of n of the demand points and, moreover, that each median hyperplane is a halving one (in a sense defined below) with respect to the geiven point set. Also an independence of norm result for finding optimal hyperplanes with fixed slope will be given. Furthermore we discuss how these geometric criteria can be used for algorithmical approaches to median hyperplanes, with an extra discussion for the case of polyhedral norms. And finally a characterizatio of all smooth norms by a sharpened incidence criterion for median hyperplanes is mentioned.Anita Schöbel; Horst Martinipreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/510Mon, 03 Apr 2000 00:00:00 +0200A geometric approach to global optimization
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/500
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.Stefan Nickel; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/500Mon, 03 Apr 2000 00:00:00 +0200A Note on Center Problems with forbidden Polyhedra
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/522
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^2Horst W. Hamacher; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/522Mon, 03 Apr 2000 00:00:00 +0200Median hyperplanes in normed spaces
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/490
In this paper we deal with the location of hyperplanes in n-dimensional normed spaces. If d is a distance measure, our objective is to find a hyperplane H which minimizes f(H) = sum_{m=1}^{M} w_{m}d(x_m,H), where w_m ge 0 are non-negative weights, x_m in R^n, m=1, ... ,M demand points and d(x_m,H)=min_{z in H} d(x_m,z) is the distance from x_m to the hyperplane H. In robust statistics and operations research such an optimal hyperplane is called a median hyperplane. We show that for all distance measures d derived from norms, one of the hyperplanes minimizing f(H) is the affine hull of n of the demand points and, moreover, that each median hyperplane is (ina certain sense) a halving one with respect to the given point set.Anita Schöbel; H. Martinipreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/490Mon, 03 Apr 2000 00:00:00 +0200On Center Cycles in Grid Graphs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/846
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.Horst W. Hamacher; Anita Schöbelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/846Fri, 17 Sep 1999 00:00:00 +0200