Generating Appropriate Starting Configurations for Continuous Multi-Facility Location Models

Source abstract

Abstract We propose a new algorithm for constructing good starting configurations in continuous multi-facility location problems such as sum of squares clustering, $p$-center, clique partitioning, and the $p$-median problem which is selected to be tested in this paper. The p-median problem is to find locations for p facilities to serve a set of demand points. Each demand point has a given number of customers. The objective is to minimize the sum of distances to all the customers. As an example for the p-median model: suppose that a distribution company such as Amazon, Federal Express, UPS, and the postal service, consider building several warehouses in an area. Their objective is to minimize the total transportation cost. The number of facilities to be built is usually determined by the available budget. What are the best locations for the warehouses? Other applications may include, locating facilities such as collection points for returning products bought by customers, switching centers, laboratories that process blood samples from hospitals and medical centers, and base stations for electric vehicles and UAVs, which require battery-charging facilities at suitable locations. Computational experiments found that the suggested starting configurations resulted in better quality solutions. Better quality solutions lead to a significant cost savings resulting from better decisions by management on where to open new facilities. Quality of service will also be improved by decreasing average travel distance or time for all customers to their closest facility.