1.Merchant Marine College, Shanghai Maritime University, Shanghai 201306, China 2.Marine College, Shandong Transport Vocational College, Weifang 261206, China 3.Weifang University of Science and Technology, Weifang 262700, China
Abstract:With the improvement of people's living standards, large-scaled public activities have increased considerably, and the emergency probability has increased greatly. When an emergency occurs, the emergency evacuation can effectively reduce casualties and economic losses. Therefore, how to quickly evacuate crowd is a current research hotspot in this field. The path planning of emergency evacuation is one of the effective ways to implement the crowd evacuation. Aiming at the problem of path planning for emergency evacuation and taking the grid map as the background, the ant colony cellular optimization (ACCO) algorithm is proposed as the path planning algorithm based on the cellular automata theory and ant colony algorithm. Firstly, in order to solve the problem of inconsistent time steps in the quadrilateral grid map, the grid map based on hexagonal cell is established and the ACCO algorithm is developed based on the hexagonal grid map. And the method of solving grid coordinate is given. Then, in order to improve the convergence speed and search ability of the ACCO algorithm, the static field is used to optimize the heuristic function, and the segment update rule is used to optimize the pheromone update method. Finally, the parameters of ACCO algorithm are optimized through the particle swarm optimization (PSO) algorithm. The method of designing the fitness evaluation function is proposed, and the optimal combination of parameters of the ACCO algorithm is implemented according to the fitness function. In order to verify the scientificity and effectiveness of the algorithm proposed in this research and also to systematically verify the optimization strategy, in this research the exhibition hall on the B-deck of a large cruise ship is used as the engineering background, and the traditional algorithm and the ACCO algorithm are adopted to perform the simulations. The simulation results show that compared with the traditional quadrilateral grid, the hexagonal grid proposed in this research unifies the simulation time step and can be used as the division method of the simulation environment. At the same time, the ACCO algorithm can effectively perform the evacuation path planning, and the optimization strategy proposed in this research not only acceletates the search speed, but also increases the solution space and improves the search ability, which can effectively avoid falling into the local optimal solution. Keywords:path planning/ population evacuation/ ant colony cellular optimization/ partical swarm optimization
$\begin{split}& { {{F}_{i}}\left( x \right)={{\lambda }_{1}}{{L}_{i}}\left( x \right)+{{\lambda }_{2}}{{S}_{i}}\left( x \right)+{{\lambda }_{3}}{{Q}_{i}}\left( x \right)-{{\lambda }_{4}}{{T}_{i}}\left( x \right),}\\& {{{L}_{i}}\left( x \right)= {1}/{\left( {{L}_{\rm{best}}}+1 \right)}\;,}\\& {{{S}_{i}}\left( x \right)={{\rm{e}}^{{}{-{{N}_{\rm{best}}}}/{{{N}_{\rm{max}}}}\;}},}\\& {{{Q}_{i}}\left( x \right)= {1}/{}{{{L}_{\rm{std}}}}\;,}\\& {{{T}_{i}}\left( x \right)=~{{\rm{e}}^{1-{}{1}/{}{\rm{Dis}}\;}},}\end{split}$
其中${F_i}\left( x \right)$为第i个粒子代表的参数所对应的适应度函数值; λ1, λ2, λ3, λ4为权重系数, 且满足λ1 + λ2 + λ3 + λ4 = 1; ${L_i}\left( x \right)$是使用粒子i运算所得的参数, 表示ACCO算法搜索最优路径的能力; Lbest表示每次PSO迭代所得到的最优路径的元胞数量; ${S_i}\left( x \right)$是使用粒子i运算所得的参数, 表征ACCO算法的收敛速度; Nbest为ACCO算法搜索到当前最优路径时自身的迭代次数; Nmax为元胞蚂蚁的最大迭代次数; ${Q_i}\left( x \right)$是使用粒子i运算所得的参数, 表示ACCO算法的稳定性; Lstd为每次PSO迭代过程中, 表征ACCO算法搜索到的路径的方差; ${T_i}\left( x \right)$表示使用粒子i运算所得的参数, 表征ACCO算法的运行时间; Dis表示元每次PSO迭代过程中ACCO算法搜索路径总和. 23.4.路径规划流程 -->
当最大迭代次数一定时, 由于传统算法与ACCO算法在路径选择概率上的差异, 导致每次迭代所有蚂蚁搜寻的总路径长度和搜索速度也不同, 其结果如图7所示. 图 7 路径长度对比 (a) 传统算法路径统计; (b) 基于经验参数的ACCO算法路径统计; (c) 启发函数优化后的路径统计; (d) 信息素更新优化的路径统计; (e) 基于参数组1的路径统计; (f) 基于参数组2的路径统计 Figure7. Path length comparison: (a) The path statistics for traditional algorithm; (b) the path statistics for ACCO algorithm with experience; (c) the path statistics for only optimizing heuristic function; (d) the path statistics for only optimizing pheromone update methods; (e) the path statistics for parameter group 1; (f) the path statistics for parameter group 2.