Abstract
This paper introduces the concept of cooperative users in facility location problems with a median or a covering objective. Cooperative users can act as intermediate facilities which are more accessible than primary facilities to excentric users. Four versions of location problems with cooperative users are modeled, for all four combinations of median and covering objectives. Several families of valid inequalities are then presented. This is followed by the development of a non-linear model to assess the fair price of cooperation. The results of computational experiments on randomly generated and benchmark instances demonstrate the positive effect of having cooperative users on the solution structure and cost, as well the impact of the valid inequalities on the LP relaxation value and on the CPU time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aardal K, Labbé M, Leung J, Queyranne M (1996) On the two-level uncapacitated facility location problem. INFORMS J Comput 8(3):289–301
Archetti C, Savelsbergh MWP, Speranza MG (2016) The vehicle routing problem with occasional drivers. Eur J Oper Res 254(2):472–480
Buldeo R, Verlinde H, Merckx J, Macharis C (2017) Crowd logistics: an opportunity for more sustainable urban freight transport? Eur Transp Res Rev 9:39
Cuda R, Guastaroba G, Speranza MG (2015) A survey on two-echelon routing problems. Comput Oper Res 55:185–199
Daskin MS, Maass KL (2015) The \(p\)-median problem. In: Laporte G, Nickel S, Saldanha da Gama F (eds) Location science. Springer, Berlin
Espejo I, Marín A, Rodríguez-Chía AM (2012) Closest assignment constraints in discrete location problems. Eur J Oper Res 219(1):49–58
Fernández E, Landete M (2015) Fixed-charge facility location problems. In: Laporte G, Nickel S, Saldanha da Gama F (eds) Location science. Springer, Berlin
Fiestras-Janeiro MG, García-Jurado I, Meca A, Mosquera MA (2015) Cooperation on capacitated inventory situations with fixed holding costs. Eur J Oper Res 241:719–726
García S, Marín A (2015) The covering location problem. In: Laporte G, Nickel S, Saldanha da Gama F (eds) Location science. Springer, Berlin
García S, Labbé M, Marín A (2011) Solving large \(p\)-median problems with a radius formulation. INFORMS J Comput 23(4):546–556
Gendron B, Semet F (2009) Formulations and relaxations for a multi-echelon capacitated location-distribution problem. Comput Oper Res 36:1335–1355
Gendron B, Khuong P-V, Semet F (2016) A Lagrangian-based branch-and-bound algorithm for the two-level uncapacitated facility location problem with single-assignment constraints. Transp Sci 50(4):1286–1299
Gendron B, Khuong P-V, Semet F (2017) Comparison of formulations for the two-level uncapacitated facility location problem with single assignment constraints. Comput Oper Res 86:86–93
Grötschel M, Lovász L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer, Berlin
Hagtvedt R, Ferguson M, Giffin P, Jones GT, Keskinocak P (2009) Cooperative strategies to reduce ambulance diversion. In: Proceedings of the 2009 Winter Simulation Conference, pp 1861–1874
Kolen A, Tamir A (1990) Covering problems. In: Mirchandani PB, Francis RL (eds) Discrete location theory. Wiley, New York
Krajewska MA, Kopfer H, Laporte G, Røpke S, Zaccour G (2008) Horizontal cooperation among freight carriers: request allocation and profit sharing. J Oper Res Soc 59:1483–1491
Marín A (2007) Lower bounds for the two-stage uncapacitated facility location problem. Eur J Oper Res 179:1126–1142
Marín A, Pelegrín B (1999) Applying Lagrangian relaxation to the resolution of two-stage location problems. Ann Oper Res 86:179–198
Mercer A, Tao X (1996) Alternative inventory and distribution policies of a food manufacturer. J Oper Res Soc 47(6):755–765
Ortiz-Astorquiza C, Contreras I, Laporte G (2018) Multi-level facility location problems. Eur J Oper Res 267:791–805
Paterson C, Kiesmüller G, Teunter R, Glazebrook K (2011) Inventory models with lateral transshipments: a review. Eur J Oper Res 210(2):125–136
Rancourt M-È, Cordeau J-F, Laporte G, Watkins B (2015) Tactical network planning for food aid distribution in Kenya. Comput Oper Res 56:68–83
Savelsbergh MWP, Van Woensel T (2016) City logistics: challenges and opportunities. Transp. Sci. 50(2):579–590
Wagner JL, Falkson LM (1975) The optimal nodal location of public facilities with price-sensitive demand. Geogr Anal 7:69–83
Walker WE, Chaiken JM, Ignall EJ (eds) (1979) Fire department deployment analysis: a public policy analysis case study. North-Holland, Amsterdam
Acknowledgements
This work was partially funded by the Canadian Natural Sciences and Engineering Research Council under grant 2015-06189 and by Spanish Ministerio de Economía y Competividad (MINECO/FEDER) project MTM-2015-68097(P). This support is gratefully acknowledged. We want to express our deep appreciation to the reviewers for their valuable comments, some of which have lead to significant improvements
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Landete, M., Laporte, G. Facility location problems with user cooperation. TOP 27, 125–145 (2019). https://doi.org/10.1007/s11750-018-00496-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-018-00496-9