IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v22y2016i4d10.1007_s10732-014-9277-7.html
   My bibliography  Save this article

Hybrid meta-heuristics with VNS and exact methods: application to large unconditional and conditional vertex $$p$$ p -centre problems

Author

Listed:
  • Chandra Ade Irawan

    (University of Portsmouth
    Institut Teknologi Nasional)

  • Said Salhi

    (Kent Business School, University of Kent)

  • Zvi Drezner

    (California State University-Fullerton)

Abstract

Large-scale unconditional and conditional vertex $$p$$ p -centre problems are solved using two meta-heuristics. One is based on a three-stage approach whereas the other relies on a guided multi-start principle. Both methods incorporate Variable Neighbourhood Search, exact method, and aggregation techniques. The methods are assessed on the TSP dataset which consist of up to 71,009 demand points with $$p$$ p varying from 5 to 100. To the best of our knowledge, these are the largest instances solved for unconditional and conditional vertex $$p$$ p -centre problems. The two proposed meta-heuristics yield competitive results for both classes of problems.

Suggested Citation

  • Chandra Ade Irawan & Said Salhi & Zvi Drezner, 2016. "Hybrid meta-heuristics with VNS and exact methods: application to large unconditional and conditional vertex $$p$$ p -centre problems," Journal of Heuristics, Springer, vol. 22(4), pages 507-537, August.
    • Handle: RePEc:spr:joheur:v:22:y:2016:i:4:d:10.1007_s10732-014-9277-7
    DOI: 10.1007/s10732-014-9277-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-014-9277-7
    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/s10732-014-9277-7?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Irawan, Chandra Ade & Salhi, Said & Scaparra, Maria Paola, 2014. "An adaptive multiphase approach for large unconditional and conditional p-median problems," European Journal of Operational Research, Elsevier, vol. 237(2), pages 590-605.
    2. 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.
    3. D.X. Shaw, 1999. "A unified limited column generation approach for facility location problems ontrees," Annals of Operations Research, Springer, vol. 87(0), pages 363-382, April.
    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. Lu, Chung-Cheng, 2013. "Robust weighted vertex p-center model considering uncertain data: An application to emergency management," European Journal of Operational Research, Elsevier, vol. 230(1), pages 113-121.
    6. B. C. Tansel & R. L. Francis & T. J. Lowe & M. L. Chen, 1982. "Duality and Distance Constraints for the Nonlinear p -Center Problem and Covering Problem on a Tree Network," Operations Research, INFORMS, vol. 30(4), pages 725-744, August.
    7. Oded Berman & David Simchi-Levi, 1990. "Technical Note—Conditional Location Problems on Networks," Transportation Science, INFORMS, vol. 24(1), pages 77-78, February.
    8. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    9. Zvi Drezner, 1989. "Conditional p -Center Problems," Transportation Science, INFORMS, vol. 23(1), pages 51-53, February.
    10. M D H Gamal & S Salhi, 2001. "Constructive heuristics for the uncapacitated continuous location-allocation problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(7), pages 821-829, July.
    11. R. Francis & T. Lowe & M. Rayco & A. Tamir, 2009. "Aggregation error for location models: survey and analysis," Annals of Operations Research, Springer, vol. 167(1), pages 171-208, March.
    12. Salhi, S. & Sari, M., 1997. "A multi-level composite heuristic for the multi-depot vehicle fleet mix problem," European Journal of Operational Research, Elsevier, vol. 103(1), pages 95-112, November.
    13. Caruso, C. & Colorni, A. & Aloi, L., 2003. "Dominant, an algorithm for the p-center problem," European Journal of Operational Research, Elsevier, vol. 149(1), pages 53-64, August.
    14. 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.
    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. Cihan Çetinkaya & Samer Haffar, 2018. "A Risk-Based Location-Allocation Approach for Weapon Logistics," Logistics, MDPI, vol. 2(2), pages 1-15, May.
    2. Chandra Ade Irawan & Dylan Jones, 2019. "Formulation and solution of a two-stage capacitated facility location problem with multilevel capacities," Annals of Operations Research, Springer, vol. 272(1), pages 41-67, January.
    3. Zhao, Jinqiu & Yu, Le & Xie, Binglei, 2024. "An ellipse-based locating method for flexible deployment of emergency UAVs," Socio-Economic Planning Sciences, Elsevier, vol. 96(C).
    4. Chandra Ade Irawan & Said Salhi & Kusmaningrum Soemadi, 2020. "The continuous single-source capacitated multi-facility Weber problem with setup costs: formulation and solution methods," Journal of Global Optimization, Springer, vol. 78(2), pages 271-294, 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. Marilène Cherkesly & Claudio Contardo, 2021. "The conditional p-dispersion problem," Journal of Global Optimization, Springer, vol. 81(1), pages 23-83, September.
    2. Elshaikh, Abdalla & Salhi, Said & Nagy, Gábor, 2015. "The continuous p-centre problem: An investigation into variable neighbourhood search with memory," European Journal of Operational Research, Elsevier, vol. 241(3), pages 606-621.
    3. Richard Francis & Timothy Lowe, 2014. "Comparative error bound theory for three location models: continuous demand versus discrete demand," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(1), pages 144-169, April.
    4. Callaghan, Becky & Salhi, Said & Nagy, Gábor, 2017. "Speeding up the optimal method of Drezner for the p-centre problem in the plane," European Journal of Operational Research, Elsevier, vol. 257(3), pages 722-734.
    5. Chandra Ade Irawan & Dylan Jones, 2019. "Formulation and solution of a two-stage capacitated facility location problem with multilevel capacities," Annals of Operations Research, Springer, vol. 272(1), pages 41-67, January.
    6. Puca Huachi Vaz Penna & Anand Subramanian & Luiz Satoru Ochi & Thibaut Vidal & Christian Prins, 2019. "A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet," Annals of Operations Research, Springer, vol. 273(1), pages 5-74, February.
    7. 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.
    8. Marc Demange & Virginie Gabrel & Marcel A. Haddad & Cécile Murat, 2020. "A robust p-Center problem under pressure to locate shelters in wildfire context," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 103-139, June.
    9. Irawan, Chandra Ade & Salhi, Said & Scaparra, Maria Paola, 2014. "An adaptive multiphase approach for large unconditional and conditional p-median problems," European Journal of Operational Research, Elsevier, vol. 237(2), pages 590-605.
    10. Rahimeh Neamatian Monemi & Shahin Gelareh & Anass Nagih & Dylan Jones, 2021. "Bi-objective load balancing multiple allocation hub location: a compromise programming approach," Annals of Operations Research, Springer, vol. 296(1), pages 363-406, January.
    11. Kenneth Carling & Mengjie Han & Johan Håkansson, 2012. "Does Euclidean distance work well when the p-median model is applied in rural areas?," Annals of Operations Research, Springer, vol. 201(1), pages 83-97, December.
    12. Zhizhu Lai & Qun Yue & Zheng Wang & Dongmei Ge & Yulong Chen & Zhihong Zhou, 2022. "The min-p robust optimization approach for facility location problem under uncertainty," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1134-1160, September.
    13. 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.
    14. Chandra Ade Irawan & Martino Luis & Said Salhi & Arif Imran, 2019. "The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem," Annals of Operations Research, Springer, vol. 275(2), pages 367-392, April.
    15. Enrique Domínguez & Alfredo Marín, 2020. "Discrete ordered median problem with induced order," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(3), pages 793-813, October.
    16. 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.
    17. Contreras, Ivan & Fernández, Elena & Reinelt, Gerhard, 2012. "Minimizing the maximum travel time in a combined model of facility location and network design," Omega, Elsevier, vol. 40(6), pages 847-860.
    18. Tammy Drezner & Zvi Drezner, 2016. "Sequential location of two facilities: comparing random to optimal location of the first facility," Annals of Operations Research, Springer, vol. 246(1), pages 5-18, November.
    19. R. L. Francis & T. J. Lowe & Arie Tamir, 2000. "Aggregation Error Bounds for a Class of Location Models," Operations Research, INFORMS, vol. 48(2), pages 294-307, April.
    20. Ade Irawan, Chandra & Starita, Stefano & Chan, Hing Kai & Eskandarpour, Majid & Reihaneh, Mohammad, 2023. "Routing in offshore wind farms: A multi-period location and maintenance problem with joint use of a service operation vessel and a safe transfer boat," European Journal of Operational Research, Elsevier, vol. 307(1), pages 328-350.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:joheur:v:22:y:2016:i:4:d:10.1007_s10732-014-9277-7. 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.