IDEAS home Printed from https://ideas.repec.org/a/spr/eurjco/v8y2020i3d10.1007_s13675-020-00131-y.html
   My bibliography  Save this article

The complete vertex p-center problem

Author

Listed:
  • F. Antonio Medrano

    (Texas A&M University–Corpus Christi)

Abstract

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.

Suggested Citation

  • F. Antonio Medrano, 2020. "The complete vertex p-center problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 327-343, October.
    • Handle: RePEc:spr:eurjco:v:8:y:2020:i:3:d:10.1007_s13675-020-00131-y
    DOI: 10.1007/s13675-020-00131-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13675-020-00131-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13675-020-00131-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    2. Zvi Drezner, 1984. "The Planar Two-Center and Two-Median Problems," Transportation Science, INFORMS, vol. 18(4), pages 351-361, November.
    3. Sune Lauth Gadegaard & Andreas Klose & Lars Relund Nielsen, 2018. "An improved cut-and-solve algorithm for the single-source capacitated facility location problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 1-27, March.
    4. Sourour Elloumi & Martine Labbé & Yves Pochet, 2004. "A New Formulation and Resolution Method for the p-Center Problem," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 84-94, February.
    5. ReVelle, Charles, 1993. "Facility siting and integer-friendly programming," European Journal of Operational Research, Elsevier, vol. 65(2), pages 147-158, March.
    6. Niblett, Matthew R. & Church, Richard L., 2015. "The disruptive anti-covering location problem," European Journal of Operational Research, Elsevier, vol. 247(3), pages 764-773.
    7. M. L. Balinski, 1965. "Integer Programming: Methods, Uses, Computations," Management Science, INFORMS, vol. 12(3), pages 253-313, November.
    8. Michael B. Teitz & Polly Bart, 1968. "Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph," Operations Research, INFORMS, vol. 16(5), pages 955-961, October.
    9. Richard L. Church & Kenneth L. Roberts, 1983. "Generalized Coverage Models And Public Facility Location," Papers in Regional Science, Wiley Blackwell, vol. 53(1), pages 117-135, January.
    10. S. L. Hakimi, 1964. "Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph," Operations Research, INFORMS, vol. 12(3), pages 450-459, June.
    11. Mark S. Daskin & Kayse Lee Maass, 2015. "The p-Median Problem," Springer Books, in: Gilbert Laporte & Stefan Nickel & Francisco Saldanha da Gama (ed.), Location Science, edition 127, chapter 0, pages 21-45, Springer.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Arie M. C. A. Koster & Clemens Thielen, 2020. "Special issue on: Computational discrete optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 201-203, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Stephanie A. Snyder & Robert G. Haight, 2016. "Application of the Maximal Covering Location Problem to Habitat Reserve Site Selection," International Regional Science Review, , vol. 39(1), pages 28-47, January.
    2. Jesus Garcia-Diaz & Jairo Sanchez-Hernandez & Ricardo Menchaca-Mendez & Rolando Menchaca-Mendez, 2017. "When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem," Journal of Heuristics, Springer, vol. 23(5), pages 349-366, October.
    3. ReVelle, C. S. & Eiselt, H. A., 2005. "Location analysis: A synthesis and survey," European Journal of Operational Research, Elsevier, vol. 165(1), pages 1-19, August.
    4. Rosing, K. E. & ReVelle, C. S., 1997. "Heuristic concentration: Two stage solution construction," European Journal of Operational Research, Elsevier, vol. 97(1), pages 75-86, February.
    5. S Salhi & A Al-Khedhairi, 2010. "Integrating heuristic information into exact methods: The case of the vertex p-centre problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1619-1631, November.
    6. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    7. Mauricio Resende & Renato Werneck, 2007. "A fast swap-based local search procedure for location problems," Annals of Operations Research, Springer, vol. 150(1), pages 205-230, March.
    8. Pierre Hansen & Jack Brimberg & Dragan Urošević & Nenad Mladenović, 2007. "Primal-Dual Variable Neighborhood Search for the Simple Plant-Location Problem," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 552-564, November.
    9. Schilling, D. A. & Rosing, K. E. & ReVelle, C. S., 2000. "Network distance characteristics that affect computational effort in p-median location problems," European Journal of Operational Research, Elsevier, vol. 127(3), pages 525-536, December.
    10. Daniel Martins & Gabriel M. Vianna & Isabel Rosseti & Simone L. Martins & Alexandre Plastino, 2018. "Making a state-of-the-art heuristic faster with data mining," Annals of Operations Research, Springer, vol. 263(1), pages 141-162, April.
    11. Blanco, Víctor & Gázquez, Ricardo & Ponce, Diego & Puerto, Justo, 2023. "A branch-and-price approach for the continuous multifacility monotone ordered median problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 105-126.
    12. Ting L. Lei & Richard L. Church, 2011. "Constructs for Multilevel Closest Assignment in Location Modeling," International Regional Science Review, , vol. 34(3), pages 339-367, July.
    13. Rosing, K. E. & ReVelle, C. S. & Rolland, E. & Schilling, D. A. & Current, J. R., 1998. "Heuristic concentration and Tabu search: A head to head comparison," European Journal of Operational Research, Elsevier, vol. 104(1), pages 93-99, January.
    14. Klose, Andreas & Drexl, Andreas, 2005. "Facility location models for distribution system design," European Journal of Operational Research, Elsevier, vol. 162(1), pages 4-29, April.
    15. Duran-Mateluna, Cristian & Ales, Zacharie & Elloumi, Sourour, 2023. "An efficient benders decomposition for the p-median problem," European Journal of Operational Research, Elsevier, vol. 308(1), pages 84-96.
    16. K.E. Rosing & C.S. ReVelle, 1997. "Heuristic Concentration and Tabu Search: A Nose to Nose Comparison," Tinbergen Institute Discussion Papers 97-058/3, Tinbergen Institute.
    17. ReVelle, C.S. & Eiselt, H.A. & Daskin, M.S., 2008. "A bibliography for some fundamental problem categories in discrete location science," European Journal of Operational Research, Elsevier, vol. 184(3), pages 817-848, February.
    18. Bell, Michael G.H. & Fonzone, Achille & Polyzoni, Chrisanthi, 2014. "Depot location in degradable transport networks," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 148-161.
    19. Gaar, Elisabeth & Sinnl, Markus, 2022. "A scaleable projection‐based branch‐and‐cut algorithm for the p‐center problem," European Journal of Operational Research, Elsevier, vol. 303(1), pages 78-98.
    20. Antiopi Panteli & Basilis Boutsinas & Ioannis Giannikos, 2021. "On solving the multiple p-median problem based on biclustering," Operational Research, Springer, vol. 21(1), pages 775-799, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:eurjco:v:8:y:2020:i:3:d:10.1007_s13675-020-00131-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.