To access the full text documents, please follow this link: http://hdl.handle.net/2117/19982

The 1-median and 1-highway problem
Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Ventura, Inmaculada
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II
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 L1 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(n3logn) 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(n3) time.
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa
Taxicab geometry
Geometric optimization
Location
Time distance
Transportation
Optimització matemàtica
info:eu-repo/semantics/publishedVersion
Article
Elsevier
         

Show full item record

Related documents

Other documents of the same author

Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Pilz, Alexander; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Ventura, Immaculada
Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Ventura, Immaculada
Díaz-Báñez, José Miguel; López, Mario A.; Mora Giné, Mercè; Seara Ojea, Carlos; Ventura, Inmaculada
Hurtado Díaz, Fernando Alfredo; Merino, C.; Oliveros, D.; Sakai, T.; Urrutia, J.; Ventura, Inmaculada
 

Coordination

 

Supporters