{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,29]],"date-time":"2025-03-29T04:16:39Z","timestamp":1743221799552,"version":"3.40.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T00:00:00Z","timestamp":1737072000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T00:00:00Z","timestamp":1737072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Karlsruher Institut f\u00fcr Technologie (KIT)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This paper investigates a Multi-Stage Stochastic Districting Problem (MSSDP). The goal is to devise a districting plan (i.e., clusters of Territorial Units\u2014TUs) accounting for uncertain parameters changing over a discrete multi-period planning horizon. The problem is cast as a multi-stage stochastic programming problem. It is assumed that uncertainty can be captured by a finite set of scenarios, which induces a scenario tree. Each node in the tree corresponds to the realization of all the stochastic parameters from the root node\u2014the state of nature\u2014up to that node. A mathematical programming model is proposed that embeds redistricting recourse decisions and other recourse actions to ensure that the districts are balanced regarding their activity. The model is tested on instances generated using literature data containing real geographical data. The results demonstrate the relevance of hedging against uncertainty in multi-period districting. Since the model is challenging to tackle using a general-purpose solver, a heuristic algorithm is proposed based on a restricted model. The computational results obtained give evidence that the approximate algorithm can produce high-quality feasible solutions within acceptable computation times.<\/jats:p>","DOI":"10.1007\/s10479-024-06459-7","type":"journal-article","created":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T20:30:29Z","timestamp":1737145829000},"page":"2225-2251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Multi-stage stochastic districting: optimization models and solution algorithms"],"prefix":"10.1007","volume":"346","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-6087-5363","authenticated-orcid":false,"given":"Anika","family":"Pomes","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9775-3927","authenticated-orcid":false,"given":"Antonio","family":"Diglio","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8339-0117","authenticated-orcid":false,"given":"Stefan","family":"Nickel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2074-1856","authenticated-orcid":false,"given":"Francisco","family":"Saldanha-da-Gama","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,17]]},"reference":[{"key":"6459_CR1","doi-asserted-by":"publisher","first-page":"2950","DOI":"10.1016\/j.cor.2013.06.015","volume":"40","author":"U Aldasoro","year":"2013","unstructured":"Aldasoro, U., Escudero, L., Merino, M., & P\u00e9rez, G. (2013). An algorithmic framework for solving large-scale multistage stochastic mixed 0\u20131 problems with nonsymmetric scenario trees. Part II: Parallelization. Computers & Operations Research, 40, 2950\u20132960.","journal-title":"Computers & Operations Research"},{"key":"6459_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2023.106376","volume":"160","author":"S Baldassarre","year":"2023","unstructured":"Baldassarre, S., Bruno, G., Diglio, A., & Piccolo, C. (2023). A sample approximation solution procedure for chance-constrained districting problems. Computers & Operations Research, 160, 106376.","journal-title":"Computers & Operations Research"},{"key":"6459_CR3","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1111\/j.1937-5956.2010.01194.x","volume":"20","author":"O Baron","year":"2011","unstructured":"Baron, O., Milner, J., & Naseraldin, H. (2011). Facility location: A robust optimization approach. Production and Operations Management, 20, 772\u2013785.","journal-title":"Production and Operations Management"},{"issue":"4","key":"6459_CR4","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1017\/S0305004100034095","volume":"55","author":"J Beardwood","year":"1959","unstructured":"Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959). The shortest path through many points. Mathematical proceedings of the Cambridge philosophical society, 55(4), 299\u2013327.","journal-title":"Mathematical proceedings of the Cambridge philosophical society"},{"key":"6459_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.omega.2020.102283","volume":"96","author":"M Bender","year":"2020","unstructured":"Bender, M., Kalcsics, J., & Meyer, A. (2020). Districting for parcel delivery services-a two-stage solution approach and a real-world case study. Omega, 96, 102283.","journal-title":"Omega"},{"key":"6459_CR6","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.ejor.2018.01.047","volume":"269","author":"M Bender","year":"2018","unstructured":"Bender, M., Kalcsics, J., Nickel, S., & Pouls, M. (2018). A branch-and-price algorithm for the scheduling of customer visits in the context of multi-period service territory design. European Journal of Operational Research, 269, 382\u2013396.","journal-title":"European Journal of Operational Research"},{"key":"6459_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tre.2016.09.007","volume":"96","author":"M Bender","year":"2016","unstructured":"Bender, M., Meyer, A., Kalcsics, J., & Nickel, S. (2016). The multi-period service territory design problem-an introduction, a model and a heuristic approach. Transportation Research Part E: Logistics and Transportation Review, 96, 135\u2013157.","journal-title":"Transportation Research Part E: Logistics and Transportation Review"},{"key":"6459_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.seps.2015.11.001","volume":"53","author":"G Bruno","year":"2016","unstructured":"Bruno, G., Esposito, E., Genovese, A., & Piccolo, C. (2016). Institutions and facility mergers in the Italian education system: Models and case studies. Socio-Economic Planning Sciences, 53, 23\u201332.","journal-title":"Socio-Economic Planning Sciences"},{"key":"6459_CR9","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1287\/opre.2013.1160","volume":"61","author":"J Carlsson","year":"2013","unstructured":"Carlsson, J., & Delage, E. (2013). Robust partitioning for stochastic multivehicle routing. Operations Research, 61, 727\u2013744.","journal-title":"Operations Research"},{"issue":"1","key":"6459_CR10","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10479-020-03631-7","volume":"292","author":"A Diglio","year":"2020","unstructured":"Diglio, A., Nickel, S., & Saldanha-da Gama, F. (2020). Towards a stochastic programming modeling framework for districting. Annals of Operations Research, 292(1), 249\u2013285.","journal-title":"Annals of Operations Research"},{"key":"6459_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.omega.2021.102430","volume":"103","author":"A Diglio","year":"2021","unstructured":"Diglio, A., Peir\u00f3, J., Piccolo, C., & Saldanha-da-Gama, F. (2021). Solutions for districting problems with chance-constrained balancing requirements. Omega, 103, 102430.","journal-title":"Omega"},{"issue":"1","key":"6459_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.ejor.2022.09.005","volume":"307","author":"A Diglio","year":"2023","unstructured":"Diglio, A., Peir\u00f3, J., Piccolo, C., & Saldanha-da Gama, F. (2023). Approximation schemes for districting problems with probabilistic constraints. European Journal of Operational Research, 307(1), 233\u2013248.","journal-title":"European Journal of Operational Research"},{"key":"6459_CR13","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/s11750-007-0005-4","volume":"15","author":"L Escudero","year":"2007","unstructured":"Escudero, L., Gar\u00edn, M., Merino, M., & P\u00e9rez, G. (2007). The value of the stochastic solution in multistage problems. TOP, 15, 48\u201364.","journal-title":"TOP"},{"key":"6459_CR14","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1016\/j.cor.2009.06.023","volume":"37","author":"L Escudero","year":"2010","unstructured":"Escudero, L., Gar\u00edn, M., Merino, M., & P\u00e9rez, G. (2010). On BFC-MSMIP strategies for scenario cluster partitioning, and twin node family branching selection and bounding for multistage stochastic mixed integer programming. Computers & Operations Research, 37, 738\u2013753.","journal-title":"Computers & Operations Research"},{"key":"6459_CR15","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1016\/j.cor.2011.06.021","volume":"39","author":"L Escudero","year":"2012","unstructured":"Escudero, L., Gar\u00edn, M., Merino, M., & P\u00e9rez, G. (2012). An algorithmic framework for solving large-scale multistage stochastic mixed 0\u20131 problems with nonsymmetric scenario trees. Computers & Operations Research, 39, 1133\u20131144.","journal-title":"Computers & Operations Research"},{"key":"6459_CR16","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s10287-018-0318-9","volume":"15","author":"LF Escudero","year":"2018","unstructured":"Escudero, L. F., & Monge, J. F. (2018). On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse management. Computational Management Science, 15, 479\u2013500.","journal-title":"Computational Management Science"},{"key":"6459_CR17","doi-asserted-by":"crossref","unstructured":"Farughi, H., Tavana, M., Mostafayi, S., & Arteaga, F. J. S. (2019). A novel optimization model for designing compact, balanced, and contiguous healthcare districts. Journal of the Operational Research Society.","DOI":"10.1080\/01605682.2019.1621217"},{"key":"6459_CR18","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/j.ejor.2005.11.070","volume":"180","author":"D Haugland","year":"2007","unstructured":"Haugland, D., Ho, S., & Laporte, G. (2007). Designing delivery districts for the vehicle routing problem with stochastic demands. European Journal of Operational Research, 180, 997\u20131010.","journal-title":"European Journal of Operational Research"},{"key":"6459_CR19","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.orp.2015.03.001","volume":"2","author":"AA Juan","year":"2015","unstructured":"Juan, A. A., Faulin, J., Grasman, S. E., Rabe, M., & Figueira, G. (2015). A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems. Operations Research Perspectives, 2, 62\u201372.","journal-title":"Operations Research Perspectives"},{"key":"6459_CR20","doi-asserted-by":"crossref","unstructured":"Kalcsics, J. and R\u00edos-Mercado, R. (2019). Districting problems. In G. Laporte, S. Nickel, & F. Saldanha-da-Gama (Eds.), Location Science (2nd ed., Chapter 25, pp. 705\u2013743). Springer International Publishing.","DOI":"10.1007\/978-3-030-32177-2_25"},{"issue":"1","key":"6459_CR21","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10287-013-0182-6","volume":"11","author":"M Kaut","year":"2014","unstructured":"Kaut, M., Midthun, K. T., Werner, A. S., Tomasgard, A., Hellemo, L., & Fodstad, M. (2014). Multi-horizon stochastic programming. Computational Management Science, 11(1), 179\u2013193.","journal-title":"Computational Management Science"},{"key":"6459_CR22","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s13676-012-0005-x","volume":"1","author":"H Lei","year":"2012","unstructured":"Lei, H., Laporte, G., & Guo, B. (2012). Districting for routing with stochastic customers. EURO Journal on Transportation and Logistics, 1, 67\u201385.","journal-title":"EURO Journal on Transportation and Logistics"},{"key":"6459_CR23","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.cor.2014.11.008","volume":"56","author":"H Lei","year":"2015","unstructured":"Lei, H., Laporte, G., Liu, Y., & Zhang, T. (2015). Dynamic design of sales territories. Computers & Operations Research, 56, 84\u201392.","journal-title":"Computers & Operations Research"},{"key":"6459_CR24","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.cor.2015.09.002","volume":"67","author":"H Lei","year":"2016","unstructured":"Lei, H., Wang, R., & Laporte, G. (2016). Solving a multi-objective dynamic stochastic districting and routing problem with a co-evolutionary algorithm. Computers & Operations Research, 67, 12\u201324.","journal-title":"Computers & Operations Research"},{"key":"6459_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105425","volume":"135","author":"S Mostafayi Darmian","year":"2021","unstructured":"Mostafayi Darmian, S., Fattahi, M., & Keyvanshokooh, E. (2021). An optimization-based approach for the healthcare districting under uncertainty. Computers & Operations Research, 135, 105425.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"6459_CR26","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10479-012-1267-2","volume":"204","author":"F Ricca","year":"2013","unstructured":"Ricca, F., Scozzari, A., & Simeone, B. (2013). Political districting: From classical models to recent approaches. Annals of Operations Research, 204(1), 271\u2013299.","journal-title":"Annals of Operations Research"},{"volume-title":"Optimal districting and territory design","year":"2020","key":"6459_CR27","unstructured":"R\u00edos-Mercado, R. Z. (Ed.). (2020). Optimal districting and territory design. Springer International Publishing."},{"issue":"3","key":"6459_CR28","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.omega.2012.08.002","volume":"41","author":"RZ R\u00edos-Mercado","year":"2013","unstructured":"R\u00edos-Mercado, R. Z., & L\u00f3pez-P\u00e9rez, J. F. (2013). Commercial territory design planning with realignment and disjoint assignment requirements. Omega, 41(3), 525\u2013535.","journal-title":"Omega"},{"issue":"3","key":"6459_CR29","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s11067-010-9151-6","volume":"11","author":"MA Salazar-Aguilar","year":"2011","unstructured":"Salazar-Aguilar, M. A., R\u00edos-Mercado, R. Z., & Cabrera-R\u00edos, M. (2011). New models for commercial territory design. Networks and Spatial Economics, 11(3), 487\u2013507.","journal-title":"Networks and Spatial Economics"},{"key":"6459_CR30","doi-asserted-by":"crossref","unstructured":"Saldanha-da-Gama, F., & Wang, S. (2024). Territory design. In F. Saldanha-da-Gama & S. Wang (Eds.), Facility Location Under Uncertainty: Models, Algorithms and Applications (Chapter 13, pp. 415\u2013436). Springer International Publishing.","DOI":"10.1007\/978-3-031-55927-3_13"},{"key":"6459_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.omega.2022.102687","volume":"113","author":"MG Sandoval","year":"2022","unstructured":"Sandoval, M. G., \u00c1lvarez-Miranda, E., Pereira, J., R\u00edos-Mercado, R. Z., & D\u00edaz, J. A. (2022). A novel districting design approach for on-time last-mile delivery: An application on an express postal company. Omega, 113, 102687.","journal-title":"Omega"},{"issue":"5","key":"6459_CR32","doi-asserted-by":"publisher","first-page":"1676","DOI":"10.1111\/itor.12633","volume":"26","author":"S Yan\u0131k","year":"2019","unstructured":"Yan\u0131k, S., Kalcsics, J., Nickel, S., & Bozkaya, B. (2019). A multi-period multi-criteria districting problem applied to primary care scheme with gradual assignment. International Transactions in Operational Research, 26(5), 1676\u20131697.","journal-title":"International Transactions in Operational Research"},{"key":"6459_CR33","unstructured":"Ziegler, H.-P. (2012). Algorithms for linear stochastic programs and their application in supply chain network design problems. PhD thesis, Karlsruhe Institute of Technology, KIT."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-06459-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-024-06459-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-06459-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,29]],"date-time":"2025-03-29T01:51:55Z","timestamp":1743213115000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-024-06459-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,17]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["6459"],"URL":"https:\/\/doi.org\/10.1007\/s10479-024-06459-7","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2025,1,17]]},"assertion":[{"value":"20 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}