The 1-Center and 1-Highway problem revisited

J. M. Díaz-Báñez (), M. Korman (), P. Pérez-Lantero () and I. Ventura ()
Additional contact information
J. M. Díaz-Báñez: Universidad de Sevilla
M. Korman: National Institute of Informatics
P. Pérez-Lantero: Universidad de Valparaíso
I. Ventura: Universidad de Sevilla

Annals of Operations Research, 2016, vol. 246, issue 1, No 10, 167-179

Abstract: Abstract In this paper we extend the Rectilinear 1-center problem as follows: given a set $$S$$ S of $$n$$ n demand points in the plane, simultaneously locate a facility point $$f$$ f and a rapid transit line (i.e. highway) $$h$$ h that together minimize the expression $$\max _{p\in S}T_{h}(p,f)$$ max p ∈ S T h ( p , f ) , where $$T_{h}(p,f)$$ T h ( p , f ) denotes the travel time between $$p$$ p and $$f$$ f . A point of $$S$$ S uses $$h$$ h to reach $$f$$ f if $$h$$ h saves time: every point $$p\in S$$ p ∈ S moves outside $$h$$ h at unit speed under the $$L_1$$ L 1 metric, and moves along $$h$$ h at a given speed $$v>1$$ v > 1 . We consider two types of highways: (1) a turnpike in which the demand points can enter/exit the highway only at the endpoints; and (2) a freeway problem in which the demand points can enter/exit the highway at any point. We solve the location problem for the turnpike case in $$O(n^2)$$ O ( n 2 ) or $$O(n\log n)$$ O ( n log n ) time, depending on whether or not the highway’s length is fixed. In the freeway case, independently of whether the highway’s length is fixed or not, the location problem can be solved in $$O(n\log n)$$ O ( n log n ) time.

Keywords: Geometric optimization; Facility location; Time metric; Rectilinear 1-center problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-015-1790-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:246:y:2016:i:1:d:10.1007_s10479-015-1790-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-1790-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().