{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T13:26:37Z","timestamp":1775741197681,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T00:00:00Z","timestamp":1772409600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T00:00:00Z","timestamp":1772409600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M16PAA"],"award-info":[{"award-number":["05M16PAA"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001663","name":"Volkswagen Foundation","doi-asserted-by":"publisher","award":["Freigeist-Fellowship"],"award-info":[{"award-number":["Freigeist-Fellowship"]}],"id":[{"id":"10.13039\/501100001663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Research Training Group 2236 UnRAVeL"],"award-info":[{"award-number":["Research Training Group 2236 UnRAVeL"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Single-source capacitated facility location problems are well studied in the operations research literature, yet classic problems often lack practicability by disregarding the customers\u2019 perspective: An authority that assigns customers to open facilities deprives customers from choosing facilities according to their individual preferences. In reality, this can render solutions infeasible, as customers may deviate to their most preferred open facility, thereby breaking capacities of facilities serving more customers than originally planned.\n                    <jats:italic>Preference constraints<\/jats:italic>\n                    aim to prevent this by ensuring that each customer is served at their most preferred open facility. The corresponding problem is called\n                    <jats:italic>single-source capacitated facility location problem with customer preferences<\/jats:italic>\n                    (\n                    <jats:italic>CFLP-CP<\/jats:italic>\n                    ) and is known to be strongly NP-hard. In this paper, we provide a deeper understanding of the transition from polynomially solvable cases to strongly NP-hard cases of the CFLP-CP. In particular, we show that the effect of preference constraints on the theoretical complexity can go both ways: Some problems become harder, while others become easier. This is because preference constraints simplify the assignment of customers to facilities, while simultaneously increasing the complexity of locating facilities. We show that the type of customer preferences, e.g., strict preferences or geographically closest assignments, has a vital impact on the complexity. Notably, strict preferences, i.e., customers cannot be indifferent, allow to compute feasible solutions of the CFLP-CP in polynomial time.\n                  <\/jats:p>","DOI":"10.1007\/s10479-026-07110-3","type":"journal-article","created":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T12:55:19Z","timestamp":1772456119000},"page":"2457-2482","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Insights into the computational complexity of the single-source capacitated facility location problem with customer preferences"],"prefix":"10.1007","volume":"359","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3394-2788","authenticated-orcid":false,"given":"Christina","family":"B\u00fcsing","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9291-0762","authenticated-orcid":false,"given":"Timo","family":"Gersing","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8813-9952","authenticated-orcid":false,"given":"Sophia","family":"Wrede","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,2]]},"reference":[{"key":"7110_CR1","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1287\/moor.20.3.562.","volume":"20","author":"K Aardal","year":"1995","unstructured":"Aardal, K., Pochet, Y., & Wolsey, L. (1995). Capacitated facility location: Valid inequalities and facets. Mathematics of Operations Research, 20, 562\u201382. https:\/\/doi.org\/10.1287\/moor.20.3.562.","journal-title":"Mathematics of Operations Research"},{"key":"7110_CR2","doi-asserted-by":"publisher","first-page":"2314","DOI":"10.1016\/j.egyr.2022.01.180","volume":"8","author":"F Ahmad","year":"2022","unstructured":"Ahmad, F., Iqbal, A., Ashraf, I., Marzband, M., & Khan, I. (2022). Optimal location of electric vehicle charging station and its impact on distribution network: A review. Energy Reports, 8, 2314\u20132333. https:\/\/doi.org\/10.1016\/j.egyr.2022.01.180","journal-title":"Energy Reports"},{"key":"7110_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.cor.2016.05.018","volume":"79","author":"A Ahmadi-Javid","year":"2017","unstructured":"Ahmadi-Javid, A., Seyedi, P., & Syam, S. (2017). A survey of healthcare facility location. Computers & Operations Research, 79, 223\u2013263. https:\/\/doi.org\/10.1016\/j.cor.2016.05.018","journal-title":"Computers & Operations Research"},{"key":"7110_CR4","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s10589-007-9125-x","volume":"43","author":"P Avella","year":"2009","unstructured":"Avella, P., & Boccia, M. (2009). A cutting plane algorithm for the capacitated facility location problem. Computational Optimization and Applications, 43, 39\u201365. https:\/\/doi.org\/10.1007\/s10589-007-9125-x","journal-title":"Computational Optimization and Applications"},{"issue":"2","key":"7110_CR5","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.ejor.2020.07.033","volume":"289","author":"P Avella","year":"2021","unstructured":"Avella, P., Boccia, M., Mattia, S., & Rossi, F. (2021). Weak flow cover inequalities for the capacitated facility location problem. European Journal of Operational Research, 289(2), 485\u2013494. https:\/\/doi.org\/10.1016\/j.ejor.2020.07.033","journal-title":"European Journal of Operational Research"},{"key":"7110_CR6","unstructured":"Berman, P., Karpinski, M., Scott, A. (2003). Approximation hardness of short symmetric instances of MAX-3SAT."},{"key":"7110_CR7","unstructured":"B\u00fcsing, C., Gersing, T., Wrede, S. (2022). Analysing the complexity of facility location problems with capacities, revenues, and closest assignments. Proceedings of the 10th International Network Optimization Conference (INOC), Aachen, Germany, June 7\u201310, 2022, 81\u201386, https:\/\/doi.org\/10.48786\/inoc.2022.15"},{"key":"7110_CR8","doi-asserted-by":"publisher","unstructured":"B\u00fcsing, C., Leitner, M., & Wrede, S. (2025). Cover-based inequalities for the single-source capacitated facility location problem with customer preferences. Computers & Operations Research, 182, 107082. https:\/\/doi.org\/10.1016\/j.cor.2025.107082","DOI":"10.1016\/j.cor.2025.107082"},{"key":"7110_CR9","doi-asserted-by":"publisher","unstructured":"Cabezas, X., & Garc\u00eda, S. (2022). A semi-lagrangian relaxation heuristic algorithm for the simple plant location problem with order. Journal of the Operational Research Society, 1\u201312. https:\/\/doi.org\/10.1080\/01605682.2022.2150573","DOI":"10.1080\/01605682.2022.2150573"},{"key":"7110_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105066","volume":"124","author":"H Calvete","year":"2020","unstructured":"Calvete, H., Gal\u00e9, C., Iranzo, J., Camacho-Vallejo, J., & Casas-Ram\u00edrez, M. (2020). A matheuristic for solving the bilevel approach of the facility location problem with cardinality constraints and preferences. Computers & Operations Research, 124, Article 105066. https:\/\/doi.org\/10.1016\/j.cor.2020.105066","journal-title":"Computers & Operations Research"},{"issue":"2","key":"7110_CR11","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.orl.2006.01.012","volume":"35","author":"L C\u00e1novas","year":"2007","unstructured":"C\u00e1novas, L., Garc\u00eda, S., Labb\u00e9, M., & Mar\u00edn, A. (2007). A strengthened formulation for the simple plant location problem with order. Operations Research Letters, 35(2), 141\u2013150. https:\/\/doi.org\/10.1016\/j.orl.2006.01.012","journal-title":"Operations Research Letters"},{"key":"7110_CR12","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/j.amc.2017.03.051","volume":"319","author":"M Casas-Ram\u00edrez","year":"2018","unstructured":"Casas-Ram\u00edrez, M., Camacho-Vallejo, J., & Mart\u00ednez-Salazar, I. (2018). Approximating solutions to a bilevel capacitated facility location problem with customer\u2019s patronization toward a list of preferences. Applied Mathematics and Computation, 319, 369\u2013386. https:\/\/doi.org\/10.1016\/j.amc.2017.03.051","journal-title":"Applied Mathematics and Computation"},{"key":"7110_CR13","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s10479-019-03385-x","volume":"292","author":"D Celik Turkoglu","year":"2020","unstructured":"Celik Turkoglu, D., & Erol Genevois, M. (2020). A comparative survey of service facility location problems. Annals of Operations Research, 292, 399\u2013468. https:\/\/doi.org\/10.1007\/s10479-019-03385-x","journal-title":"Annals of Operations Research"},{"issue":"1","key":"7110_CR14","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ejor.2011.12.002","volume":"219","author":"I Espejo","year":"2012","unstructured":"Espejo, I., Mar\u00edn, A., & Rodr\u00edguez-Ch\u00eda, A. M. (2012). Closest assignment constraints in discrete location problems. European Journal of Operational Research, 219(1), 49\u201358. https:\/\/doi.org\/10.1016\/j.ejor.2011.12.002","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"7110_CR15","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/j.ejor.2016.03.002","volume":"253","author":"M Fischetti","year":"2016","unstructured":"Fischetti, M., Ljubi\u0107, I., & Sinnl, M. (2016). Benders decomposition without separability: A computational study for capacitated facility location problems. European Journal of Operational Research, 253(3), 557\u2013569. https:\/\/doi.org\/10.1016\/j.ejor.2016.03.002","journal-title":"European Journal of Operational Research"},{"key":"7110_CR16","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.mathsocsci.2019.07.005","volume":"101","author":"J Gan","year":"2019","unstructured":"Gan, J., Suksompong, W., & Voudouris, W. (2019). Envy-freeness in house allocation problems. Mathematical Social Sciences, 101, 104\u2013106. https:\/\/doi.org\/10.1016\/j.mathsocsci.2019.07.005","journal-title":"Mathematical Social Sciences"},{"key":"7110_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., & Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. New York: W. H. Freeman & Co., New York, USA."},{"issue":"4","key":"7110_CR18","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0966-8349(97)00001-6","volume":"4","author":"RA Gerrard","year":"1996","unstructured":"Gerrard, R. A., & Church, R. L. (1996). Closest assignment constraints and location models: Properties and structure. Location Science, 4(4), 251\u2013270. https:\/\/doi.org\/10.1016\/S0966-8349(97)00001-6","journal-title":"Location Science"},{"issue":"4","key":"7110_CR19","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1287\/ijoc.1110.0468","volume":"24","author":"S G\u00f6rtz","year":"2012","unstructured":"G\u00f6rtz, S., & Klose, A. (2012). A simple but usually fast branch-and-bound algorithm for the capacitated facility location problem. INFORMS Journal on Computing, 24(4), 597\u2013610. https:\/\/doi.org\/10.1287\/ijoc.1110.0468","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"7110_CR20","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0166-0462(87)90011-1","volume":"17","author":"P Hanjoul","year":"1987","unstructured":"Hanjoul, P., & Peeters, D. (1987). A facility location problem with clients\u2019 preference orderings. Regional Science and Urban Economics, 17(3), 451\u2013473. https:\/\/doi.org\/10.1016\/0166-0462(87)90011-1","journal-title":"Regional Science and Urban Economics"},{"key":"7110_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-56039-6","volume-title":"Combinatorial optimization: Theory and algorithms","author":"BH Korte","year":"2018","unstructured":"Korte, B. H., & Vygen, J. (2018). Combinatorial optimization: Theory and algorithms. New York: Springer."},{"key":"7110_CR22","doi-asserted-by":"crossref","unstructured":"Laporte, G., Nickel, S., & Saldanha da Gama, F. (Eds.). (2019). Location science (2nd ed.). Switzerland: Springer.","DOI":"10.1007\/978-3-030-32177-2"},{"key":"7110_CR23","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF01587093","volume":"44","author":"JMY Leung","year":"1989","unstructured":"Leung, J. M. Y., & Magnanti, T. L. (1989). Valid inequalities and facets of the capacitated plant location problem. Mathematical Programming, 44, 271\u2013291. https:\/\/doi.org\/10.1007\/BF01587093","journal-title":"Mathematical Programming"},{"issue":"3","key":"7110_CR24","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1016\/j.ejor.2014.07.024","volume":"240","author":"A Mestre","year":"2015","unstructured":"Mestre, A., Oliveira, M., & Barbosa-P\u00f3voa, A. (2015). Location\u2013allocation approaches for hospital network planning under uncertainty. European Journal of Operational Research, 240(3), 791\u2013806. https:\/\/doi.org\/10.1016\/j.ejor.2014.07.024","journal-title":"European Journal of Operational Research"},{"key":"7110_CR25","unstructured":"Mirchandani, P., & Francis, R. (Eds.). (1990). Discrete Location Theory. New York: Wiley."},{"key":"7110_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/itor.13368","volume":"0","author":"S Polino","year":"2023","unstructured":"Polino, S., Camacho-Vallejo, J.-F., & Villegas, J. G. (2023). A facility location problem for extracurricular workshop planning: bi-level model and metaheuristics. International Transactions in Operational Research, 0, 1\u201343. https:\/\/doi.org\/10.1111\/itor.13368","journal-title":"International Transactions in Operational Research"},{"issue":"4","key":"7110_CR27","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1111\/j.1538-4632.1970.tb00864.x","volume":"2","author":"P Rojeski","year":"1970","unstructured":"Rojeski, P., & ReVelle, C. (1970). Central facilities location under an investment constraint. Geographical Analysis, 2(4), 343\u2013360. https:\/\/doi.org\/10.1111\/j.1538-4632.1970.tb00864.x","journal-title":"Geographical Analysis"},{"key":"7110_CR28","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.orl.2012.12.006","volume":"41","author":"I Vasilyev","year":"2013","unstructured":"Vasilyev, I., Klimentova, X., & Boccia, M. (2013). Polyhedral study of simple plant location problem with order. Oper. Res. Lett., 41, 153\u2013158. https:\/\/doi.org\/10.1016\/j.orl.2012.12.006","journal-title":"Oper. Res. Lett."},{"key":"7110_CR29","doi-asserted-by":"publisher","first-page":"2010","DOI":"10.1134\/S0965542509060098","volume":"49","author":"I Vasilyev","year":"2009","unstructured":"Vasilyev, I., Klimentova, X., & Kochetov, Y. A. (2009). New lower bounds for the facility location problem with clients\u2019 preferences. Computational Mathematics and Mathematical Physics, 49, 2010\u20132020. https:\/\/doi.org\/10.1134\/S0965542509060098","journal-title":"Computational Mathematics and Mathematical Physics"},{"issue":"1","key":"7110_CR30","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1111\/j.1538-4632.1975.tb01024.x","volume":"7","author":"JL Wagner","year":"1975","unstructured":"Wagner, J. L., & Falkson, L. M. (1975). The optimal nodal location of public facilities with price-sensitive demand. Geographical Analysis, 7(1), 69\u201383. https:\/\/doi.org\/10.1111\/j.1538-4632.1975.tb01024.x","journal-title":"Geographical Analysis"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07110-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-026-07110-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07110-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T12:20:43Z","timestamp":1775737243000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-026-07110-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,2]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["7110"],"URL":"https:\/\/doi.org\/10.1007\/s10479-026-07110-3","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,2]]},"assertion":[{"value":"10 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}