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(n3) 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(n4), 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(n2logn) so that existing enumeration algorithms can be fixed without increasing their O(n3) 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(n2logn). The new algorithm also guarantees that the regions are enumerated only once.

A new algorithm for the Single Source Weber Problem with Limited Distances / G. Righini. - In: TRANSPORTATION SCIENCE. - ISSN 0041-1655. - (2021). [Epub ahead of print] [10.1287/trsc.2021.1083]

A new algorithm for the Single Source Weber Problem with Limited Distances

G. Righini
2021

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(n3) 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(n4), 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(n2logn) so that existing enumeration algorithms can be fixed without increasing their O(n3) 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(n2logn). The new algorithm also guarantees that the regions are enumerated only once.
Weber problem; depth-first-search
Settore MAT/09 - Ricerca Operativa
30-ago-2021
Article (author)
File in questo prodotto:
File Dimensione Formato  
49 - 2021 TS - SSWPLD.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 886.41 kB
Formato Adobe PDF
886.41 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/870225
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact