An iterative local search based hybrid algorithm for the service area problem

Abstract

This article presents a hybrid algorithm for the service area problem. The design of service areas is one of the essential issues in providing efficient services in both the public and private sectors. For a geographical region with a number of small spatial units, the service area problem is to assign the service-demand units to the service-supply units such that each facility has a service area. The basic criteria for the service areas are the highest service accessibility, the contiguous service areas, and that the service demand does not exceed the service supply in each service area. A hybrid algorithm for the service area problem is proposed by extending iterative local search (ILS) algorithm with three schemes: population-based ILS, variable neighborhood descent (VND) search, and set partitioning. The performance of the algorithm was tested using 60 well-designed instances. Experimentation showed that the instances could be solved effectively and efficiently. The solutions found by the hybrid algorithm approximate optimal solutions or the lower bounds with an average gap of 0.15%.

Keywords

Service area problem / Hybrid algorithm / Local search / Set partitioning

References

[1] BacaoF, LoboV, PainhoM. Applying genetic algorithms to zone design. Soft Computing, 2005, 9(5):341-348

[2] BergeyPK, RagsdaleCT, HoskoteM. A simulated annealing genetic algorithm for the electrical power districting problem. Annals of Operations Research, 2003, 121(1):33-55

[3] ButschA, KalcsicsJ, LaporteG. Districting for arc routing. INFORMS Journal on Computing, 2014, 26(4):809-824

[4] CaroF, ShirabeT, GuignardM, WeintraubA. School redistricting: Embedding GIS tools with integer programming. Journal of the Operational Research Society, 2004, 55(8):836-849

[5] ChouC. A knowledge-based evolution algorithm approach to political districting problem. Computer Physics Communications, 2011, 182(1):209-212

[6] ChouC, ChuY, LiS. Evolutionary strategy for political districting problem using genetic algorithm. Lecture Notes in Computer Science, 2007, 4490(4):1163-1166

[7] Daskin, M. S. (2011). Location and Districting Problems in Services. In Service science (pp. 183–283). Wiley.

[8] DattaD, et al.. Graph partitioning through a multi-objective evolutionary algorithm: a preliminary study. Proceedings of the 10th annual conference on Genetic and evolutionary computation, 2008 625-632

[9] DuqueJC, ChurchRL, MiddletonRS. The p-regions problem. Geographical Analysis, 2011, 43(1):104-126

[10] EmilianoWM, TelhadaJ, CarvalhoMD. Home health care logistics planning: A review and framework. Procedia Manufacturing, 2017, 13: 948-955

[11] FerlandJA, GuenetteG. Decision support system for the school districting problem. Operations Research, 1990, 38(1):15-21

[12] FormanSL, YueY. Congressional districting using a TSP-based genetic algorithm. Lecture Notes on Computer Science, 2003, 2724: 2072-2083

[13] FranklinAD, KoenigsbergE. Computed school assignments in a large district. Operations Research, 1973, 21(2):413-426

[14] GarfinkelRS, NemhauserGL. Optimal political districting by implicit enumeration techniques. Management Science, 1970, 16(8):495-508

[15] GeorgeJA, LamarBW, WallaceCA. Political district determination using large-scale network optimization. Socioeconomic Planning Science, 1997, 31(1):11-28

[16] HessSW, WeaverJB, SiegfeldtHJ, WhelanJN, ZitlauPA. Nonpartisan political redistricting by computer. Operations Research, 1965, 13(6):998-1006

[17] HojatiM. Optimal political districting. Computers & Operations Research, 1996, 23(12):1147-1161

[18] HuF, YangS, XuW. A non-dominated sorting genetic algorithm for the location and districting planning of earthquake shelters. International Journal of Geographical Information Science, 2014, 28(7):1482-1501

[19] HuY, WangF, XieraliI. Automated delineation of hospital service areas and hospital referral regions by modularity optimization. Health Services Research, 2018, 53(1):236-255

[20] JacobsDA, SilanMN, ClemsonB. An analysis of alternative locations and service areas of American red cross blood facilities. Interfaces, 1996, 26(3):40-50

[21] KalcsicsJ, NickelS, SchroderM. Towards a unified territorial design approach: Applications, algorithms and GIS integration. Top, 2005, 13(1):1-56

[22] KoenigsbergE. Mathematical analysis applied to school attendance areas. Socio-Economic Planning Sciences, 1968, 1(4):465-475

[23] KongY, ZhuY, WangY. A hybrid metaheuristic algorithm for the school districting problem. Acta Geographica Sinica, 2017, 72(2):256-268 (in Chinese)

