Multi-objective optimization of population partitioning problem under interval uncertainty

Document Type : Research Paper

Authors

1 Industrial Engineering Department, Yazd University, Yazd, Iran

2 Birjand University of Technology, birjand , Iran

Abstract

This paper addresses a bi-objective mixed integer optimization model under uncertainty for population partitioning problem. The objective functions are to minimize the number of communications between partitions and to balance their population. The main constraints are defined for creating contiguous and compact partitions as well as assigning uniquely each basic unit to one partition. To deal with the uncertainty of parameters, a robust programming method is proposed that causes the uncertainty parameters lie between the interval of best-case (the deterministic mode) and worst-case (the highest uncertainty level for all parameters). As the suggested method is NP-Hard, three meta-heuristic algorithms NSGAII, PESA, and SPEA are developed and, to evaluate the efficiency of the algorithms, 10 small-size examples, 10 medium-size examples and, 10 large-size examples are generated and solved. According to computational results, the SPEA has the best performance. The method is examined for a real-world application, as a case study in Iran.

Keywords

Main Subjects

References

Baños, R., Gil, C., Paechter, B., & Ortega, J. (2007). A hybrid meta-heuristic for multi-objective optimization: MOSATS. Journal of Mathematical Modelling and Algorithms, 6(2), 213-230.
Baqir, R. (2002). Districting and government overspending. Journal of political Economy, 110(6), 1318-1354.
Benzarti, E., Sahin, E., & Dallery, Y. (2013). Operations management applied to home care services: Analysis of the districting problem. Decision Support Systems, 55(2), 587-598.
Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35-53.
Bertsimas, D., & Sim, M. J. M. p. (2003). Robust discrete optimization and network flows. 98(1-3), 49-71.
Bozkaya, B., Erkut, E., & Laporte, G. (2003). A tabu search heuristic and adaptive memory procedure for political districting. European Journal of Operational Research, 144(1), 12-26.
Brooks, S. P., & Morgan, B. J. (1995). Optimization using simulated annealing. Journal of the Royal Statistical Society: Series D (The Statistician), 44(2), 241-257.
Butsch, A., Kalcsics, J., & Laporte, G. (2014). Districting for arc routing. INFORMS Journal on Computing, 26(4), 809-824.
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, 246(2), 674-684.
Chen, X., & Yum, T.-S. P. (2010). Patrol districting and routing with security level functions. Paper presented at the 2010 IEEE International Conference on Systems, Man and Cybernetics.
Corne, D. W., Jerram, N. R., Knowles, J. D., & Oates, M. J. (2001). PESA-II: Region-based selection in evolutionary multiobjective optimization. Paper presented at the Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation.
Datta, D., Figueira, J., Gourtani, A., & Morton, A. (2013). Optimal administrative geographies: an algorithmic approach. Socio-Economic Planning Sciences, 47(3), 247-257.
Datta, D., & Figueira, J. R. (2011). Graph partitioning by multi-objective real-valued metaheuristics: A comparative study. Applied Soft Computing, 11(5), 3976-3987.
De Assis, L. S., Franca, P. M., & Usberti, F. L. (2014). A redistricting problem applied to meter reading in power distribution networks. Computers & Operations Research, 41, 65-75.
Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. Paper presented at the International Conference on Parallel Problem Solving From Nature.
Fan, N., Zheng, Q. P., & Pardalos, P. M. (2012). Robust optimization of graph partitioning involving interval uncertainty. Theoretical Computer Science, 447, 53-61.
García‐Ayala, G., González‐Velarde, J. L., Ríos‐Mercado, R. Z., & Fernández, E. (2016). A novel model for arc territory design: promoting Eulerian districts. International Transactions in Operational Research, 23(3), 433-458.
Garfinkel, R. S., & Nemhauser, G. L. (1970). Optimal political districting by implicit enumeration techniques. Management Science, 16(8), B-495-B-508.
Ghiggi, C., Puliafito, P. P., & Zoppoli, R. (1975). A combinatorial method for health-care districting. Paper presented at the IFIP Technical Conference on Optimization Techniques.
Kong, Y., Zhu, Y., & Wang, Y. (2018). A center-based modeling approach to solve the districting problem. International Journal of Geographical Information Science, 1-17.
Li, W., Church, R. L., & Goodchild, M. F. (2014). An extendable heuristic framework to solve the p-compact-regions problem for urban economic modeling. Computers, Environment and Urban Systems, 43, 1-13.
Liberatore, F., & Camacho-Collados, M. (2016). A comparison of local search methods for the multicriteria police districting problem on graph. Mathematical Problems in Engineering, 2016.
Lin, H.-Y., & Kao, J.-J. (2008). Subregion districting analysis for municipal solid waste collection privatization. Journal of the Air & Waste Management Association, 58(1), 104-111.
Lin, M., Chin, K.-S., Fu, C., & Tsui, K.-L. (2017). An effective greedy method for the Meals-On-Wheels service districting problem. Computers & Industrial Engineering, 106, 1-19.
Maghsoudlou, H., Kahag, M. R., Niaki, S. T. A., & Pourvaziri, H. (2016). Bi-objective optimization of a three-echelon multi-server supply-chain problem in congested systems: Modeling and solution. Computers & Industrial Engineering, 99, 41-62.
Minciardi, R., Puliafito, P., & Zoppoli, R. (1981). A districting procedure for social organizations. European Journal of Operational Research, 8(1), 47-57.
Pezzella, F., Bonanno, R., & Nicoletti, B. (1981). A system approach to the optimal health-care districting. European Journal of Operational Research, 8(2), 139-146.
Ríos-Mercado, R. Z., & López-Pérez, J. F. (2013). Commercial territory design planning with realignment and disjoint assignment requirements. Omega, 41(3), 525-535.
Samadi, A., Mehranfar, N., Fathollahi Fard, A., & Hajiaghaei-Keshteli, M. (2018). Heuristic-based metaheuristics to address a sustainable supply chain network design problem. Journal of Industrial and Production Engineering, 35(2), 102-117.
Shirabe, T. (2012). Prescriptive modeling with map algebra for multi-zone allocation with size constraints. Computers, Environment and Urban Systems, 36(5), 456-469.
Steiner, M. T. A., Datta, D., Neto, P. J. S., Scarpin, C. T., & Figueira, J. R. (2015). Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil. Omega, 52, 53-64.
Tran, T.-C., Dinh, T. B., & Gascon, V. (2017). Meta-heuristics to Solve a Districting Problem of a Public Medical Clinic. Paper presented at the Proceedings of the Eighth International Symposium on Information and Communication Technology.
Wang, T., Wu, Z., & Mao, J. (2007). A new method for multi-objective tdma scheduling in wireless sensor networks using pareto-based pso and fuzzy comprehensive judgement. Paper presented at the International Conference on High Performance Computing and Communications.
Zhao, J., Wang, D., & Peng, Q. (2018). Optimizing the Train Dispatcher Desk Districting Problem in High-Speed Railway Network (No. 18-03607).
Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-report, 103. 
Journal of Industrial and Systems Engineering
Volume 12, Issue 4 - Serial Number 4
November 2019
Pages 172-197

Files

History

  • Receive Date: 06 July 2020
  • Revise Date: 25 January 2020
  • Accept Date: 29 January 2020

Share

How to cite

Statistics