Abstract
In sectorization problems, a large district is split into small ones, usually meeting certain criteria. In this study, at first, two single-objective integer programming models for sectorization are presented. Models contain sector centers and customers, which are known beforehand. Sectors are established by assigning a subset of customers to each center, regarding objective functions like equilibrium and compactness. Pulp and Pyomo libraries available in Python are utilised to solve related benchmarks. The problems are then solved using a genetic algorithm available in Pymoo, which is a library in Python that contains evolutionary algorithms. Furthermore, the multi-objective versions of the models are solved with NSGA-II and RNSGA-II from Pymoo. A comparison is made among solution approaches. Between solvers, Gurobi performs better, while in the case of setting proper parameters and operators the evolutionary algorithm in Pymoo is better in terms of solution time, particularly for larger benchmarks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Teymourifar, A., Rodrigues, A.M., Ferreira, J.S.: A comparison between simultaneous and hierarchical approaches to solve a multi-objective location-routing problem. In: Gentile, C., Stecca, G., Ventura, P. (eds.) Graphs and Combinatorial Optimization: From Theory to Applications. ASS, vol. 5, pp. 251–263. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-63072-0_20
Teymourifar, A., Rodrigues, A.M., Ferreira, J.S.: A comparison between NSGA-II and NSGA-III to solve multi-objective sectorization problems based on statistical parameter tuning. In: 2020 24th International Conference on Circuits, Systems, Communications and Computers (CSCC), pp. 64–74. IEEE (2020)
Teymourifar, A., Rodrigues, A.M., Ferreira, J.S., Lopes, C., Oliveira, C., Romanciuc, V.: A two-stage method to solve location-routing problems based on sectorization. In: Machado, J., Soares, F., Trojanowska, J., Ivanov, V. (eds.) icieng 2021. LNME, pp. 148–159. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-78170-5_14
Teymourifar, A., Rodrigues, A.M., Ferreira, J.S.: A new model for location-allocation problem based on sectorization. Eng. World 3, 92–96 (2021)
Rodrigues, A.M., Ferreira, J.S.: Measures in sectorization problems. In: Barbosa Póvoa, A.P.F.D., de Miranda, J.L. (eds.) Operations Research and Big Data. SBD, vol. 15, pp. 203–211. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24154-8_24
Rodrigues, A.M., Ferreira, J.S.: Sectors and routes in solid waste collection. In: Almeida, J.P., Oliveira, J.F., Pinto, A.A. (eds.) Operational Research. CSMS, vol. 4, pp. 353–375. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20328-7_20
Treimuth, T.: Dynamic optimization of airspace sector grouping. Ph.D. thesis (2018)
Ríos-Mercado, R.Z., López-Pérez, J.F.: Commercial territory design planning with realignment and disjoint assignment requirements. Omega 41(3), 525–535 (2013)
Bergey, P.K., Ragsdale, C.T., Hoskote, M.: A decision support system for the electrical power districting problem. Decis. Support Syst. 36(1), 1–17 (2003)
Shan, Y., Bettinger, P., Cieszewski, C.J., Li, R.T.: Trends in spatial forest planning. Mathe. Comput. For. Nat. Resource Sci. (MCFNS) 1(2), 86–112 (2009)
Emiliano, W., Telhada, J., do Sameiro Carvalho, M.: Home health care logistics planning: a review and framework. Procedia Manufact. 13, 948–955 (2017)
Farughi, H., Mostafayi, S., Arkat, J.: Healthcare districting optimization using gray wolf optimizer and ant lion optimizer algorithms (case study: South Khorasan healthcare system in Iran). J. Optim. Ind. Eng. 12(1), 119–131 (2019)
Lei, H., Laporte, G., Liu, Y., Zhang, T.: Dynamic design of sales territories. Comput. Oper. Res. 56, 84–92 (2015)
Ríos-Mercado, R.Z., Fernández, E.: A reactive grasp for a commercial territory design problem with multiple balancing requirements. Comput. Oper. Res. 36(3), 755–776 (2009)
Caro, F., Shirabe, T., Guignard, M., Weintraub, A.: School redistricting: embedding GIS tools with integer programming. J. Oper. Res. Soc. 55(8), 836–849 (2004)
Lin, M., Chin, K.S., Ma, L., Tsui, K.L.: A comprehensive multi-objective mixed integer nonlinear programming model for an integrated elderly care service districting problem. Ann. Oper. Res., 1–31 (2018)
Dugošija, D., Savić, A., Maksimović, Z.: A new integer linear programming formulation for the problem of political districting. Ann. Oper. Res., 1–17 (2020)
Ricca, F., Scozzari, A., Simeone, B.: Political districting: from classical models to recent approaches. Ann. Oper. Res. 204(1), 271–299 (2013)
Kalcsics, J., Nickel, S., Schröder, M.: Towards a unified territorial design approach—applications, algorithms and GIS integration. TOP 13(1), 1–56 (2005)
Romanciuc, V., et al.: An integer programming approach to sectorization with compactness and equilibrium constraints. In: Machado, J., Soares, F., Trojanowska, J., Ivanov, V. (eds.) icieng 2021. LNME, pp. 185–196. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-78170-5_17
Blank, J., Deb, K.: pymoo: multi-objective optimization in Python. IEEE Access 8, 89497–89509 (2020)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Teymourifar, A., Ozturk, G., Bahadir, O.: A comparison between two modified NSGA-II algorithms for solving the multi-objective flexible job shop scheduling problem. Univ. J. Appl. Math. 6(3), 79–93 (2018)
Deb, K., Sundar, J.: Reference point based multi-objective optimization using evolutionary algorithms. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp. 635–642 (2006)
pymoo: Multi-objective Optimization in Python. http://pymoo.org/. Accessed July 2021
Acknowledgements
Financial support from Fundação para a Ciência e Tecnologia (through project UIDB/00731/2020) is gratefully acknowledged.
This work is financed by the ERDF - European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme and by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia within project POCI-01-0145-FEDER-031671.
The authors would like to thank the editor and the anonymous referees for their valuable comments which helped to significantly improve the manuscript. They also express gratitude to Julian Blank for his support about the Pymoo library of Python.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Teymourifar, A., Rodrigues, A.M., Ferreira, J., Lopes, C. (2022). A Comparison Between Optimization Tools to Solve Sectorization Problem. In: Le Thi, H.A., Pham Dinh, T., Le, H.M. (eds) Modelling, Computation and Optimization in Information Systems and Management Sciences. MCO 2021. Lecture Notes in Networks and Systems, vol 363. Springer, Cham. https://doi.org/10.1007/978-3-030-92666-3_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-92666-3_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92665-6
Online ISBN: 978-3-030-92666-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)