IDEAS home Printed from https://ideas.repec.org/a/wly/jnlaaa/v2013y2013i1n624398.html

A Heuristic Algorithm for Constrained Multi‐Source Location Problem with Closest Distance under Gauge: The Variational Inequality Approach

Author

Listed:
  • Jian-Lin Jiang
  • Saeed Assani
  • Kun Cheng
  • Xiao-Xing Zhu

Abstract

This paper considers the locations of multiple facilities in the space Rp, with the aim of minimizing the sum of weighted distances between facilities and regional customers, where the proximity between a facility and a regional customer is evaluated by the closest distance. Due to the fact that facilities are usually allowed to be sited in certain restricted areas, some locational constraints are imposed to the facilities of our problem. In addition, since the symmetry of distances is sometimes violated in practical situations, the gauge is employed in this paper instead of the frequently used norms for measuring both the symmetric and asymmetric distances. In the spirit of the Cooper algorithm (Cooper, 1964), a new location‐allocation heuristic algorithm is proposed to solve this problem. In the location phase, the single‐source subproblem with regional demands is reformulated into an equivalent linear variational inequality (LVI), and then, a projection‐contraction (PC) method is adopted to find the optimal locations of facilities, whereas in the allocation phase, the regional customers are allocated to facilities according to the nearest center reclassification (NCR). The convergence of the proposed algorithm is proved under mild assumptions. Some preliminary numerical results are reported to show the effectiveness of the new algorithm.

