Comparison of Spatially Guided Tabu Search and Nested Genetic Algorithms for Solving the Capacitated Location-Allocation Problem in Emergency Situations

Severe earthquakes cause a lot of human and financial damage, which was prevented from occurring after the accident with quick and timely relief. One of the important problems in this field is the optimal allocation of injured to medical centers, and these problems have a dynamic and complex nature and cannot be solved by simple methods. The use of geographic information systems (GIS) along with optimization and simulation methods makes it possible to find a method for optimally allocating injured to medical centers. The problem of allocation of earthquake-related injured to medical centers is in the category of capacity allocation problems, and in this type of problems, with the increase in the number of demand points and service centers, the complexity and volume of the problem calculations increases exponentially, so in many cases, it is not It is possible to use direct and definite search methods in solving this type of problems, and appropriate innovative methods should be used to solve them optimally.On the other hand, because data plays an important role in allocating injured to medical centers, it is possible to move towards a better and simpler solution by integrating and combining the spatial information system with optimization methods.

In this study, it is assumed that in the event of an earthquake in a number of building blocks, a number of people living in them will be injured and need help, and the locations of this injured population are the demand points. In this way, these injured should be sent to medical centers, each of which has the ability to provide services to a certain number of these injured. The next parameter is the number of medical centers and their capacity to provide medical services. In this research, the capacity of medical centers is assumed to be less than the number of injured people. Finally, by optimizing the objective function, a ratio of injured people at different points that should be accepted by existing or new treatment centers is calculated using a nested genetic algorithm. The output of the genetic algorithm that determines the location of the new centers is combined with the existing information, which is the location of the existing centers, and then it is used as the input parameters of the spatially guided tabu search (SGTS) algorithm to determine the best allocation.

In order to assess the accuracy of the genetic algorithm and SGTS method, the standard deviation, accuracy, and processing time have been evaluated, which SGTS method has performed better in all three assessment. The results show that the standard deviation ratio of the proposed method compared to the genetic algorithm is 0.12, and the average accuracy of SGTS method has improved by 18% on average compared to the genetic algorithm. Also, the SGTS method performed calculations 7% faster.

By comparing the processing time to optimally solve the problem of earthquake-related injured allocation to medical centers, it can be concluded that SGTS method can reach convergence in a shorter period of time. Therefore, creating a selection list using the structure provided based on spatial analysis can be effective in this field. The SGTS method is more accurate than the genetic algorithm, and the results obtained from this method are robust. For solving the capacitated location-allocation problem, if the objective of optimization is locating and allocating, then combined algorithms are recommended for optimally solving both. Although this study has succeeded to propose a combination method for the optimal solution of the capacitated location-allocation problem, it is recommended to conduct the combination of meta-heuristic methods and compare the results with the proposed method.