The 1‐median and 1‐highway problem

The 1‐median and 1‐highway problem

0.00 Avg rating0 Votes
Article ID: iaor20128018
Volume: 225
Issue: 3
Start Page Number: 552
End Page Number: 557
Publication Date: Mar 2013
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: transportation: road
Abstract:

In this paper we study a facility location problem in the plane in which a single point (median) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time of the clients to the facility, using the L 1 or Manhattan metric. The highway is an alternative transportation system that can be used by the clients to reduce their travel time to the facility. We represent the highway by a line segment with fixed length and arbitrary orientation. This problem was introduced in [Computers & Operations Research 38(2) (2011) 525–538]. They gave both a characterization of the optimal solutions and an algorithm running in O(n 3logn) time, where n represents the number of clients. In this paper we show that the previous characterization does not work in general. Moreover, we provide a complete characterization of the solutions and give an algorithm solving the problem in O(n 3) time.

Reviews

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