Suggested Citation

  • Jian-Lin Jiang & Saeed Assani & Kun Cheng & Xiao-Xing Zhu, 2013. "A Heuristic Algorithm for Constrained Multi‐Source Location Problem with Closest Distance under Gauge: The Variational Inequality Approach," Abstract and Applied Analysis, John Wiley & Sons, vol. 2013(1).
    • Handle: RePEc:wly:jnlaaa:v:2013:y:2013:i:1:n:624398
    DOI: 10.1155/2013/624398
    as

    Download full text from publisher

    File URL: https://doi.org/10.1155/2013/624398
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2013/624398?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. Z. Drezner & G. O. Weslowsky, 1980. "Optimal location of a facility relative to area demands," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 27(2), pages 199-206, June.
    2. Stefan Nickel & Justo Puerto & Antonio M. Rodriguez-Chia, 2003. "An Approach to Location Models Involving Sets as Existing Facilities," Mathematics of Operations Research, INFORMS, vol. 28(4), pages 693-715, November.
    3. Carrizosa, E. & Munoz-Marquez, M. & Puerto, J., 1998. "The Weber problem with regional demand," European Journal of Operational Research, Elsevier, vol. 104(2), pages 358-365, January.
    4. Emilio Carrizosa & Eduardo Conde & Manuel Muñoz-Márquez & Justo Puerto, 1997. "Simpson Points in Planar Problems with Locational Constraints. The Round-Norm Case," Mathematics of Operations Research, INFORMS, vol. 22(2), pages 276-290, May.
    5. Robert F. Love & James G. Morris, 1979. "Mathematical Models of Road Travel Distances," Management Science, INFORMS, vol. 25(2), pages 130-139, February.
    6. Nickel, Stefan, 1998. "Restricted center problems under polyhedral gauges," European Journal of Operational Research, Elsevier, vol. 104(2), pages 343-357, January.
    7. Emilio Carrizosa & Eduardo Conde & Manuel Muñoz-Márquez & Justo Puerto, 1997. "Simpson Points in Planar Problems with Locational Constraints. The Polyhedral-Gauge Case," Mathematics of Operations Research, INFORMS, vol. 22(2), pages 291-300, May.
    8. James E. Ward & Richard E. Wendell, 1985. "Using Block Norms for Location Modeling," Operations Research, INFORMS, vol. 33(5), pages 1074-1090, October.
    9. J. E. Ward & R. E. Wendell, 1980. "Technical Note—A New Norm for Measuring Distance Which Yields Linear Location Problems," Operations Research, INFORMS, vol. 28(3-part-ii), pages 836-844, June.
    10. Richard E. Stone, 1991. "Technical Note—Some Average Distance Results," Transportation Science, INFORMS, vol. 25(1), pages 83-90, February.
    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. Frank Plastria, 2009. "Asymmetric distances, semidirected networks and majority in Fermat–Weber problems," Annals of Operations Research, Springer, vol. 167(1), pages 121-155, March.
    2. C. Valero Franco & A. Rodríguez-Chía & I. Espejo Miranda, 2008. "The single facility location problem with average-distances," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 16(1), pages 164-194, July.
    3. 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.
    4. H Younies & G O Wesolowsky, 2007. "Planar maximal covering location problem under block norm distance measure," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(6), pages 740-750, June.
    5. Jianlin Jiang & Su Zhang & Yibing Lv & Xin Du & Ziwei Yan, 2020. "An ADMM-based location–allocation algorithm for nonconvex constrained multi-source Weber problem under gauge," Journal of Global Optimization, Springer, vol. 76(4), pages 793-818, April.
    6. Enrique R. Venta & Francis J. Nourie, 1989. "Facility location on a grid with a diagonal line," Naval Research Logistics (NRL), John Wiley & Sons, vol. 36(5), pages 709-717, October.
    7. Masashi Miyagawa, 2017. "Continuous location model of a rectangular barrier facility," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(1), pages 95-110, April.
    8. Jian-lin Jiang & Ya Xu, 2006. "Minisum location problem with farthest Euclidean distances," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 64(2), pages 285-308, October.
    9. Diaz-Banez, J.M. & Ramos, P.A. & Sabariego, P., 2007. "The maximin line problem with regional demand," European Journal of Operational Research, Elsevier, vol. 181(1), pages 20-29, August.
    10. Carrizosa, Emilio & Goerigk, Marc & Schöbel, Anita, 2017. "A biobjective approach to recoverable robustness based on location planning," European Journal of Operational Research, Elsevier, vol. 261(2), pages 421-435.
    11. Campos Rodriguez, Clara M. & Moreno Perez, Jose A., 2003. "Relaxation of the Condorcet and Simpson conditions in voting location," European Journal of Operational Research, Elsevier, vol. 145(3), pages 673-683, March.
    12. Jack Brimberg & Robert F. Love, 1991. "Estimating travel distances by the weighted lp norm," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(2), pages 241-259, April.
    13. Jianlin Jiang & Xiaoming Yuan, 2012. "A Barzilai-Borwein-based heuristic algorithm for locating multiple facilities with regional demand," Computational Optimization and Applications, Springer, vol. 51(3), pages 1275-1295, April.
    14. AltInel, I. Kuban & Durmaz, Engin & Aras, Necati & ÖzkIsacIk, Kerem Can, 2009. "A location-allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations," European Journal of Operational Research, Elsevier, vol. 198(3), pages 790-799, November.
    15. Blanco, Víctor & Gázquez, Ricardo & Leal, Marina, 2025. "Incorporation of regional preferences in facility location: Insights into efficiency and satisfaction trade-offs," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 203(C).
    16. Ndiaye, M. & Michelot, C., 1998. "Efficiency in constrained continuous location," European Journal of Operational Research, Elsevier, vol. 104(2), pages 288-298, January.
    17. Daoqin Tong & Alan T. Murray, 2009. "Maximising coverage of spatial demand for service," Papers in Regional Science, Wiley Blackwell, vol. 88(1), pages 85-97, March.
    18. Luca Quadrifoglio & Randolph W. Hall & Maged M. Dessouky, 2006. "Performance and Design of Mobility Allowance Shuttle Transit Services: Bounds on the Maximum Longitudinal Velocity," Transportation Science, INFORMS, vol. 40(3), pages 351-363, August.
    19. Behrens, Kristian, 2007. "On the location and lock-in of cities: Geography vs transportation technology," Regional Science and Urban Economics, Elsevier, vol. 37(1), pages 22-45, January.
    20. Levinson, David & El-Geneidy, Ahmed, 2009. "The minimum circuity frontier and the journey to work," Regional Science and Urban Economics, Elsevier, vol. 39(6), pages 732-738, November.

    More about this item

    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:wly:jnlaaa:v:2013:y:2013:i:1:n:624398. 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: Wiley Content Delivery (email available below). General contact details of provider: https://onlinelibrary.wiley.com/journal/4058 .

    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.