Exact Solution of Large-Scale Simple Plant Location Problems

摘要

The selection of facility sites from a set of possible locations with the intention of serving a given set of customers from the chosen locations is considered. The objective is to minimize the sum of the fixed charges for establishing the facilities and the transportation costs corresponding to the supply of the demands. This model may, e.g., be applied to locate Earth stations of a satellite communication system with minimum cost. It is shown how to modify a primal-dual version of Erlenkotter's exact algorithm to get an improved procedure. Computational experience with large-scale problems indicates that, compared with Erlenkotter's code, an implementation of the modified algorithm is faster by more than an order of magnitude.