Applying Scatter Search Algorithm To Capacitated P-Median Problem In Facility Location Allocation

Facility location problems, which can be divided into three kinds or more, covering problem,p-center problem,p-median problem, etc. according to classical location theory, are frequently encountered in urban planning. Each kind of problems may contain many variations of different constraints or different objective functions. In this paper, we take capacitated p-median problem as research issue. Firstly, the paper summarizes shortcomings of existing methods in solving capacitated p-median problems. Then, the paper proposes an improved heuristic algorithm, scatter search algorithm (SS), to solve capacitated p-median problem maintaining the continuity of service area of facilities. Finally, the paper applies the proposed algorithm to the Shanghai shelter location problem.The p-median problem is to select a group of p facilities to ensure the average weighted distance (or time) of demand points to facilities is shortest. Capacitated p-median problem (CPMP) is a kind of p-median problem in which each demand unit has definite demand and each facility has definite service capacity. Currently, many heuristic algorithms, such as genetic algorithms, simulated annealing algorithms and scatter search algorithms, etc., are raised by many domestic and foreign scholars to solve CPMP. Based on them, and considering uneven distribution of demand units and continuity of service area of facilities, we proposed a novel scatter search algorithm. The algorithm is improved as follows. Firstly, shift-insertion algorithm is combined to assign demand unit to ensure the continuity of service area of facilities. Secondly, neighborhood search tactics is substituted by adjacent rectangle tactics to improve the speed of neighborhood search. Thirdly, path re-linking algorithm is integrated solution combination method in scatter search algorithm. The paper validates the proposed improved algorithm from several aspects, such as computation speed, continuity of demand units, and capacity limits of facilities, etc., by two groups of experiments.In our experiments, traffic analysis zone, road network distance are considered as demand unit, distance measuring method, respectively, and several scenarios of shelter location problem are demonstrated. Based on a certain facility location result, shortest paths of all road junctions in the road network are computed, and characteristics of personnel evacuation are analyzed.