IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v14y2014i3p629-646.html
   My bibliography  Save this article

Covering Part of a Planar Network

Author

Listed:
  • Zvi Drezner
  • George Wesolowsky

Abstract

The problem of locating facilities in a feasible area covering some parts of network links within a given radius is analyzed. The feasible area can be the interior (convex hull of the nodes) of a planar network or any union of convex polygons. Both minimization and maximization of coverage are considered. The single facility location problem is solved by the global optimization approach “Big Triangle Small Triangle.” The multiple facility maximization problem is solved by a specially designed heuristic algorithm. The idea of the heuristic algorithm may prove to work well on other planar multiple facility location problems. Computational experience with problems of up to 40,000 links demonstrate the effectiveness of the single facility and multiple facilities algorithms. The largest single facility minimal cover problem is solved in about one minute and the largest single facility maximal cover problem is solved in less than 4 minutes. Copyright Springer Science+Business Media New York 2014

Suggested Citation

  • Zvi Drezner & George Wesolowsky, 2014. "Covering Part of a Planar Network," Networks and Spatial Economics, Springer, vol. 14(3), pages 629-646, December.
    • Handle: RePEc:kap:netspa:v:14:y:2014:i:3:p:629-646
    DOI: 10.1007/s11067-014-9263-5
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s11067-014-9263-5
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11067-014-9263-5?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. Yafeng Yin, 2008. "A Scenario-based Model for Fleet Allocation of Freeway Service Patrols," Networks and Spatial Economics, Springer, vol. 8(4), pages 407-417, December.
    2. Current, John R. & Schilling, David A., 1994. "The median tour and maximal covering tour problems: Formulations and heuristics," European Journal of Operational Research, Elsevier, vol. 73(1), pages 114-126, February.
    3. Drezner, Tammy & Drezner, Zvi & Salhi, Said, 2002. "Solving the multiple competitive facilities location problem," European Journal of Operational Research, Elsevier, vol. 142(1), pages 138-151, October.
    4. 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.
    5. Michael Bell, 2006. "Mixed Route Strategies for the Risk-Averse Shipment of Hazardous Materials," Networks and Spatial Economics, Springer, vol. 6(3), pages 253-265, September.
    6. Karkazis, J. & Boffey, T. B., 1995. "Optimal location of routes for vehicles transporting hazardous materials," European Journal of Operational Research, Elsevier, vol. 86(2), pages 201-215, October.
    7. Jack Elzinga & Donald W. Hearn, 1972. "Geometrical Solutions for Some Minimax Location Problems," Transportation Science, INFORMS, vol. 6(4), pages 379-394, November.
    8. Drezner, Zvi, 1986. "The p-cover problem," European Journal of Operational Research, Elsevier, vol. 26(2), pages 312-313, August.
    9. Zvi Drezner & Atsuo Suzuki, 2004. "The Big Triangle Small Triangle Method for the Solution of Nonconvex Facility Location Problems," Operations Research, INFORMS, vol. 52(1), pages 128-135, February.
    10. Eiselt, H.A. & Marianov, Vladimir, 2009. "Gradual location set covering with service quality," Socio-Economic Planning Sciences, Elsevier, vol. 43(2), pages 121-130, June.
    11. Lili Du & Srinivas Peeta, 2014. "A Stochastic Optimization Model to Reduce Expected Post-Disaster Response Time Through Pre-Disaster Investment Decisions," Networks and Spatial Economics, Springer, vol. 14(2), pages 271-295, June.
    12. Paul Berglund & Changhyun Kwon, 2014. "Robust Facility Location Problem for Hazardous Waste Transportation," Networks and Spatial Economics, Springer, vol. 14(1), pages 91-116, March.
    13. Richard E. Wendell & Arthur P. Hurter, 1973. "Location Theory, Dominance, and Convexity," Operations Research, INFORMS, vol. 21(1), pages 314-320, February.
    14. Plastria, Frank, 1992. "GBSSS: The generalized big square small square method for planar single-facility location," European Journal of Operational Research, Elsevier, vol. 62(2), pages 163-174, October.
    15. Kevin Curtin & Karen Hayslett-McCall & Fang Qiu, 2010. "Determining Optimal Police Patrol Areas with Maximal Covering and Backup Covering Location Models," Networks and Spatial Economics, Springer, vol. 10(1), pages 125-145, March.
    16. Yafeng Yin, 2006. "Optimal Fleet Allocation of Freeway Service Patrols," Networks and Spatial Economics, Springer, vol. 6(3), pages 221-234, September.
    17. Suzuki, Atsuo & Drezner, Zvi, 2009. "The minimum equitable radius location problem with continuous demand," European Journal of Operational Research, Elsevier, vol. 195(1), pages 17-30, May.
    18. Nimrod Megiddo, 1981. "The Maximum Coverage Location Problem," Discussion Papers 490, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    19. Jiashan Wang & Yingying Kang & Changhyun Kwon & Rajan Batta, 2012. "Dual Toll Pricing for Hazardous Materials Transport with Linear Delay," Networks and Spatial Economics, Springer, vol. 12(1), pages 147-165, March.
    20. Watson-Gandy, C. D. T., 1982. "Heuristic procedures for the m-partial cover problem on a plane," European Journal of Operational Research, Elsevier, vol. 11(2), pages 149-157, October.
    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. Tammy Drezner & Zvi Drezner, 2019. "Cooperative Cover of Uniform Demand," Networks and Spatial Economics, Springer, vol. 19(3), pages 819-831, September.

    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. Berman, Oded & Drezner, Zvi & Krass, Dmitry & Wesolowsky, George O., 2009. "The variable radius covering problem," European Journal of Operational Research, Elsevier, vol. 196(2), pages 516-525, July.
    2. Tammy Drezner & Zvi Drezner, 2019. "Cooperative Cover of Uniform Demand," Networks and Spatial Economics, Springer, vol. 19(3), pages 819-831, September.
    3. Tammy Drezner & Zvi Drezner & Pawel Kalczynski, 2020. "Gradual cover competitive facility location," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 333-354, June.
    4. Tammy Drezner & Zvi Drezner & Atsuo Suzuki, 2019. "A cover based competitive facility location model with continuous demand," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 565-581, October.
    5. Tammy Drezner & Zvi Drezner & Pawel Kalczynski, 2021. "Directional approach to gradual cover: the continuous case," Computational Management Science, Springer, vol. 18(1), pages 25-47, January.
    6. T Drezner & Z Drezner & P Kalczynski, 2011. "A cover-based competitive location model," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 100-113, January.
    7. 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.
    8. T Drezner & Z Drezner, 2008. "Lost demand in a competitive environment," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(3), pages 362-371, March.
    9. J. Redondo & J. Fernández & I. García & P. Ortigosa, 2009. "A robust and efficient algorithm for planar competitive location problems," Annals of Operations Research, Springer, vol. 167(1), pages 87-105, March.
    10. 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.
    11. Rafael Suárez-Vega & Dolores Santos-Peñate & Pablo Dorta-González, 2014. "Location and quality selection for new facilities on a network market," The Annals of Regional Science, Springer;Western Regional Science Association, vol. 52(2), pages 537-560, March.
    12. Tammy Drezner & Zvi Drezner & Pawel Kalczynski, 2019. "A directional approach to gradual cover," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(1), pages 70-93, April.
    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. Drezner, Tammy & Drezner, Zvi & Hulliger, Beat, 2014. "The Quintile Share Ratio in location analysis," European Journal of Operational Research, Elsevier, vol. 238(1), pages 166-174.
    15. M. Akyüz & İ. Altınel & Temel Öncan, 2014. "Location and allocation based branch and bound algorithms for the capacitated multi-facility Weber problem," Annals of Operations Research, Springer, vol. 222(1), pages 45-71, November.
    16. 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.
    17. Tammy Drezner & Morton O’Kelly & Zvi Drezner, 2023. "Multipurpose shopping trips and location," Annals of Operations Research, Springer, vol. 321(1), pages 191-208, February.
    18. Dongyan Chen & Chan He & Senlin Wu, 2016. "Single facility collection depots location problem with random weights," Operational Research, Springer, vol. 16(2), pages 287-299, July.
    19. Rafael Blanquero & Emilio Carrizosa & Amaya Nogales-Gómez & Frank Plastria, 2014. "Single-facility huff location problems on networks," Annals of Operations Research, Springer, vol. 222(1), pages 175-195, November.
    20. Tammy Drezner & Zvi Drezner & Pawel Kalczynski, 2020. "Directional approach to gradual cover: a maximin objective," Computational Management Science, Springer, vol. 17(1), pages 121-139, January.

    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:kap:netspa:v:14:y:2014:i:3:p:629-646. 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.