The discrete ordered median problem: Models and solution methods. (Q1412414)

In contrast to classical location theory ordered median problems deal with objective functions which are pointwise defined. For a new location the costs for satisfying the demand that is given at existing customer locations is determined. Moreover, if several new locations have to be considered only the costs of the closest location are taken into account. Then the components of the cost vector are sorted in non-decreasing order and the objective function value is calculated via the scalar product of the resulting ordered cost vector and a vector \(\Lambda\). Thereby it can be shown that by choosing appropriate \(\Lambda\) vectors all classical objective functions from location theory have an ordered median representation. In addition new objective functions, which have various applications but have not yet been treated in literature, can be formulated. Considering the decision-space, ordered median problems can, like classical location problems, be distinguished in continuous, network and discrete location problems. In this regard especially the discrete case, which is the topic of this monograph, has been more or less neglected so far. The book is divided into eight chapters and an appendix. In chapter one and two a motivation for ordered median problems is given and a first mathematical formulation for the Discrete Ordered Median Problem (DOMP) is derived. This formulation, being a combination of a feasibility problem of a generalized matching formulation and a classical \(N\)-Median problem, is nonlinear which is due to the sorting of the cost vector in the objective function. The third chapter is devoted to three linearizations of the nonlinear (DOMP) whereas, in addition to their validity, some structural results and several valid inequalities are proven. In order to compare these linearizations detailed statistical tests are reported which are based on an extensive number of test problems. Thereby, an analysis of variance and nonparametric statistical methods are used. In chapter four a specific Branch \& Bound Method for the (DOMP) is provided whereas the problem is divided according to the values of the binary decision variables. In this context various new lower bounds are introduced and it is shown that the proposed method performs much better in solving the (DOMP) than a standard Branch \& Bound applied to the linearizations of chapter three. Furthermore, extensive computational results are provided. In the fifth chapter two heuristic approaches are developed in order to find solutions for large, close to reality instances of the (DOMP). Moreover, the heuristics are used to determine upper bounds for the Branch \& Bound method. On the one hand an evolution program which is based on genetic algorithms is applied. Thereby, the coding of the individuals, the initial population, the evolution function, the genetic operators, the selection criterion and the determination of the parameter values is discussed. On the other hand a Variable Neighborhood Search is applied whereas a neighborhood structure and an interchange step are defined. The chapter ends with extensive computational result which show that problems with over 500 existing facilities can be solved. In chapter six two interesting special cases of the (DOMP) are detailed. The first one is the Discrete Partitioned Median Problem (DPMP) which results from the vector \(\Lambda =(a, \ldots, a,b,\ldots,b)\). Starting with \(a=0\) and \(b=1\) new formulations are derived before they are applied to the general (DPMP). Moreover, some results of chapter three are adopted to the (DPMP). The second special case is the one with \(\Lambda\) having non-decreasing entries. Thereby, several known results of the \(k\)-centra problem are transferred to the (DOMP) and again numerical tests are provided. Extensions of the (DOMP) to the capacitated case are discussed in chapter seven. In doing so two cases are distinguished whereas the first one considers single sourcing resulting in a model similar to the uncapacitated (DOMP). The second case does not consider single sourcing which results in a completely different approach. For both cases mixed-integer formulations are provided and some structural results are proven. In chapter eight some general conclusions are drawn and various research direction for the future are pointed out. The book contains more than 200 pages and 75 references. It is very well written and structured and, in particular, the extensive computational results and the numerous examples provide an excellent insight in the Discrete Ordered Median Problem.