The 1-Center and 1-Highway problem revisited

The 1-Center and 1-Highway problem revisited

0.00 Avg rating0 Votes
Article ID: iaor20163543
Volume: 246
Issue: 1
Start Page Number: 167
End Page Number: 179
Publication Date: Nov 2016
Journal: Annals of Operations Research
Authors: , , ,
Keywords: combinatorial optimization, design, location
Abstract:

In this paper we extend the Rectilinear 1‐center problem as follows: given a set S equ1 of n equ2 demand points in the plane, simultaneously locate a facility point f equ3 and a rapid transit line (i.e. highway) h equ4 that together minimize the expression max p S T h ( p , f ) equ5 , where T h ( p , f ) equ6 denotes the travel time between p equ7 and f equ8 . A point of S equ9 uses h equ10 to reach f equ11 if h equ12 saves time: every point p S equ13 moves outside h equ14 at unit speed under the L 1 equ15 metric, and moves along h equ16 at a given speed v > 1 equ17 . 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 ) equ18 or O ( n log n ) equ19 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 ) equ20 time.

Reviews

Required fields are marked *. Your email address will not be published.