IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v55y2021i5p1136-1150.html
   My bibliography  Save this article

A New Algorithm for the Single Source Weber Problem with Limited Distances

Author

Listed:
  • Giovanni Righini

    (Department of Computer Science, University of Milan, Milan 20122, Italy)

Abstract

The single source Weber problem with limited distances (SSWPLD) is a continuous optimization problem in location theory. The SSWPLD algorithms proposed so far are based on the enumeration of all regions of ℜ 2 defined by a given set of n intersecting circumferences. Early algorithms require O ( n 3 ) time for the enumeration, but they were recently shown to be incorrect in case of degenerate intersections, that is, when three or more circumferences pass through the same intersection point. This problem was fixed by a modified enumeration algorithm with complexity O ( n 4 ) , based on the construction of neighborhoods of degenerate intersection points. In this paper, it is shown that the complexity for correctly dealing with degenerate intersections can be reduced to O ( n 2 log n ) so that existing enumeration algorithms can be fixed without increasing their O ( n 3 ) time complexity, which is due to some preliminary computations unrelated to intersection degeneracy. Furthermore, a new algorithm for enumerating all regions to solve the SSWPLD is described: its worst-case time complexity is O ( n 2 log n ) . The new algorithm also guarantees that the regions are enumerated only once.

Suggested Citation

  • Giovanni Righini, 2021. "A New Algorithm for the Single Source Weber Problem with Limited Distances," Transportation Science, INFORMS, vol. 55(5), pages 1136-1150, September.
    • Handle: RePEc:inm:ortrsc:v:55:y:2021:i:5:p:1136-1150
    DOI: 10.1287/trsc.2021.1083
    as

    Download full text from publisher

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

    More about this item

    Keywords

    Weber problem; depth-first-search;

    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:inm:ortrsc:v:55:y:2021:i:5:p:1136-1150. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.