IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v346y2025i3d10.1007_s10479-024-06459-7.html
   My bibliography  Save this article

Multi-stage stochastic districting: optimization models and solution algorithms

Author

Listed:
  • Anika Pomes

    (Karlsruhe Institute of Technology (KIT))

  • Antonio Diglio

    (Università degli Studi di Napoli Federico II)

  • Stefan Nickel

    (Karlsruhe Institute of Technology (KIT)
    Research Center for Information Technology (FZI))

  • Francisco Saldanha-da-Gama

    (Sheffield University Management School)

Abstract

This paper investigates a Multi-Stage Stochastic Districting Problem (MSSDP). The goal is to devise a districting plan (i.e., clusters of Territorial Units—TUs) 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—the state of nature—up 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.

Suggested Citation

  • Anika Pomes & Antonio Diglio & Stefan Nickel & Francisco Saldanha-da-Gama, 2025. "Multi-stage stochastic districting: optimization models and solution algorithms," Annals of Operations Research, Springer, vol. 346(3), pages 2225-2251, March.
    • Handle: RePEc:spr:annopr:v:346:y:2025:i:3:d:10.1007_s10479-024-06459-7
    DOI: 10.1007/s10479-024-06459-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-024-06459-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-024-06459-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Bruno, Giuseppe & Esposito, Emilio & Genovese, Andrea & Piccolo, Carmela, 2016. "Institutions and facility mergers in the Italian education system: Models and case studies," Socio-Economic Planning Sciences, Elsevier, vol. 53(C), pages 23-32.
    2. Diglio, Antonio & Peiró, Juanjo & Piccolo, Carmela & Saldanha-da-Gama, Francisco, 2023. "Approximation schemes for districting problems with probabilistic constraints," European Journal of Operational Research, Elsevier, vol. 307(1), pages 233-248.
    3. Laureano F. Escudero & Juan F. Monge, 2018. "On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse management," Computational Management Science, Springer, vol. 15(3), pages 479-500, October.
    4. Laureano Escudero & Araceli Garín & María Merino & Gloria Pérez, 2007. "The value of the stochastic solution in multistage problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 15(1), pages 48-64, July.
    5. Federica Ricca & Andrea Scozzari & Bruno Simeone, 2013. "Political Districting: from classical models to recent approaches," Annals of Operations Research, Springer, vol. 204(1), pages 271-299, April.
    6. Sandoval, M. Gabriela & Álvarez-Miranda, Eduardo & Pereira, Jordi & Ríos-Mercado, Roger Z. & Díaz, Juan A., 2022. "A novel districting design approach for on-time last-mile delivery: An application on an express postal company," Omega, Elsevier, vol. 113(C).
    7. Juan, Angel A. & Faulin, Javier & Grasman, Scott E. & Rabe, Markus & Figueira, Gonçalo, 2015. "A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems," Operations Research Perspectives, Elsevier, vol. 2(C), pages 62-72.
    8. Haugland, Dag & Ho, Sin C. & Laporte, Gilbert, 2007. "Designing delivery districts for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 180(3), pages 997-1010, August.
    9. María Salazar-Aguilar & Roger Ríos-Mercado & Mauricio Cabrera-Ríos, 2011. "New Models for Commercial Territory Design," Networks and Spatial Economics, Springer, vol. 11(3), pages 487-507, September.
    10. John Gunnar Carlsson & Erick Delage, 2013. "Robust Partitioning for Stochastic Multivehicle Routing," Operations Research, INFORMS, vol. 61(3), pages 727-744, June.
    11. Michal Kaut & Kjetil Midthun & Adrian Werner & Asgeir Tomasgard & Lars Hellemo & Marte Fodstad, 2014. "Multi-horizon stochastic programming," Computational Management Science, Springer, vol. 11(1), pages 179-193, January.
    12. Bender, Matthias & Kalcsics, Jörg & Meyer, Anne, 2020. "Districting for parcel delivery services – A two-Stage solution approach and a real-World case study," Omega, Elsevier, vol. 96(C).
    13. Bender, Matthias & Kalcsics, Jörg & Nickel, Stefan & Pouls, Martin, 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, Elsevier, vol. 269(1), pages 382-396.
    14. Diglio, Antonio & Peiró, Juanjo & Piccolo, Carmela & Saldanha-da-Gama, Francisco, 2021. "Solutions for districting problems with chance-constrained balancing requirements," Omega, Elsevier, vol. 103(C).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Diglio, Antonio & Peiró, Juanjo & Piccolo, Carmela & Saldanha-da-Gama, Francisco, 2021. "Solutions for districting problems with chance-constrained balancing requirements," Omega, Elsevier, vol. 103(C).
    2. Diglio, Antonio & Peiró, Juanjo & Piccolo, Carmela & Saldanha-da-Gama, Francisco, 2023. "Approximation schemes for districting problems with probabilistic constraints," European Journal of Operational Research, Elsevier, vol. 307(1), pages 233-248.
    3. Sandoval, M. Gabriela & Álvarez-Miranda, Eduardo & Pereira, Jordi & Ríos-Mercado, Roger Z. & Díaz, Juan A., 2022. "A novel districting design approach for on-time last-mile delivery: An application on an express postal company," Omega, Elsevier, vol. 113(C).
    4. Zhen, Lu & Gao, Jiajing & Tan, Zheyi & Laporte, Gilbert & Baldacci, Roberto, 2023. "Territorial design for customers with demand frequency," European Journal of Operational Research, Elsevier, vol. 309(1), pages 82-101.
    5. Antonio Diglio & Stefan Nickel & Francisco Saldanha-da-Gama, 2020. "Towards a stochastic programming modeling framework for districting," Annals of Operations Research, Springer, vol. 292(1), pages 249-285, September.
    6. Arevalo-Ascanio, Rafael & De Meyer, Annelies & Gevaers, Roel & Guisson, Ruben & Dewulf, Wouter, 2024. "From operational to strategic modelling: A continuous multi-scale approach for last-mile analysis," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 191(C).
    7. Bender, Matthias & Kalcsics, Jörg & Meyer, Anne, 2020. "Districting for parcel delivery services – A two-Stage solution approach and a real-World case study," Omega, Elsevier, vol. 96(C).
    8. Giovanni Pantuso & Trine K. Boomsma, 2020. "On the number of stages in multistage stochastic programs," Annals of Operations Research, Springer, vol. 292(2), pages 581-603, September.
    9. Domínguez, Ruth & Vitali, Sebastiano & Carrión, Miguel & Moriggia, Vittorio, 2021. "Analysing decarbonizing strategies in the European power system applying stochastic dominance constraints," Energy Economics, Elsevier, vol. 101(C).
    10. Juan A. Díaz & Dolores E. Luna, 2017. "Primal and dual bounds for the vertex p-median problem with balance constraints," Annals of Operations Research, Springer, vol. 258(2), pages 613-638, November.
    11. Nils Boysen & Stefan Fedtke & Stefan Schwerdfeger, 2021. "Last-mile delivery concepts: a survey from an operational research perspective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 1-58, March.
    12. Sebastián Moreno & Jordi Pereira & Wilfredo Yushimito, 2020. "A hybrid K-means and integer programming method for commercial territory design: a case study in meat distribution," Annals of Operations Research, Springer, vol. 286(1), pages 87-117, March.
    13. Castro, Jordi & Escudero, Laureano F. & Monge, Juan F., 2023. "On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach," European Journal of Operational Research, Elsevier, vol. 310(1), pages 268-285.
    14. Zhou, Lin & Zhen, Lu & Baldacci, Roberto & Boschetti, Marco & Dai, Ying & Lim, Andrew, 2021. "A Heuristic Algorithm for solving a large-scale real-world territory design problem," Omega, Elsevier, vol. 103(C).
    15. Ouyang, Zhiyuan & Leung, Eric K.H. & Huang, George Q., 2023. "Community logistics and dynamic community partitioning: A new approach for solving e-commerce last mile delivery," European Journal of Operational Research, Elsevier, vol. 307(1), pages 140-156.
    16. Ouyang, Zhiyuan & Leung, Eric Ka Ho & Huang, George Q., 2022. "Community logistics for dynamic vehicle dispatching: The effects of community departure “time” and “space”," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    17. Dinçer Konur & Joseph Geunes, 2019. "Integrated districting, fleet composition, and inventory planning for a multi-retailer distribution system," Annals of Operations Research, Springer, vol. 273(1), pages 527-559, February.
    18. Hongyu Zhang & Ignacio E. Grossmann & Asgeir Tomasgard, 2024. "Decomposition methods for multi-horizon stochastic programming," Computational Management Science, Springer, vol. 21(1), pages 1-24, June.
    19. Laureano F. Escudero & Juan F. Monge, 2021. "On Multistage Multiscale Stochastic Capacitated Multiple Allocation Hub Network Expansion Planning," Mathematics, MDPI, vol. 9(24), pages 1-39, December.
    20. Noordhoek, Marije & Dullaert, Wout & Lai, David S.W. & de Leeuw, Sander, 2018. "A simulation–optimization approach for a service-constrained multi-echelon distribution network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 292-311.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:346:y:2025:i:3:d:10.1007_s10479-024-06459-7. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.