The complete vertex p-center problem
The vertex p-center problem consists of locating p facilities among a set of M potential sites such that the maximum distance from any demand to its closest located facility is minimized. The complete vertex p-center problem solves the p-center problem for all p from 1 to the total number of sites,...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Elsevier
2020
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/d4d62cbe3b094d379bcac9cb3e7f77d5 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| id |
oai:doaj.org-article:d4d62cbe3b094d379bcac9cb3e7f77d5 |
|---|---|
| record_format |
dspace |
| spelling |
oai:doaj.org-article:d4d62cbe3b094d379bcac9cb3e7f77d52021-12-03T04:01:17ZThe complete vertex p-center problem2192-440610.1007/s13675-020-00131-yhttps://doaj.org/article/d4d62cbe3b094d379bcac9cb3e7f77d52020-10-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001337https://doaj.org/toc/2192-4406The vertex p-center problem consists of locating p facilities among a set of M potential sites such that the maximum distance from any demand to its closest located facility is minimized. The complete vertex p-center problem solves the p-center problem for all p from 1 to the total number of sites, resulting in a multi-objective trade-off curve between the number of facilities and the service distance required to achieve full coverage. This trade-off provides a reference to planners and decision makers, enabling them to easily visualize the consequences of choosing different coverage design criteria for the given spatial configuration of the problem. We present two fast algorithms for solving the complete p-center problem: one using the classical formulation but trimming variables while still maintaining optimality and the other converting the problem to a location set covering problem and solving for all distances in the distance matrix. We also discuss scenarios where it makes sense to solve the problem via brute-force enumeration. All methods result in significant speedups, with the set covering method reducing computation times by many orders of magnitude.F.Antonio MedranoElsevierarticle90C1090C1190C2790C90Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 8, Iss 3, Pp 327-343 (2020) |
| institution |
DOAJ |
| collection |
DOAJ |
| language |
EN |
| topic |
90C10 90C11 90C27 90C90 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 |
| spellingShingle |
90C10 90C11 90C27 90C90 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 F.Antonio Medrano The complete vertex p-center problem |
| description |
The vertex p-center problem consists of locating p facilities among a set of M potential sites such that the maximum distance from any demand to its closest located facility is minimized. The complete vertex p-center problem solves the p-center problem for all p from 1 to the total number of sites, resulting in a multi-objective trade-off curve between the number of facilities and the service distance required to achieve full coverage. This trade-off provides a reference to planners and decision makers, enabling them to easily visualize the consequences of choosing different coverage design criteria for the given spatial configuration of the problem. We present two fast algorithms for solving the complete p-center problem: one using the classical formulation but trimming variables while still maintaining optimality and the other converting the problem to a location set covering problem and solving for all distances in the distance matrix. We also discuss scenarios where it makes sense to solve the problem via brute-force enumeration. All methods result in significant speedups, with the set covering method reducing computation times by many orders of magnitude. |
| format |
article |
| author |
F.Antonio Medrano |
| author_facet |
F.Antonio Medrano |
| author_sort |
F.Antonio Medrano |
| title |
The complete vertex p-center problem |
| title_short |
The complete vertex p-center problem |
| title_full |
The complete vertex p-center problem |
| title_fullStr |
The complete vertex p-center problem |
| title_full_unstemmed |
The complete vertex p-center problem |
| title_sort |
complete vertex p-center problem |
| publisher |
Elsevier |
| publishDate |
2020 |
| url |
https://doaj.org/article/d4d62cbe3b094d379bcac9cb3e7f77d5 |
| work_keys_str_mv |
AT fantoniomedrano thecompletevertexpcenterproblem AT fantoniomedrano completevertexpcenterproblem |
| _version_ |
1718373957665554432 |