Location and path planning for urban emergency rescue by a hybrid clustering and ant colony algorithm approach

Rescue station setup and rescue path planning are two important tasks in urban emergency rescue. The former task ensures rescue response capability and the latter task provides effective rescue solutions. When emergencies occur in cities, evacuees are distributed along the urban road network. Rescue resources refer to rescue vehicles whose available number and capacity are both limited. With the constraints of rescue resources and the number of rescues, this paper aims to simultaneously optimize the tasks of rescue station setup and rescue path planning. In the addressed scenario, the priority of each evacuee is quantified as a weight value that is used as the main optimization objective. To solve the problem, a comprehensive urban emergency rescue planning approach is proposed. The proposed approach consists of components of road network processing, road network weight calculation, rescue station setup and rescue path planning. For the setup of rescue stations, this paper employs a clustering method to provide a set of high-quality candidate rescue stations for subsequent path planning based on the locations of evacuees and the road network structure. For rescue path planning, an improved ant colony optimization algorithm is developed. The proposed method is called the planning algorithm with clustering and improved ant colony optimization (PA-C-IACO). The proposed PA-C-IACO redefines the degree of heuristic and pheromone concentration increments for transfer between intersections in the ant colony algorithm and incorporates a reward mechanism during the pheromone update process. Experimental results on six different size datasets show that PA-C-IACO outperforms state-of-the-art algorithms and shows good robustness and feasibility.