Abstract
In this paper the following facility location problem in a mixed planar-network space is considered: We assume that traveling along a given network is faster than traveling within the plane according to the Euclidean distance. A pair of points (A i ,A j ) is called covered if the time to access the network from A i plus the time for traveling along the network plus the time for reaching A j is lower than, or equal to, a given acceptance level related to the travel time without using the network. The objective is to find facilities (i.e. entry and exit points) on the network that maximize the number of covered pairs. We present a reformulation of the problem using convex covering sets and use this formulation to derive a finite dominating set and an algorithm for locating two facilities on a tree network. Moreover, we adapt a geometric branch and bound approach to the discrete nature of the problem and suggest a procedure for locating more than two facilities on a single line, which is evaluated numerically.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abellanas M, Hurtado F, Sacristán V, Icking C, Ma L, Klein R, Langetep E, Palop B (2003) Voronoi diagram for services neighboring a highway. Inf Process Lett 86:283–288
Abellanas M, Hurtado F, Palop B (2008) The heavy luggage metric. Int J Comput Geom Appl 18:295–306
Bae SW, Kim JH, Chwa KY (2009) Optimal construction of the city voronoi diagram. Int J Comput Geom 19:95–117
Berman O, Krass D, Drezner Z (2003) The gradual covering decay location problem on a network. Eur J Oper Res 151:474–480
Blanquero R, Carrizosa E (2009) Continuous location problems and big triangle small triangle: constructing better bounds. J Glob Optim 45:389–402
Cardinal J, Collette S, Hurtado F, Langerman S, Palop B (2008) Optimal location of transportation devices. Comput Geom 41:319–329
Carrizosa E, Rodríguez-Chía A (1997) Weber problems with alternative transportation systems. Eur J Oper Res 97:87–93
Dearing P, Francis RL, Lowe TJ (1976) Convex location problems on tree networks. Oper Res 24:628–642
Görke R, Shin CS, Wolff A (2008) Constructing the city voronoi diagram faster. Int J Comput Geom Appl 18:275–294
Hansen P, Peeters D, Richard D, Thisse JF (1985) The minisum and minimax location problems revisited. Oper Res 33:1251–1265
Horst R, Thoai N (1999) DC programming: overview. J Optim Theory Appl 103:1–43
Kirwan F (1992) Complex algebraic curves. Cambridge University Press, Cambridge
Koolen A, Tamir A (1990) Covering problems. In: Mirchandani P, Francis R (eds) Discrete location theory. Wiley-Interscience, New York
Körner MC, Schöbel A (2010) Weber problems with high–speed lines. TOP 18:223–241
Laporte G, Mesa JA, Ortega FA, Sevillano I (2005) Maximizing trip coverage in the location of a single rapid transit alignment. Ann Oper Res 136:49–63
Laporte G, Mesa JA, Perea F (2010) A game theoretic framework for the robust railway transit network design problem. Transp Res, Part B 44:447–459
Laporte G, Marín A, Mesa JA, Perea F (2011) Designing robust rapid transit networks with alternative routes. J Adv Transp 45:54–65
Márquez-Diez-Canedo J (1987) Fundamentos de Teoría de Optimización. Limusa, México
Ortúzar JD, Willumsen LG (2001) Modelling transport. Wiley, New York
Pfeiffer B, Klamroth K (2008) Unified model for weber problems with continuous and network distances. Comput Oper Res 35:312–326
Plastria F (1992) GBSSS: the generalized big square small square method for planar single-facility location. Eur J Oper Res 62:163–174
Plastria F (2002) Continuous covering location problems. In: Drezner Z, Hamacher H (eds) Facility location: applications and theory. Springer, Berlin
Preparata F, Shamos M (1985) Computational geometry, an introduction. Springer, Berlin
Schöbel A, Scholz D (2010) The big cube small cube solution method for multidimensional facility location problems. Comput Oper Res 37:115–122
Scholz D (2010) Geometric branch & bound methods in global optimization: theory and applications to facility location problems. Ph.D. thesis, Universität Göttingen. To appear at Springer
Scholz D, Schöbel A (2010) The theoretical and empirical rate of convergence for geometric branch-and-bound methods. J Glob Optim 48(3):473–495
Acknowledgements
This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority—6th FP), under contract no. FP6-021235-2 (project ARRIVAL), by Ministerio de Educación, Ciencia e Innovación (Spain)/FEDER under project MTM2009-14243 and by Junta de Andalucía (Spain)/FEDER under excellence projects P09-TEP-5022 and FQM-5849.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Körner, MC., Mesa, J.A., Perea, F. et al. A maximum trip covering location problem with an alternative mode of transportation on tree networks and segments. TOP 22, 227–253 (2014). https://doi.org/10.1007/s11750-012-0251-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-012-0251-y