刘浩翰，郭晶晶，李建伏，贺怀清

(中国民航大学 计算机科学与技术学院，天津 300300)(*通信作者电子邮箱peony_g@163.com)

0 引言

目前很多研究领域的问题都可以归结为多目标最短路径问题，例如，车道规划、城市交通网络、机器人监控、卫星定位、路由通信网络等。

多目标最短路径问题是根据多个目标在图中找到起始节点到一个目的节点(一对一问题)或图中的多个节点(一对多问题)的所有帕累托(Pareto)最优解的集合。学者们提出了几种解决该问题的方法，包括枚举方法(标签设置[1]和标签校正[2])、排序算法[3]和两阶段算法[4]。在大规模图中，寻找任意给定的起始节点和目的节点间的最短路径(一对一的问题，例如路线图中的导航查询)，标签设置算法通常是最佳的选择。通常情况下，多目标标签设置算法是在单目标算法，如Dijkstra算法和A*算法[5]基础上改进的。在一对一问题中A*算法作为Dijkstra算法的变体，通过使用启发函数来提高搜索效率。如果启发函数值满足下界条件，则A*算法是一种精确的算法，即它总是返回一个最优解。极端情况下，如果启发函数值等于0，A*算法等同于Dijkstra算法。

1 相关知识

1.1 多目标A*算法

多目标A*算法描述如下：G=(N,A,c)用于表示描述搜索空间的有向图。其中：N表示节点，A表示两节点之间的有向弧，c表示标志有向弧的多目标代价向量，每一维代表一个目标。在G上任意指定起始节点s∈N，目的节点t∈N，寻找两节点间的非支配路径P=(n1,n2,…,nk)，代价向量c(P)可以通过路径的子部分的代价向量求和得到。多目标A*算法用到的部分重要定义如下。……