双权重应急交通网络最优路径数学模型及算法研究

摘要

The graph theory and multi-objective optimization method were used to build a mathematical model for route selection in emergency network with double weights and a fast approximation algorithm was proposed to calculate it based on hyper-heuristic methodology. Several low-level heuristics were applied to get new heuristic algorithm and provide problem solving strategy for emergency decision-makers. Application effect of the designed algorithm in emergency management and decision-making was tested and compared with A* algorithm in a road map. A simulation was performed in different parameter settings ofc,b, n,δ1andδ2. The results show that the former has advantages on path optimization in an emergency network with double road-weights. The efficiency of the algorithm has a significant positive correlation with these parameters ofn,δ1andδ2, but not withcandb, and the proposed algorithm has a high efficiency which can provides powerful technical support for emergency decision and a strong powerful technical support for emergency relief and evacuation.%运用运筹学中的图论与多目标优化理论和方法建立双权重应急交通网络最优路径的数学模型，基于超启发式算法思想，提出适合该模型的双试探点搜索算法。算法从应急决策的角度寻找最优路径，通过操纵和管理低层启发式算法，不断获得新启发式算法，是一种快速、近似的算法。用真实路网验证本文算法在应急管理与决策中的应用效果，并与A*算法进行对比分析，证明前者在双权重应急交通网络的路径寻优上更具优势。此外，用随机路网测试不同限制条件参数c和b以及节点规模n，研究算法精度参数δ1及δ2对双试探点搜索算法求解效率的影响。研究结果表明：所提出的算法求解效率与n及算法流程参数δ1和δ2有显著的正相关关系，而与限制条件参数c和b之间的相关性并不显著，算法有较高的求解效率，为突发事件救灾与疏散提供了有力的技术支持。