KLUEDO RSS Feed
Neueste Dokumente / Latest documents
https://kluedo.ub.unikl.de/index/index/
Tue, 29 Aug 2000 00:00:00 +0200
Tue, 29 Aug 2000 00:00:00 +0200

Polyhedral Properties of the Uncapacitated Multiple Allocation Hub Location Problem
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/1132
We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets of this polyhedron. We develop some general rules about lifting facets from the uncapacitated facility location (UFL) for UHL and projecting facets from UHL to UFL. By applying these rules we get a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we get a new formulation of UHL whose constraints are all facet defining. We show its superior computational performance by benchmarking it on a well known data set.
Horst W. Hamacher; Martine LabbĂ©; Stefan Nickel; Tim Sonneborn
preprint
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/1132
Tue, 29 Aug 2000 00:00:00 +0200

Multicriteria network location problems with sumb objectives
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/487
In this paper network location problems with several objectives are discussed, where every single objective is a classical median objective function. We will lock at the problem of finding Pareto optimal locations and lexicographically optimal locations. It is shown that for Pareto optimal locations in undirected networks no node dominance result can be shown. Structural results as well as efficient algorithms for these multicriteria problems are developed. In the special case of a tree network a generalization of Goldman's dominance algorithm for finding Pareto locations is presented.
Horst W. Hamacher; Stefan Nickel; Martine Labbe
preprint
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/487
Mon, 03 Apr 2000 00:00:00 +0200

Classification of Location Problems
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/491
There are several good reasons to introduce classification schemes for optimization problems including, for instance, the ability for concise problem statement opposed to verbal, often ambiguous, descriptions or simple data encoding and information retrieval in bibliographical information systems or software libraries. In some branches like scheduling and queuing theory classification is therefore a widely accepted and appreciated tool. The aim of this paper is to propose a 5position classification which can be used to cover all location problems. We will provide a list of currentliy available symbols and indicate its usefulness in a  necessarily noncomprehensive  list of classical location problems. The classification scheme is in use since 1992 and has since proved to be useful in research, software development, classroom, and for overview articles.
Horst W. Hamacher; Stefan Nickel; Anja Schneider
preprint
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/491
Mon, 03 Apr 2000 00:00:00 +0200

Geometric Methods to Solve MaxOrdering Location Problems
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/502
Location problems with Q (in general conflicting) criteria are considered. After reviewing previous results of the authors dealing with lexicographic and Pareto location the main focus of the paper is on maxordering locations. In these location problems the worst of the single objectives is minimized. After discussing some general results (including reductions to single criterion problems and the relation to lexicographic and Pareto locations) three solution techniques are introduced and exemplified using one location problem class, each: The direct approach, the decision space approach and the objective space approach. In the resulting solution algorithms emphasis is on the representation of the underlying geometric idea without fully exploring the computational complexity issue. A further specialization of maxordering locations is obtained by introducing lexicographic maxordering locations, which can be found efficiently. The paper is concluded by some ideas about future research topics related to maxordering location problems.
Matthias Ehrgott; Horst W. Hamacher; Stefan Nickel
preprint
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/502
Mon, 03 Apr 2000 00:00:00 +0200

Solving nonconvex planar location problems by finite dominating sets
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/973
It is wellknown that some of the classical location problems with polyhedral gauges can be solved in polynomial time by finding a finite dominating set, i.e. a finite set of candidates guaranteed to contain at least one optimal location. In this paper it is first established that this result holds for a much larger class of problems than currently considered in the literature. The model for which this result can be proven includes, for instance, location problems with attraction and repulsion, and locationallocation problems. Next, it is shown that the approximation of general gauges by polyhedral ones in the objective function of our general model can be analyzed with regard to the subsequent error in the optimal objective value. For the approximation problem two different approaches are described, the sandwich procedure and the greedy algorithm. Both of these approaches lead  for fixed epsilon  to polynomial approximation algorithms with accuracy epsilon for solving the general model considered in this paper.
Emilio Carrizosa; Horst W. Hamacher; Rolf Klein; Stefan Nickel
preprint
https://kluedo.ub.unikl.de/frontdoor/index/index/docId/973
Fri, 18 Feb 2000 00:00:00 +0100