Weber problems with high-speed lines

Abstract

The Weber problem consists of finding a facility which minimizes the sum of weighted distances from itself to a finite set of given demand points. In this paper we extend the Weber problem in the following way: We allow traveling along given linear curves (lines, line-segments, and rays) with high speed. Leaving and entering such a curve is allowed at all its points, and hence a network structure is continuously integrated in the plane. This extension gives the chance to model real-world situations like highway networks or other traffic infrastructure. The extension of the Weber problem leads to a nonconvex problem. This paper presents a geometric approach to solve the extended Weber problem and gives discretization results for polyhedral gauges.