IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v238y2016i1d10.1007_s10479-015-2093-0.html
   My bibliography  Save this article

Geometric partitioning and robust ad-hoc network design

Author

Listed:
  • John Gunnar Carlsson

    (University of Southern California)

  • Mehdi Behroozi

    (University of Southern California
    University of Minnesota)

  • Xiang Li

    (University of Minnesota)

Abstract

We present fast approximation algorithms for the problem of dividing a given convex geographic region into smaller sub-regions so as to distribute the workloads of a set of vehicles. Our objective is to partition the region in such a fashion as to ensure that vehicles are capable of communicating with one another under limited communication radii. We consider variations of this problem in which sub-regions are constrained to have equal area or be convex, and as a side consequence, our approach yields a factor 1.99 approximation algorithm for the continuous k-centers problem on a convex polygon.

Suggested Citation

  • John Gunnar Carlsson & Mehdi Behroozi & Xiang Li, 2016. "Geometric partitioning and robust ad-hoc network design," Annals of Operations Research, Springer, vol. 238(1), pages 41-68, March.
    • Handle: RePEc:spr:annopr:v:238:y:2016:i:1:d:10.1007_s10479-015-2093-0
    DOI: 10.1007/s10479-015-2093-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-015-2093-0
    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-015-2093-0?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. Haugland, Dag & Ho, Sin C. & Laporte, Gilbert, 2007. "Designing delivery districts for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 180(3), pages 997-1010, August.
    2. J. Brimberg & S. Salhi, 2005. "A Continuous Location-Allocation Problem with Zone-Dependent Fixed Cost," Annals of Operations Research, Springer, vol. 136(1), pages 99-115, April.
    3. Oded Berman & Zvi Drezner & Arie Tamir & George Wesolowsky, 2009. "Optimal location with equitable loads," Annals of Operations Research, Springer, vol. 167(1), pages 307-325, March.
    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. John Carlsson & Mehdi Behroozi & Xiang Li, 2016. "Geometric partitioning and robust ad-hoc network design," Annals of Operations Research, Springer, vol. 238(1), pages 41-68, March.
    2. Faiz, Tasnim Ibn & Noor-E-Alam, Md, 2019. "Data center supply chain configuration design: A two-stage decision approach," Socio-Economic Planning Sciences, Elsevier, vol. 66(C), pages 119-135.
    3. Liu, Yanchao, 2023. "An elliptical cover problem in drone delivery network design and its solution algorithms," European Journal of Operational Research, Elsevier, vol. 304(3), pages 912-925.
    4. John Gunnar Carlsson, 2012. "Dividing a Territory Among Several Vehicles," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 565-577, November.
    5. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    6. repec:dar:wpaper:62383 is not listed on IDEAS
    7. Xin Tang & Ameur Soukhal & Vincent T’kindt, 2014. "Preprocessing for a map sectorization problem by means of mathematical programming," Annals of Operations Research, Springer, vol. 222(1), pages 551-569, November.
    8. Steiner, Maria Teresinha Arns & Datta, Dilip & Steiner Neto, Pedro José & Scarpin, Cassius Tadeu & Rui Figueira, José, 2015. "Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil," Omega, Elsevier, vol. 52(C), pages 53-64.
    9. Jabali, Ola & Gendreau, Michel & Laporte, Gilbert, 2012. "A continuous approximation model for the fleet composition problem," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1591-1606.
    10. Kalczynski, Pawel & Drezner, Zvi, 2022. "The Obnoxious Facilities Planar p-Median Problem with Variable Sizes," Omega, Elsevier, vol. 111(C).
    11. Rongbing Huang, 2016. "A short note on locating facilities on a path to minimize load range equity measure," Annals of Operations Research, Springer, vol. 246(1), pages 363-369, November.
    12. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    13. Haase, Knut & Hoppe, Mirko, 2008. "Standortplanung unter Wettbewerb - Teil 1: Grundlagen," Discussion Papers 2/2008, Technische Universität Dresden, "Friedrich List" Faculty of Transport and Traffic Sciences, Institute of Transport and Economics.
    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. Saïd Salhi & Gábor Nagy, 2009. "Local improvement in planar facility location using vehicle routing," Annals of Operations Research, Springer, vol. 167(1), pages 287-296, March.
    16. Zhen, Lu & Gao, Jiajing & Tan, Zheyi & Laporte, Gilbert & Baldacci, Roberto, 2023. "Territorial design for customers with demand frequency," European Journal of Operational Research, Elsevier, vol. 309(1), pages 82-101.
    17. Dimitris Fotakis & Epameinondas Sidiropoulos, 2014. "Combined land-use and water allocation planning," Annals of Operations Research, Springer, vol. 219(1), pages 169-185, August.
    18. Michael Schneider & Andreas Stenger & Fabian Schwahn & Daniele Vigo, 2015. "Territory-Based Vehicle Routing in the Presence of Time-Window Constraints," Transportation Science, INFORMS, vol. 49(4), pages 732-751, November.
    19. Ramamoorthy, Prasanna & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2016. "Hub Interdiction & Hub Protection problems: Model formulations & Exact Solution methods. (Revised)," IIMA Working Papers WP2016-10-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    20. Shahede Omidi & Jafar Fathali & Morteza Nazari, 2020. "Inverse and reverse balanced facility location problems with variable edge lengths on trees," OPSEARCH, Springer;Operational Research Society of India, vol. 57(2), pages 261-273, June.
    21. Lin, Yun Hui & Tian, Qingyun, 2023. "Facility location and pricing problem: Discretized mill price and exact algorithms," European Journal of Operational Research, Elsevier, vol. 308(2), pages 568-580.

    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:238:y:2016:i:1:d:10.1007_s10479-015-2093-0. 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.