IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v319y2018icp369-386.html
   My bibliography  Save this article

Approximating solutions to a bilevel capacitated facility location problem with customer's patronization toward a list of preferences

Author

Listed:
  • Casas-Ramírez, Martha-Selene
  • Camacho-Vallejo, José-Fernando
  • Martínez-Salazar, Iris-Abril

Abstract

This paper presents a bilevel capacitated facility location problem where customers are allocated to the facilities they patronize based on a predetermined list of preferences. The bilevel problem is composed of an upper level, where a company locates facilities to minimize locating and distributing costs; and a lower level, where customers aim to maximize their preferences by being allocated to the most preferred facilities to get their demands met. The complexity of the lower level problem, which is NP-hard, demands alternatives for obtaining, in general, the follower's rational reaction set. Hence, bilevel attainable solutions are defined for solving the bilevel problem in an efficient manner. Moreover, for obtaining valid bounds, a reformulation of the bilevel problem based on the lower level's linear relaxation is performed. Then, a cross entropy method is implemented for obtaining solutions in the upper level; while the lower level is solved in three different manners: by a greedy randomized adaptive procedure based on preferences, by the same procedure but based on a regret cost, and by an exact method (when possible). The conducted experimentation shows the competitiveness of the proposed algorithms, in terms of solution quality and consumed time, despite the complexity of the problem's components.

