Skip to main content
SpringerLink
Log in

Weber problems with high-speed lines

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Abellanas M, Hurtado F, Icking C, Klein R, Langetepe E, Ma L, Palop B, Sacristan V (2001) Proximity problems for time metrics induced by the L 1 metric and isothetic networks

  • Ahn H-K, Alt H, Asano T, Bae SW, Brass P, Cheong O, Knauer C, Na H-S, Shin C-S, Wolff A (2007) Constructing optimal highways. In: CATS’07: Proceedings of the thirteenth Australasian symposium on theory of computing, Darlinghurst, Australia. Australian Computer Society, Inc, Adelaide, pp 7–14

    Google Scholar 

  • Aichholzer O, Aurenhammer F, Palop B (2004) Quickest paths, straight skeletons, and the city Voronoi diagram. Discrete Comput Geom 31(1):17–35

    Google Scholar 

  • Cardinal J, Labbé M, Langerman S, Palop B (2005) Pricing of geometric transportation networks. In: CCCG, pp 92–96

  • Cardinal J, Collette S, Hurtado F, Langerman S, Palop B (2007) Moving walkways, escalators, and elevators. ArXiv e-prints, 705

  • Carrizosa E, Rodriguez-Chia AM (1997) Weber problems with alternative transportation systems. Eur J Oper Res 97:87–93

    Article  Google Scholar 

  • Chvátal C (1983) Linear programming. Freeman, New York

    Google Scholar 

  • Current J, Daskin M, Schilling D (2002) Discrete network location models. In: Drezner Z, Hamacher HW (eds) Facility location. Applications and theory. Springer, New York, pp 81–118

    Google Scholar 

  • Daskin M (1995) Network and discrete location. Wiley, New York

    Google Scholar 

  • Dearing PM, Hamacher HW, Klamroth K (2002) Dominating sets for rectilinear center location problems with polyhedral barriers. Nav Res Logist 49:647–665

    Article  Google Scholar 

  • Drezner Z, Klamroth K, Schöbel A, Wesolowsky GO (2002) The Weber problem. In: Drezner Z, Hamacher HW (eds) Facility location. Applications and theory. Springer, New York, pp 1–36

    Google Scholar 

  • Durier R, Michelot C (1985) Geometrical properties of the Fermat–Weber problem. Eur J Oper Res 20(3):332–343

    Article  Google Scholar 

  • Göerke R, Wolff A (2005) Constructing the city Voronoi diagram faster. In: Proceedings of the 21st European workshop on computational geometry (EWCG’05), pp 155–158

  • Gugat M, Pfeiffer B (2007) Weber problems with mixed distances and regional demand. Math Methods Oper Res 66(3):419–449

    Article  Google Scholar 

  • Hamacher HW, Klamroth K (2000) Planar location problems with barriers and block norms. Ann Oper Res 96(1–4):191–208

    Article  Google Scholar 

  • Körner M (2007) Das Weber Problem mit Block Metriken und Verkehrswegen. Master’s thesis, Georg-August Universität Göttingen (in German)

  • Minkowski H (1967) Gesammelte Abhandlungen, Band 2. Chelsea Publishing Company, New York

    Google Scholar 

  • Nickel S (1995) Discretization of planar location problems. Shaker, Aachen

    Google Scholar 

  • Ostrovsky-Berman Y (2005) Computing transportation Voronoi diagrams in optimal time. In: Proceedings of the 21st European workshop on computational geometry (EWCG’05)

  • Pfeiffer B, Klamroth K (2005) Bilinear programming formulations for Weber problems with continous and network distances. J Oper Res Soc Jpn 48(2):123–134

    Google Scholar 

  • Pfeiffer B, Klamroth K (2008) A unified model for Weber problems with continuous and network distances. Comput Oper Res 35(2):312–326

    Article  Google Scholar 

  • Plastria F (1995) Continuous location problems. In: Drezner Z (ed) Facility location: a survey of applications and methods. Springer, New York, pp 225–262, Chap 11

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Numerical and Applied Mathematics, Georg-August-University Goettingen, Göttingen, Germany

    Mark-Christoph Körner & Anita Schöbel

Authors
  1. Mark-Christoph Körner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anita Schöbel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mark-Christoph Körner.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Körner, MC., Schöbel, A. Weber problems with high-speed lines. TOP 18, 223–241 (2010). https://doi.org/10.1007/s11750-009-0100-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-009-0100-9

Keywords

Mathematics Subject Classification (2000)

Search

Navigation