[24] KongY, ZhuY, WangY. A center-based modeling approach to solve the districting problem. International Journal of Geographical Information Science, 2019, 33(2):368-384

[25] LiX, ClaramuntC, KungHT, GuoZ, WuJ. A decentralized and continuity-based algorithm for delineating capacitated shelters’ service areas. Environment and Planning B: Planning and Design, 2008, 35(4):593-608

[26] Li, Z., Wang, R., & Wang, Y. (2007). A quadratic programming model for political districting problem. In X. Zhang, L. Chen, L. Wu, et al. (Eds.), The First International Symposium on Optimization and Systems Biology (OSB’07) (pp. 427–435). World Publishing Corporation.

[27] LiberatoreF, CamachocolladosM. A comparison of local search methods for the multicriteria police districting problem on graph. Mathematical Problems in Engineering, 2016, Article ID 3690474: 13

[28] LiuY, ChoWK, WangS. PEAR: A massively parallel evolutionary computation approach for political redistricting optimization and analysis. Swarm and Evolutionary Computation, 2016, 30: 78-92

[29] Lodi, A. (2017). On mixed-integer programming and its connection with data science [online]. EPFL Available from: http://transp-or.epfl.ch/zinal/lectures2017.php [Accessed 5 Apr 2018].

[30] Lourenço, H. R., Martin, O., & Stützle, T. (2010). Iterated local search: Framework and applications. In M. Gendreau & J. Y. Potvin (Eds.), Handbook of metaheuristics, International series in operations research & management science (Vol. 146, 2nd ed., pp. 363–397). Springer. https://doi.org/10.1007/978-1-4419-1665-5_12.

[31] MehrotraA, JohnsonEL, NemhauserGL. An optimization based heuristic for political districting. Management Science, 1998, 44(8):1100-1114

[32] NemotoT, HottaK. Modelling and solution of the problem of optimal electoral districting. Communications of Operations Research of Japan, 2003, 48(4):300-306 (in Japanese)

[33] NygreenB. European assembly constituencies for Wales—Comparing of methods for solving a political districting problem. Mathematical Programming, 1988, 42(1):159-169

[34] PezzellaF, BonannoR, NicolettiB. A system approach to the optimal health-care districting. European Journal of Operational Research, 1981, 8(2):139-146

[35] PlaneDA, TongD, LeiT. Inter-person separation: A new objective standard for evaluating the spatial fairness of political redistricting plans. Geographical Analysis, 2019, 51(3):251-279

[36] RiccaF, SimeoneB. Local search algorithms for political districting. European Journal of Operational Research, 2008, 189(3):1409-1426

[37] Rincón-García, E. A., et al. (2015). ABC, a viable algorithm for the political districting problem. In J. Gil-Aluja et al. (Eds.), Scientific methods for the treatment of uncertainty in social sciences. Advances in intelligent systems and computing (Vol. 377). Springer.

[38] Ríos-MercadoRZ, FernandezE. A reactive GRASP for a commercial territory design problem with multiple balancing requirements. Computers & Operations Research, 2009, 36(3):755-776

[39] Salazar-AguilarMA, Ríos-MercadoRZ, González-VelardeJL, MolinaJ. Multiobjective scatter search for a commercial territory design problem. Annals of Operations Research, 2012, 199(1):343-360

[40] Salazar-AguilarMA, Ríos-MercadoRZ, Gonzalez-VerlardeJL. A bi-objective programming model for designing compact and balanced territories in commercial districting. Transportation Research Part C: Emerging Technologies, 2011, 19(5):885-895

[41] SchoepfleOB, ChurchRL. A new network representation of a “classic” school districting problem. Socio-Economic Planning Sciences, 1991, 25(3):189-197

[42] ShirabeT. A model of contiguity for spatial unit allocation. Geographical Analysis, 2005, 37(1):2-16

[43] TavarespereiraF, et al.. Multiple criteria districting problems. Annals of Operations Research, 2007, 154(1):69-92

[44] WangY, KongY. An algorithm framework for facility service districting problem. Geomatics and Information Science of Wuhan University, 2021, 46(5):726-735 (in Chinses)

[45] XiaoN. A unified conceptual framework for geographical optimization using evolutionary algorithms. Annals of the Association of American Geographers, 2008, 98(4):795-817

[46] YanikS, SurerO, OztaysiB. Designing sustainable energy regions using genetic algorithms and location-allocation approach. Energy, 2016, 97: 161-172