郭展羽，张志明，贺兰山，郑家齐，赵师兵，康 琦

同济大学 电子与信息工程学院，上海200092

最短路径问题一直是运筹学、计算机科学、地理信息科学、交通运输等领域的研究热点，并广泛应用到公共交通运输网络规划、无人自动驾驶、机器人自主导航等的实际问题中[1-6]。现实生活里有许多问题都可以抽象转化为最短路径问题，路径规划要求根据某种优化准则，在给定的真实环境中寻找到一条从起始位置到目标位置可行并且代价最小的路径。研究如何有效地计算和求解最短路径问题，其面临的难点是如何在较短的时间内找到较为完备的解。根据对环境信息的掌握程度不同，路径规划可分为全局路径规划和局部路径规划，两者没有本质上的区别。经典的全局路径规划算法有Dijkstra算法[7]和A*算法[8]等，可以静态地规划出最优或次优路线。近年来，国内外学者在此基础上，引入启发式算法和仿生算法等，提出多种最短路径改进算法[9-16]，如模拟退火法、蚁群算法、遗传算法、粒子群算法、深度优先算法和广度优先算法等，并在解决过必经点集的最短路径问题上已经取得很好的成效，康文雄等人[9]通过分层回溯的Dijkstra 算法，有效地减少问题求解的计算时间；Daniele 等人[10]对约束最短路径漫游问题（constrained shortest path tour problem，CSPTP）提出新的数学模型和高效的分支定界方法；王磊等人[14]使用改进的A*算法，对最短路径段进行拼接，使运算效率得到显著提高。

在探究路径规划算法的过程中，应用场景……