IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v48y2000i3p444-460.html
   My bibliography  Save this article

Improvements and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem

Author

Listed:
  • Jack Brimberg

    (School of Business Administration, University of Prince Edward Island, Charlottetown, Canada C1A 4P3)

  • Pierre Hansen

    (GERAD and Ecole des Hautes Etudes Commerciales, 3000, chemin de la Côte-Sainte-Catherine, Montreal, Canada H3T 2A7)

  • Nenad Mladenović

    (GERAD and Ecole des Hautes Etudes Commerciales, 3000, chemin de la Côte-Sainte-Catherine, Montreal, Canada H3T 2A7)

  • Eric D. Taillard

    (IDSIA, Corso Elvezia 36, CH-6900 Lugano, Switzerland)

Abstract

The multisource Weber problem is to locate simultaneously m facilities in the Euclidean plane to minimize the total transportation cost for satisfying the demand of n fixed users, each supplied from its closest facility. Many heuristics have been proposed for this problem, as well as a few exact algorithms. Heuristics are needed to solve quickly large problems and to provide good initial solutions for exact algorithms. We compare various heuristics, i.e., alternative location-allocation (Cooper 1964), projection (Bongartz et al. 1994), Tabu search (Brimberg and Mladenović 1996a), p -Median plus Weber (Hansen et al. 1996), Genetic search and several versions of Variable Neighbourhood search. Based on empirical tests that are reported, it is found that most traditional and some recent heuristics give poor results when the number of facilities to locate is large and that Variable Neighbourhood search gives consistently best results, on average, in moderate computing time.

Suggested Citation

  • Jack Brimberg & Pierre Hansen & Nenad Mladenović & Eric D. Taillard, 2000. "Improvements and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem," Operations Research, INFORMS, vol. 48(3), pages 444-460, June.
    • Handle: RePEc:inm:oropre:v:48:y:2000:i:3:p:444-460
    DOI: 10.1287/opre.48.3.444.12431
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.48.3.444.12431
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.48.3.444.12431?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
    ---><---

    References listed on IDEAS

    as
    1. Rosing, K. E., 1992. "An optimal method for solving the (generalized) multi-Weber problem," European Journal of Operational Research, Elsevier, vol. 58(3), pages 414-426, May.
    2. Zvi Drezner, 1984. "The Planar Two-Center and Two-Median Problems," Transportation Science, INFORMS, vol. 18(4), pages 351-361, November.
    3. Bhaskaran, Sita, 1992. "Identification of transshipment center locations," European Journal of Operational Research, Elsevier, vol. 63(2), pages 141-150, December.
    4. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    5. Jack Brimberg & Robert F. Love, 1993. "Global Convergence of a Generalized Iterative Procedure for the Minisum Location Problem with lp Distances," Operations Research, INFORMS, vol. 41(6), pages 1153-1163, December.
    6. Pey-Chun Chen & Pierre Hansen & Brigitte Jaumard & Hoang Tuy, 1998. "Solution of the Multisource Weber and Conditional Weber Problems by D.-C. Programming," Operations Research, INFORMS, vol. 46(4), pages 548-562, August.
    7. Leon Cooper, 1963. "Location-Allocation Problems," Operations Research, INFORMS, vol. 11(3), pages 331-343, June.
    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. Hanjoul, Pierre & Peeters, Dominique, 1985. "A comparison of two dual-based procedures for solving the p-median problem," European Journal of Operational Research, Elsevier, vol. 20(3), pages 387-396, June.
    10. J. Ben Rosen & Guo-Liang Xue, 1991. "Computational Comparison of Two Algorithms for the Euclidean Single Facility Location Problem," INFORMS Journal on Computing, INFORMS, vol. 3(3), pages 207-212, August.
    Full references (including those not matched with items on IDEAS)

    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. Pey-Chun Chen & Pierre Hansen & Brigitte Jaumard & Hoang Tuy, 1998. "Solution of the Multisource Weber and Conditional Weber Problems by D.-C. Programming," Operations Research, INFORMS, vol. 46(4), pages 548-562, August.
    2. Zvi Drezner & Jack Brimberg & Nenad Mladenović & Said Salhi, 2016. "New local searches for solving the multi-source Weber problem," Annals of Operations Research, Springer, vol. 246(1), pages 181-203, November.
    3. 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.
    4. Zvi Drezner & Said Salhi, 2017. "Incorporating neighborhood reduction for the solution of the planar p-median problem," Annals of Operations Research, Springer, vol. 258(2), pages 639-654, November.
    5. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    6. 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.
    7. Prahalad Venkateshan & Kamlesh Mathur, 2015. "A Heuristic for the Multisource Weber Problem with Service Level Constraints," Transportation Science, INFORMS, vol. 49(3), pages 472-483, August.
    8. Venkateshan, Prahalad & Ballou, Ronald H. & Mathur, Kamlesh & Maruthasalam, Arulanantha P.P., 2017. "A Two-echelon joint continuous-discrete location model," European Journal of Operational Research, Elsevier, vol. 262(3), pages 1028-1039.
    9. Marianov, Vladimir & Serra, Daniel & ReVelle, Charles, 1999. "Location of hubs in a competitive environment," European Journal of Operational Research, Elsevier, vol. 114(2), pages 363-371, April.
    10. Pawel Kalczynski & Jack Brimberg & Zvi Drezner, 2022. "Less is more: discrete starting solutions in the planar p-median problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 34-59, April.
    11. Carreras, Miquel & Serra, Daniel, 1999. "On optimal location with threshold requirements," Socio-Economic Planning Sciences, Elsevier, vol. 33(2), pages 91-103, June.
    12. Rolland, Erik & Schilling, David A. & Current, John R., 1997. "An efficient tabu search procedure for the p-Median Problem," European Journal of Operational Research, Elsevier, vol. 96(2), pages 329-342, January.
    13. M. Hakan Akyüz & Temel Öncan & İ. Kuban Altınel, 2019. "Branch and bound algorithms for solving the multi-commodity capacitated multi-facility Weber problem," Annals of Operations Research, Springer, vol. 279(1), pages 1-42, August.
    14. Mladenovic, Nenad & Brimberg, Jack & Hansen, Pierre & Moreno-Perez, Jose A., 2007. "The p-median problem: A survey of metaheuristic approaches," European Journal of Operational Research, Elsevier, vol. 179(3), pages 927-939, June.
    15. 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.
    16. J Brimberg & P Hansen & G Laporte & N Mladenović & D Urošević, 2008. "The maximum return-on-investment plant location problem with market share," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(3), pages 399-406, March.
    17. R. Chen & Y. Handler, 1993. "The conditional p‐center problem in the plane," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(1), pages 117-127, February.
    18. 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.
    19. H K Smith & G Laporte & P R Harper, 2009. "Locational analysis: highlights of growth to maturity," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 140-148, May.
    20. Brimberg, Jack & Drezner, Zvi & Mladenović, Nenad & Salhi, Said, 2014. "A new local search for continuous location problems," European Journal of Operational Research, Elsevier, vol. 232(2), pages 256-265.

    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:inm:oropre:v:48:y:2000:i:3:p:444-460. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.