2018/03/13 by Raphael Kramer, Manuel Iori, Kramer, Raphael +3
Business, Management and Accounting · Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Optimization and Mathematical Programming #Urban and Freight Transport Logistics #Vehicle Routing Optimization Methods #cs.DS
paper · pdf · doi:10.48550/arxiv.1803.04865
29 pages, 7 tables, 1 figure
arxiv created 2018/03/13 · openalex publication_date 2018/03/13 · arxiv updated 2018/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The capacitated p-center problem requires to select p facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility. The problem is well known in the field of facility location, because of the many applications that it can model. In this paper, we solve it by means of search algorithms that iteratively seek the optimal distance by solving tailored subproblems. We present different mathematical formulations for the subproblems and improve them by means of several valid inequalities, including an effective one based on a 0-1 disjunction and the solution of subset sum problems. We also develop an alternative search strategy that finds a balance between the traditional sequential search and binary search. This strategy limits the number of feasible subproblems to be solved and, at the same time, avoids large overestimates of the solution value, which are detrimental for the search. We evaluate the proposed techniques by means of extensive computational experiments on benchmark instances from the literature and new larger test sets. All instances from the literature with up to 402 vertices and integer distances are solved to proven optimality, including 13 open cases, and feasible solutions are found in 10 minutes for instances with up to 3038 vertices.