Suggested Citation

  • Casas-Ramírez, Martha-Selene & Camacho-Vallejo, José-Fernando & Martínez-Salazar, Iris-Abril, 2018. "Approximating solutions to a bilevel capacitated facility location problem with customer's patronization toward a list of preferences," Applied Mathematics and Computation, Elsevier, vol. 319(C), pages 369-386.
  • Handle: RePEc:eee:apmaco:v:319:y:2018:i:c:p:369-386
    DOI: 10.1016/j.amc.2017.03.051
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300317302357
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.amc.2017.03.051?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. Potvin, Jean-Yves & Rousseau, Jean-Marc, 1993. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 66(3), pages 331-340, May.
    2. Plastria, Frank, 2001. "Static competitive facility location: An overview of optimisation approaches," European Journal of Operational Research, Elsevier, vol. 129(3), pages 461-470, March.
    3. Pieter-Tjerk de Boer & Dirk Kroese & Shie Mannor & Reuven Rubinstein, 2005. "A Tutorial on the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 19-67, February.
    4. Belarmino Adenso-Díaz & Manuel Laguna, 2006. "Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search," Operations Research, INFORMS, vol. 54(1), pages 99-114, February.
    5. Reuven Rubinstein, 1999. "The Cross-Entropy Method for Combinatorial and Continuous Optimization," Methodology and Computing in Applied Probability, Springer, vol. 1(2), pages 127-190, September.
    6. H. A. Eiselt & Gilbert Laporte & Jacques-François Thisse, 1993. "Competitive Location Models: A Framework and Bibliography," Transportation Science, INFORMS, vol. 27(1), pages 44-54, February.
    7. Cattrysse, Dirk G. & Van Wassenhove, Luk N., 1992. "A survey of algorithms for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 60(3), pages 260-272, August.
    8. Benoît Colson & Patrice Marcotte & Gilles Savard, 2007. "An overview of bilevel optimization," Annals of Operations Research, Springer, vol. 153(1), pages 235-256, September.
    9. Kress, Dominik & Pesch, Erwin, 2012. "Sequential competitive location on networks," European Journal of Operational Research, Elsevier, vol. 217(3), pages 483-499.
    10. Hanjoul, Pierre & Peeters, Dominique, 1987. "A facility location problem with clients' preference orderings," Regional Science and Urban Economics, Elsevier, vol. 17(3), pages 451-473, August.
    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. Hinojosa, Yolanda & Marín, Alfredo & Puerto, Justo, 2023. "Dynamically second-preferred p-center problem," European Journal of Operational Research, Elsevier, vol. 307(1), pages 33-47.
    2. Lina Mallozzi & Justo Puerto & Moisés Rodríguez-Madrena, 2019. "On Location-Allocation Problems for Dimensional Facilities," Journal of Optimization Theory and Applications, Springer, vol. 182(2), pages 730-767, August.
    3. R. Paulavičius & C. S. Adjiman, 2020. "New bounding schemes and algorithmic options for the Branch-and-Sandwich algorithm," Journal of Global Optimization, Springer, vol. 77(2), pages 197-225, June.
    4. Wuyang Yu, 2019. "A leader-follower model for discrete competitive facility location problem under the partially proportional rule with a threshold," PLOS ONE, Public Library of Science, vol. 14(12), pages 1-16, December.

    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. Fernández, José & Hendrix, Eligius M.T., 2013. "Recent insights in Huff-like competitive facility location and design," European Journal of Operational Research, Elsevier, vol. 227(3), pages 581-584.
    2. Buechel, Berno & Roehl, Nils, 2015. "Robust equilibria in location games," European Journal of Operational Research, Elsevier, vol. 240(2), pages 505-517.
    3. Martha-Selene Casas-Ramírez & José-Fernando Camacho-Vallejo & Juan A. Díaz & Dolores E. Luna, 2020. "A bi-level maximal covering location problem," Operational Research, Springer, vol. 20(2), pages 827-855, June.
    4. Eligius M. T. Hendrix, 2016. "On competition in a Stackelberg location-design model with deterministic supplier choice," Annals of Operations Research, Springer, vol. 246(1), pages 19-30, November.
    5. Xiang Li & Tianyu Zhang & Liang Wang & Hongguang Ma & Xiande Zhao, 2022. "A minimax regret model for the leader–follower facility location problem," Annals of Operations Research, Springer, vol. 309(2), pages 861-882, February.
    6. Mattrand, C. & Bourinet, J.-M., 2014. "The cross-entropy method for reliability assessment of cracked structures subjected to random Markovian loads," Reliability Engineering and System Safety, Elsevier, vol. 123(C), pages 171-182.
    7. R. Y. Rubinstein, 2005. "A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation," Methodology and Computing in Applied Probability, Springer, vol. 7(1), pages 5-50, March.
    8. Gentile, José & Alves Pessoa, Artur & Poss, Michael & Costa Roboredo, Marcos, 2018. "Integer programming formulations for three sequential discrete competitive location problems with foresight," European Journal of Operational Research, Elsevier, vol. 265(3), pages 872-881.
    9. Fernandez, Pascual & Pelegrin, Blas & Garcia Perez, Maria Dolores & Peeters, Peter H., 2007. "A discrete long-term location-price problem under the assumption of discriminatory pricing: Formulations and parametric analysis," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1050-1062, June.
    10. Sáiz, M. Elena & Hendrix, Eligius M.T. & Pelegrín, Blas, 2011. "On Nash equilibria of a competitive location-design problem," European Journal of Operational Research, Elsevier, vol. 210(3), pages 588-593, May.
    11. B Pelegrín-Pelegrín & P Dorta-González & P Fernández-Hernández, 2011. "Finding location equilibria for competing firms under delivered pricing," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 729-741, April.
    12. H. Neil Geismar & Yiwei Huang & Suresh D. Pillai & Chelliah Sriskandarajah & Seokjun Youn, 2020. "Location‐Routing with Conflicting Objectives: Coordinating eBeam Phytosanitary Treatment and Distribution of Mexican Import Commodities," Production and Operations Management, Production and Operations Management Society, vol. 29(6), pages 1506-1531, June.
    13. Godinho, Pedro & Dias, Joana, 2013. "Two-player simultaneous location game: Preferential rights and overbidding," European Journal of Operational Research, Elsevier, vol. 229(3), pages 663-672.
    14. He, Zhou & Han, Guanghua & Cheng, T.C.E. & Fan, Bo & Dong, Jichang, 2019. "Evolutionary food quality and location strategies for restaurants in competitive online-to-offline food ordering and delivery markets: An agent-based approach," International Journal of Production Economics, Elsevier, vol. 215(C), pages 61-72.
    15. Blanquero, Rafael & Carrizosa, Emilio & G.-Tóth, Boglárka & Nogales-Gómez, Amaya, 2016. "p-facility Huff location problem on networks," European Journal of Operational Research, Elsevier, vol. 255(1), pages 34-42.
    16. Roboredo, Marcos Costa & Pessoa, Artur Alves, 2013. "A branch-and-cut algorithm for the discrete (r∣p)-centroid problem," European Journal of Operational Research, Elsevier, vol. 224(1), pages 101-109.
    17. Vladimir Marianov & H. A. Eiselt, 2016. "On agglomeration in competitive location models," Annals of Operations Research, Springer, vol. 246(1), pages 31-55, November.
    18. Reuven Y. Rubinstein, 2006. "How Many Needles are in a Haystack, or How to Solve #P-Complete Counting Problems Fast," Methodology and Computing in Applied Probability, Springer, vol. 8(1), pages 5-51, March.
    19. Ad Ridder & Bruno Tuffin, 2012. "Probabilistic Bounded Relative Error Property for Learning Rare Event Simulation Techniques," Tinbergen Institute Discussion Papers 12-103/III, Tinbergen Institute.
    20. Dilek, Hande & Karaer, Özgen & Nadar, Emre, 2018. "Retail location competition under carbon penalty," European Journal of Operational Research, Elsevier, vol. 269(1), pages 146-158.

    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:eee:apmaco:v:319:y:2018:i:c:p:369-386. 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: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.