Groupe d’études et de recherche en analyse des décisions


A Degeneracy Property in Continuous Location-Allocation Problems


This paper investigates a new phenomenon of degeneracy in the continuous location-allocation problem. This phenomenon relates to the existence of solutions in which one or more facilities are out of use; that is, no demands (or customers) are allocated to these facilities. We show that a significant portion of solutions are degenerate when large numbers of new facilities are being considered. Computational results also reveal that the well-known Cooper algorithm and the more recent projection method of Bongartz et al. tend to produce degenerate local minima under these conditions, and that this tendency adversely affects the quality of the solution. A simple modification of these algorithms involving insertion of out-of-use facilities provides a significant improvement in solution quality for larger problem sizes without affecting CPU time. Different insertion strategies are investigated.

, 21 pages