IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v259y2017i1d10.1007_s10479-017-2508-1.html
   My bibliography  Save this article

Novel formulations and VNS-based heuristics for single and multiple allocation p-hub maximal covering problems

Author

Listed:
  • Olivera Janković

    (University of Kragujevac
    University of Belgrade)

  • Stefan Mišković

    (University of Belgrade)

  • Zorica Stanimirović

    (University of Belgrade)

  • Raca Todosijević

    (LAMIH UMR CNRS 8201 - Universié de Valenciennes
    Serbian Academy of Sciences and Arts)

Abstract

This paper deals with uncapacitated single and multiple allocation p-hub maximal covering problems (USApHMCP and UMApHMCP) with binary and partial covering criteria. We present new mixed-integer programming formulations of the considered problems, which are valid for both binary and partial coverage cases. The efficiency of the proposed formulations is evaluated through computational experiments on smaller-size instances, and compared with the state-of-the art models from the literature. The obtained results indicate that the new UMApHMCP formulation outperforms the existing one for both coverage criteria in the sense of solutions’ quality and running times. In order to solve instances of larger problem dimension, we develop two heuristic methods based on variable neighborhood search: general VNS (GVNS) for USApHMCP and basic VNS (BVNS) for UMApHMCP. The proposed GVNS and BVNS involve the same shaking procedure in order to hopefully escape local minima traps, while local search phases in GVNS and BVNS use different neighborhood structures in accordance with applied allocation schemes. Computational experiments conducted on smaller-size instances showed that both GVNS and BVNS almost instantly reach all known optimal solutions. In addition, the proposed GVNS and BVNS showed to be very efficient when solving large and large-scale hub instances with up to 1000 nodes, which were not previously considered as test instances for the considered problems. Both GVNS and BVNS provided best solutions on challenging USApHMCP and UMApHMCP instances for both coverage cases in short running times, which indicates their potential to be applied to similar problems.

