IOR Preprint 2/2009
Z. Drezner, S. Mihaylo, S. Nickel, H.-P. Ziegler:
Stochastic Analysis of Ordered Median Problems
Abstract: In this paper we investigate the ordered median objective when the demand points are generated in a circle. We find the mean and variance of the k th distance from the center of the circle and the correlation matrix between all pairs of ordered distances. By applying these values, we calculate the mean and variance of any ordered median objective and the correlation coefficient between two ordered median objectives. The usefulness of the results is demonstrated by calculating various probabilities and analyzing a case study.
Keywords: Facility Location; Stochastic Models; Ordered Median; Order Statistics.
IOR Preprint 1/2009
E. Fernández, J. Kalcsics, S. Nickel:
The Maximum Dispersion Territory Design Problem
Abstract: In this paper we address a new type of territory design problem, which is motivated by the recent recycling directive WEEE of the EC. In this problem, a set of basic areas should be partitioned into territories that are balanced and, in contrast to classical territory design, geographically as dispersed as possible to avoid that a company, or its logistics provider responsible for the recollection, gains a monopoly in some region. We call this the Maximum Dispersion Territory Design Problem. We derive properties of the problem and we compare different formulations that exploit them. We also study a specific relaxation of a covering-type formulation that enables us to derive tight bounds that improve the effectiveness of the formulation. Thereby, we obtain an upper bound by finding cliques of given size in an auxiliary graph. A lower bound can be derived based on the relation of the optimal solution of the relaxation to the chromatic number of a series of auxiliary graphs. Finally, we propose an exact algorithm for the Maximum Dispersion Territory Design Problem. Extensive computational experiments assess the efficiency of the proposed exact algorithm.
Keywords: Territory Design, Combinatorial Optimization, Cliques, Chromatic Number.