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

Towards a stochastic programming modeling framework for districting

Author

Listed:
  • Antonio Diglio

    (Università degli Studi di Napoli Federico II)

  • Stefan Nickel

    (Karlsruhe Institute of Technology (KIT)
    Department of Logistics and Supply Chain Optimization, Research Center for Information Technology (FZI))

  • Francisco Saldanha-da-Gama

    (Faculdade de Ciências da Universidade de Lisboa
    Faculdade de Ciências da Universidade de Lisboa)

Abstract

In this paper a stochastic districting problem is investigated. Demand is assumed to be represented by a random vector with a given joint probability distribution function. A two-stage mixed-integer stochastic programming model is proposed. The first stage comprises the decision about the initial territory design: the districts are defined and all the territory units assigned to one and exactly one of them. In the second stage, i.e., after demand becomes known, balancing requirements are to be met. This is ensured by means of two recourse actions: outsourcing and reassignment of territory units. The objective function accounts for the total expected cost that includes the cost for the first-stage territory design plus the expected cost incurred at the second stage by outsourcing and reassignment. The (re)assignment costs are associated with the distances between territory units, i.e., the focus is put on the compactness of the solution. The model is then extended in different ways to account for aspects of practical relevance such as a maximum desirable dispersion, reallocation constraints, or similarity of the second-stage solution w.r.t. the first-stage one. The new modeling framework proposed is tested computationally using instances built using real geographical data.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:292:y:2020:i:1:d:10.1007_s10479-020-03631-7
    DOI: 10.1007/s10479-020-03631-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-020-03631-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-020-03631-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. Pierre de la Poix de Fréminville & Guy Desaulniers & Louis-Martin Rousseau & Sylvain Perron, 2015. "A column generation heuristic for districting the price of a financial product," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(6), pages 965-978, June.
    2. Ricca, Federica & Simeone, Bruno, 2008. "Local search algorithms for political districting," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1409-1426, September.
    3. Bard, Jonathan F. & Jarrah, Ahmad I., 2009. "Large-scale constrained clustering for rationalizing pickup and delivery operations," Transportation Research Part B: Methodological, Elsevier, vol. 43(5), pages 542-561, June.
    4. 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.
    5. 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.
    6. Bender, Matthias & Meyer, Anne & Kalcsics, Jörg & Nickel, Stefan, 2016. "The multi-period service territory design problem – An introduction, a model and a heuristic approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 96(C), pages 135-157.
    7. Jacques A. Ferland & Gilles Guénette, 1990. "Decision Support System for the School Districting Problem," Operations Research, INFORMS, vol. 38(1), pages 15-21, February.
    8. Camacho-Collados, M. & Liberatore, F. & Angulo, J.M., 2015. "A multi-criteria Police Districting Problem for the efficient and effective design of patrol sector," European Journal of Operational Research, Elsevier, vol. 246(2), pages 674-684.
    9. Bozkaya, Burcin & Erkut, Erhan & Laporte, Gilbert, 2003. "A tabu search heuristic and adaptive memory procedure for political districting," European Journal of Operational Research, Elsevier, vol. 144(1), pages 12-26, January.
    10. S. W. Hess & J. B. Weaver & H. J. Siegfeldt & J. N. Whelan & P. A. Zitlau, 1965. "Nonpartisan Political Redistricting by Computer," Operations Research, INFORMS, vol. 13(6), pages 998-1006, December.
    11. Mourão, Maria Cândida & Nunes, Ana Catarina & Prins, Christian, 2009. "Heuristic methods for the sectoring arc routing problem," European Journal of Operational Research, Elsevier, vol. 196(3), pages 856-868, August.
    12. John Gunnar Carlsson & Erick Delage, 2013. "Robust Partitioning for Stochastic Multivehicle Routing," Operations Research, INFORMS, vol. 61(3), pages 727-744, June.
    13. Bruno, Giuseppe & Genovese, Andrea & Piccolo, Carmela, 2017. "Territorial amalgamation decisions in local government: Models and a case study from Italy," Socio-Economic Planning Sciences, Elsevier, vol. 57(C), pages 61-72.
    14. F Caro & T Shirabe & M Guignard & A Weintraub, 2004. "School redistricting: embedding GIS tools with integer programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(8), pages 836-849, August.
    15. 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.
    16. Schoepfle, O. Benjamin & Church, Richard L., 1991. "A new network representation of a "classic" school districting problem," Socio-Economic Planning Sciences, Elsevier, vol. 25(3), pages 189-197.
    17. 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.
    18. Fernando Tavares-Pereira & José Figueira & Vincent Mousseau & Bernard Roy, 2007. "Multiple criteria districting problems," Annals of Operations Research, Springer, vol. 154(1), pages 69-92, October.
    19. Paul Bergey & Cliff Ragsdale & Mangesh Hoskote, 2003. "A Simulated Annealing Genetic Algorithm for the Electrical Power Districting Problem," Annals of Operations Research, Springer, vol. 121(1), pages 33-55, July.
    20. Hongsheng Zhong & Randolph W. Hall & Maged Dessouky, 2007. "Territory Planning and Vehicle Dispatching with Driver Learning," Transportation Science, INFORMS, vol. 41(1), pages 74-89, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    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.

    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. 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.
    2. Baghersad, Milad & Emadikhiav, Mohsen & Huang, C. Derrick & Behara, Ravi S., 2023. "Modularity maximization to design contiguous policy zones for pandemic response," European Journal of Operational Research, Elsevier, vol. 304(1), pages 99-112.
    3. 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.
    4. Alexander Butsch & Jörg Kalcsics & Gilbert Laporte, 2014. "Districting for Arc Routing," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 809-824, November.
    5. 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.
    6. 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).
    7. 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).
    8. Bruno, Giuseppe & Genovese, Andrea & Piccolo, Carmela, 2017. "Territorial amalgamation decisions in local government: Models and a case study from Italy," Socio-Economic Planning Sciences, Elsevier, vol. 57(C), pages 61-72.
    9. 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.
    10. 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).
    11. Eduardo Álvarez-Miranda & Camilo Campos-Valdés & Maurcio Morales Quiroga & Matías Moreno-Faguett & Jordi Pereira, 2020. "A Multi-Criteria Pen for Drawing Fair Districts: When Democratic and Demographic Fairness Matter," Mathematics, MDPI, vol. 8(9), pages 1-26, August.
    12. Steiner, Maria Teresinha Arns & Datta, Dilip & Steiner Neto, Pedro José & Scarpin, Cassius Tadeu & Rui Figueira, José, 2015. "Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil," Omega, Elsevier, vol. 52(C), pages 53-64.
    13. Jörg Kalcsics & Stefan Nickel & Michael Schröder, 2005. "Towards a unified territorial design approach — Applications, algorithms and GIS integration," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 13(1), pages 1-56, June.
    14. Mayerle, Sérgio F. & Rodrigues, Hidelbrando F. & Neiva de Figueiredo, João & De Genaro Chiroli, Daiane M., 2022. "Optimal student/school/class/teacher/classroom matching to support efficient public school system resource allocation," Socio-Economic Planning Sciences, Elsevier, vol. 83(C).
    15. Fernando Tavares-Pereira & José Figueira & Vincent Mousseau & Bernard Roy, 2007. "Multiple criteria districting problems," Annals of Operations Research, Springer, vol. 154(1), pages 69-92, October.
    16. Christian Haas & Lee Hachadoorian & Steven O Kimbrough & Peter Miller & Frederic Murphy, 2020. "Seed-Fill-Shift-Repair: A redistricting heuristic for civic deliberation," PLOS ONE, Public Library of Science, vol. 15(9), pages 1-34, September.
    17. Anderson Kenji Hirose & Cassius Tadeu Scarpin & José Eduardo Pécora Junior, 2020. "Goal programming approach for political districting in Santa Catarina State: Brazil," Annals of Operations Research, Springer, vol. 287(1), pages 209-232, April.
    18. Camacho-Collados, M. & Liberatore, F. & Angulo, J.M., 2015. "A multi-criteria Police Districting Problem for the efficient and effective design of patrol sector," European Journal of Operational Research, Elsevier, vol. 246(2), pages 674-684.
    19. Verónica Arredondo & Miguel Martínez-Panero & Teresa Peña & Federica Ricca, 2021. "Mathematical political districting taking care of minority groups," Annals of Operations Research, Springer, vol. 305(1), pages 375-402, October.
    20. Rui Fragoso & Conceição Rego & Vladimir Bushenkov, 2016. "Clustering of Territorial Areas: A Multi-Criteria Districting Problem," Journal of Quantitative Economics, Springer;The Indian Econometric Society (TIES), vol. 14(2), pages 179-198, December.

    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:292:y:2020:i:1:d:10.1007_s10479-020-03631-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.