The capacitated p-center problem requires one 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 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 3,038 vertices.

Mathematical Models and Search Algorithms for the Capacitated p-Center Problem / Ribeiro Kramer, Raphael; Iori, Manuel; Vidal, Thibaut. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 32:2(2020), pp. 444-460. [10.1287/ijoc.2019.0889]

Mathematical Models and Search Algorithms for the Capacitated p-Center Problem

Raphael Kramer
;
Manuel Iori;
2020

Abstract

The capacitated p-center problem requires one 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 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 3,038 vertices.
2020
10-ott-2019
32
2
444
460
Mathematical Models and Search Algorithms for the Capacitated p-Center Problem / Ribeiro Kramer, Raphael; Iori, Manuel; Vidal, Thibaut. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 32:2(2020), pp. 444-460. [10.1287/ijoc.2019.0889]
Ribeiro Kramer, Raphael; Iori, Manuel; Vidal, Thibaut
File in questo prodotto:
File Dimensione Formato  
1803.04865.pdf

Open access

Descrizione: Versione pre print
Tipologia: Versione originale dell'autore proposta per la pubblicazione
Dimensione 342.03 kB
Formato Adobe PDF
342.03 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1175077
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 8
social impact