Suggested Citation

  • Olivera Janković & Stefan Mišković & Zorica Stanimirović & Raca Todosijević, 2017. "Novel formulations and VNS-based heuristics for single and multiple allocation p-hub maximal covering problems," Annals of Operations Research, Springer, vol. 259(1), pages 191-216, December.
    • Handle: RePEc:spr:annopr:v:259:y:2017:i:1:d:10.1007_s10479-017-2508-1
    DOI: 10.1007/s10479-017-2508-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-017-2508-1
    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/s10479-017-2508-1?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. Adenso-Díaz, B. & Rodríguez, F., 1997. "A simple search heuristic for the MCLP: Application to the location of ambulance bases in a rural region," Omega, Elsevier, vol. 25(2), pages 181-187, April.
    2. Briseida Sarasola & Karl Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.
    3. 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.
    4. B Wagner, 2008. "Model formulations for hub covering problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(7), pages 932-938, July.
    5. Yaman, Hande, 2011. "Allocation strategies in hub networks," European Journal of Operational Research, Elsevier, vol. 211(3), pages 442-451, June.
    6. B Y Kara & B C Tansel, 2003. "The single-assignment hub covering problem: Models and linearizations," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(1), pages 59-64, January.
    7. Hansen, Pierre & Mladenovic, Nenad & Moreno Pérez, Jos´e A., 2008. "Variable neighborhood search," European Journal of Operational Research, Elsevier, vol. 191(3), pages 593-595, December.
    8. S Alumur & B Y Kara, 2009. "A hub covering network design problem for cargo applications in Turkey," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(10), pages 1349-1359, 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. Briseida Sarasola & Karl F. Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.
    11. Alumur, Sibel & Kara, Bahar Y., 2008. "Network hub location problems: The state of the art," European Journal of Operational Research, Elsevier, vol. 190(1), pages 1-21, October.
    12. Carrizosa, Emilio & Mladenović, Nenad & Todosijević, Raca, 2013. "Variable neighborhood search for minimum sum-of-squares clustering on networks," European Journal of Operational Research, Elsevier, vol. 230(2), pages 356-363.
    13. Berman, Oded & Krass, Dmitry & Drezner, Zvi, 2003. "The gradual covering decay location problem on a network," European Journal of Operational Research, Elsevier, vol. 151(3), pages 474-480, December.
    14. Campbell, James F., 1994. "Integer programming formulations of discrete hub location problems," European Journal of Operational Research, Elsevier, vol. 72(2), pages 387-405, January.
    15. Ernst, Andreas T. & Krishnamoorthy, Mohan, 1998. "Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem," European Journal of Operational Research, Elsevier, vol. 104(1), pages 100-112, January.
    16. Federico Della Croce & Fabio Salassa, 2014. "A variable neighborhood search based matheuristic for nurse rostering problems," Annals of Operations Research, Springer, vol. 218(1), pages 185-199, July.
    17. Ilic, Aleksandar & Urosevic, Dragan & Brimberg, Jack & Mladenovic, Nenad, 2010. "A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem," European Journal of Operational Research, Elsevier, vol. 206(2), pages 289-300, October.
    18. Hansen, Pierre & Oguz, Ceyda & Mladenovic, Nenad, 2008. "Variable neighborhood search for minimum cost berth allocation," European Journal of Operational Research, Elsevier, vol. 191(3), pages 636-649, December.
    19. Galvao, Roberto Dieguez & ReVelle, Charles, 1996. "A Lagrangean heuristic for the maximal covering location problem," European Journal of Operational Research, Elsevier, vol. 88(1), pages 114-123, January.
    20. Peker, Meltem & Kara, Bahar Y., 2015. "The P-Hub maximal covering problem and extensions for gradual decay functions," Omega, Elsevier, vol. 54(C), pages 158-172.
    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. Dimitrije D. Čvokić & Yury A. Kochetov & Aleksandr V. Plyasunov & Aleksandar Savić, 2022. "A variable neighborhood search algorithm for the $$ (r{\mid }p) $$ ( r ∣ p ) hub–centroid problem under the price war," Journal of Global Optimization, Springer, vol. 83(3), pages 405-444, July.
    2. G. Bergantiños & J. Vidal-Puga, 2020. "One-way and two-way cost allocation in hub network problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 199-234, March.
    3. A. Ghodratnama & H. R. Arbabi & A. Azaron, 2020. "A bi˗objective hub location-allocation model considering congestion," Operational Research, Springer, vol. 20(4), pages 2427-2466, December.
    4. Madani, Seyed Reza & Shahandeh Nookabadi, Ali & Hejazi, Seyed Reza, 2018. "A bi-objective, reliable single allocation p-hub maximal covering location problem: Mathematical formulation and solution approach," Journal of Air Transport Management, Elsevier, vol. 68(C), pages 118-136.
    5. Li, Yanfeng & Liu, Yang, 2021. "The static bike rebalancing problem with optimal user incentives," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 146(C).
    6. Lazar Mrkela & Zorica Stanimirović, 2022. "A variable neighborhood search for the budget-constrained maximal covering location problem with customer preference ordering," Operational Research, Springer, vol. 22(5), pages 5913-5951, November.

    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. Alumur, Sibel A. & Yaman, Hande & Kara, Bahar Y., 2012. "Hierarchical multimodal hub location problem with time-definite deliveries," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(6), pages 1107-1120.
    2. Ghaffarinasab, Nader & Motallebzadeh, Alireza, 2018. "Hub interdiction problem variants: Models and metaheuristic solution algorithms," European Journal of Operational Research, Elsevier, vol. 267(2), pages 496-512.
    3. Peker, Meltem & Kara, Bahar Y., 2015. "The P-Hub maximal covering problem and extensions for gradual decay functions," Omega, Elsevier, vol. 54(C), pages 158-172.
    4. S Alumur & B Y Kara, 2009. "A hub covering network design problem for cargo applications in Turkey," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(10), pages 1349-1359, October.
    5. Alumur, Sibel A. & Nickel, Stefan & Saldanha-da-Gama, Francisco, 2012. "Hub location under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 46(4), pages 529-543.
    6. Soylu, Banu & Katip, Hatice, 2019. "A multiobjective hub-airport location problem for an airline network design," European Journal of Operational Research, Elsevier, vol. 277(2), pages 412-425.
    7. Alumur, Sibel A. & Campbell, James F. & Contreras, Ivan & Kara, Bahar Y. & Marianov, Vladimir & O’Kelly, Morton E., 2021. "Perspectives on modeling hub location problems," European Journal of Operational Research, Elsevier, vol. 291(1), pages 1-17.
    8. Meuffels, W.J.M., 2015. "The design of road and air networks for express service providers," Other publications TiSEM d3266cb8-bc55-41be-adc7-4, Tilburg University, School of Economics and Management.
    9. Hande Yaman & Oya Ekin Karasan & Bahar Y. Kara, 2012. "Release Time Scheduling and Hub Location for Next-Day Delivery," Operations Research, INFORMS, vol. 60(4), pages 906-917, August.
    10. James F. Campbell & Morton E. O'Kelly, 2012. "Twenty-Five Years of Hub Location Research," Transportation Science, INFORMS, vol. 46(2), pages 153-169, May.
    11. Taherkhani, Gita & Alumur, Sibel A., 2019. "Profit maximizing hub location problems," Omega, Elsevier, vol. 86(C), pages 1-15.
    12. Alumur, Sibel A. & Kara, Bahar Y. & Karasan, Oya E., 2009. "The design of single allocation incomplete hub networks," Transportation Research Part B: Methodological, Elsevier, vol. 43(10), pages 936-951, December.
    13. Silva, Marcos Roberto & Cunha, Claudio B., 2017. "A tabu search heuristic for the uncapacitated single allocation p-hub maximal covering problem," European Journal of Operational Research, Elsevier, vol. 262(3), pages 954-965.
    14. Nader Azizi & Navneet Vidyarthi & Satyaveer S. Chauhan, 2018. "Modelling and analysis of hub-and-spoke networks under stochastic demand and congestion," Annals of Operations Research, Springer, vol. 264(1), pages 1-40, May.
    15. Mahmutogullari, Ali Irfan & Kara, Bahar Y., 2016. "Hub location under competition," European Journal of Operational Research, Elsevier, vol. 250(1), pages 214-225.
    16. F. Parvaresh & S. Hashemi Golpayegany & S. Moattar Husseini & B. Karimi, 2013. "Solving the p-hub Median Problem Under Intentional Disruptions Using Simulated Annealing," Networks and Spatial Economics, Springer, vol. 13(4), pages 445-470, December.
    17. Mohammadreza Hamidi & Mohammadreza Gholamian & Kamran Shahanaghi, 2014. "Developing prevention reliability in hub location models," Journal of Risk and Reliability, , vol. 228(4), pages 337-346, August.
    18. Madani, Seyed Reza & Shahandeh Nookabadi, Ali & Hejazi, Seyed Reza, 2018. "A bi-objective, reliable single allocation p-hub maximal covering location problem: Mathematical formulation and solution approach," Journal of Air Transport Management, Elsevier, vol. 68(C), pages 118-136.
    19. Rath, Srushti & Chow, Joseph Y.J., 2022. "Air taxi skyport location problem with single-allocation choice-constrained elastic demand for airport access," Journal of Air Transport Management, Elsevier, vol. 105(C).
    20. Liting Chen & Sebastian Wandelt & Weibin Dai & Xiaoqian Sun, 2022. "Scalable Vertiport Hub Location Selection for Air Taxi Operations in a Metropolitan Region," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 834-856, 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:annopr:v:259:y:2017:i:1:d:10.1007_s10479-017-2508-1. 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.