基于路段赋值的多目标最短路算法研究

冯树民，王宪凯，孙祥龙

(1. 哈尔滨工业大学 交通科学与工程学院，黑龙江 哈尔滨 150090； 2. 东北林业大学 土木工程学院，黑龙江 哈尔滨 150040)

0 引 言

多目标最短路问题(multi-objective shortest path problem, MOSPP)在最优化、运输路线设计、通信网络设计等领域被广泛研究[1-3]。解决多目标最短路问题的关键在于寻找满足多个目标的有效路径集合，而这些目标之间一般相互冲突。例如，通信网络中最优线路要兼顾延迟最小、交换量最大两个矛盾目标；运输路线规划中要同时满足成本、路径长度、旅行时间3个目标最小化。不同于单目标优化问题中求解一个目标函数的最优解，多目标优化的任务不是找到每个目标函数的最优解，而是找到一个同时满足所有目标的最优解。往往在大多数情况下，这个全局的最优解并不存在，一般只有一个有效解或非劣解的集合。

多目标最短路问题的处理方法一般可分为交互法、产生法和权重法[4]。交互法可以通过一个用户界面得到完整的有效路径集合，帮助决策者根据自身偏好找出最终解[5-6]。产生法是大量列举有效解，然后根据实际情况和决策者偏好选择满意解[7-10]。权重法是根据不同目标函数的重要程度，赋予其一定的权值来求解多目标最短路问题，常用方法是线性加权法和几何加权法[11-12]。相比而言，对不同的目标进行加权将多目标问题转化为单目标问题求解，是一种较好的思路。但是，如何确定权重来体现目标的重要性是权重法的一个难点。

因此，笔者在常规线性加权法和几何加权法的基础上，提出路段赋值法来求解多目标最短路问题。路段赋值法综合考虑每条路线的路段数和距离对路线选择的影响，计算各目标下相应路段的赋值，并依据不同权重进行加权叠加，最终形成赋值网络，在该路段赋值网络中求得的最短路径即为该多目标最短路问题的优选路径。同时，以江西省萍乡市运输网络为例，对常规线性加权法、几何加权法与路段赋值法进行了对比分析。

1 问题描述

多目标最短路问题可以描述为：对于网络G=(N，E)，E为节点间的有向边的集合，N为节点集，fq(i,j)≥0(q=1,2,…,Q)为节点i到节点j的第q个目标值，求解起点O到终点D之间的最短路。

定义变量δij如下：

则多目标最短路模型可表述为式(1)：

(1)

⋮

该模型满足式(2)所述约束条件：

(2)

δij∈{0,1},∀(i,j)∈E

2 算法分析

2.1 多目标优化相关定义

多目标优化问题的最终目的是使多个矛盾的子目标尽可能同时极小化，而多目标最短路问题作为多目标优化的具体案例，可描述为式(3)[13]：

X⊂En,m>2

(3)

与单目标优化问题的解不同，多目标优化一般不存在唯一的全局最优解，而是存在多个最优解的集合。因此，关于多目标最短路的解有如下定义。

2.2 路段赋值法

多目标最短路的线性加权是将多目标函数的各目标按相应的准则加权后以某种方式进行求和，做出评价函数g(f(x))，再对评价函数进行单目标极小化，表达式Pg如式(4)：

(4)

权系数λ的确定，不仅要考虑目标的重要程度，也要考虑目标单位量纲的不同。为了消除单位不同产生的不可公度性，应对不同目标进行标准化。记单一目标下最短路线上的所有路段赋值为1。对于非最短路线上的路段，可赋值为路线距离与最短路距离之比并加以路段个数的修正值，路线距离的比值体现路线距离的重要程度，比值越小越重要；同时为消除路线上路段个数的影响，用最短路线路段个数与比较路线路段个数的比值加以修正，以此保证路段赋值与原路线路段有良好的对应关系。

设最短路线Lmin的路段数为Smin，距离为Dmin，则最短路线上的所有路段赋值都为1，对起讫点之间路线Li，路段数为Si，距离为Di，则该路线上所有路段赋值为ai，表达式见式(5)：

(5)

利用路段赋值后，Pg表达式转换为式(6)中Pg1所述形式：

(6)

如果某路段多次赋值，则选取最小的赋值。在实际应用中，如果网络很大，对每个路段都进行赋值需要的工作量很大，考虑到最优路径一般都是在单目标下的K-最短路中取得[14]，因此先求不同目标下的K-最短路，然后对求得的所有路段进行赋值。

2.3 主要结果

作为农业绿色发展基础的土壤，目前面临着严重的“变质”问题，土壤侵蚀、土壤养分不平衡、土壤中碳和生物多样性丧失、土壤酸化、土壤盐渍化、土壤板结、土壤污染等多种威胁制约着土壤质量的发挥和土壤安全的保障。除自然因素外，土壤污染是导致多重土壤问题的主要原因。汪洪表示，与大气污染和水体污染不同，土壤污染不易被人体直接感受到，需要通过仪器设备的检测才可以感知，具有隐蔽性、滞后性、累积性、成因复杂等特点，也因此易于被公众所忽视。

(7)

(8)

3 算法步骤

在上述分析的基础上，提出基于路段赋值的多目标最短路求解算法，算法的具体步骤如下。

步骤1：运用Dijkstra算法分别求解各目标的最短路径Lmin和最短路距离Dmin；

步骤3：运用K-最短路算法分别求解各目标对应的K-最短路径Li和距离Di；

步骤5：按各目标权重对多目标进行加权叠加，求出最短路径；

步骤6：令K=K+1，转入步骤(3)，若两次所求得的路径相同，则该路径即为多目标最短路问题的满意解，算法结束；否则，继续令K=K+1值，直到前后两次所求得的路径相同为止。

算法流程如图1。

图1 算法流程Fig. 1 Flowchart of algorithm

4 案例分析

江西省萍乡市运输网络如图2，运输网络中每个路段包含3个度量值，分别为运输风险、运输成本和路段拥堵评分。其中，运输风险值越大，表明此路段的运输风险越高；运输成本值越大，表明此路段的运输成本越高；路段拥堵评分用于描述不同路段的拥堵程度，其值介于0～100之间，路段拥堵评分越大表示路段拥堵越严重，具体路段属性详见表1。运输线路的选取属于多目标最短路问题，其中目标1为运输风险最小，目标2为运输成本最小，目标3为路段拥堵评分最小。求解起点20到终点13之间3个目标下的最短路径。

图2 运输网络Fig. 2 Transport network

路段号风险成本拥堵评分路段号风险成本拥堵评分1→278179407→111454371→13162133408→97125701→163454448→193124412→326488→20485792282→12259329→143103572→1519468269→20204862443→4430101210→2055128783→19916282111→1748238533→21112591111→19267134274→5782252311→211 32121464→148082503512→13262159354→15370951012→171 256226205→1462417212→2113227115→1821286913→1754752296→7188108714→19642209276→10787905115→1665162246→177252615→1855313747→822595916→18157316657→101 3164046

只考虑单个目标，求解不同目标下的最短路线和最短路距离，计算结果见表2及图3，从表2及图3中可以看出，在3个不同的目标下，所得结果各不相同，且相差较大。

表2 单目标结果Table 2 Single target result

图3 单目标下各目标的最短路Fig. 3 The shortest path of each target under single objective

将3个目标按照不同的权重λq进行线性加权，求得不同权重下的最优路径见表3和图4，可以看出对于不同的权重系数，最终的最优路径并不相同，但总体上倾向于目标1的最短路。

表3 线性加权法计算结果表Table 3 Calculation results of linear weighting method

图4 线性加权法最短路Fig. 4 The shortest path of linear weighting method

将3个目标按照不同的权重λq进行几何加权，求得不同权重下的最优路径见表4和图5。可以看出对于不同的权重系数，最终的最优路径总体上倾向于目标3的最短路。

表4 几何加权法计算结果Table 4 Calculation results of geometric weighting method

图5 几何加权法最短路Fig. 5 The shortest path of geometric weighting method

在相同的权重下以路段赋值法进行计算，求得不同权重下的最优路径见图6和表5，可以看出由于目标3函数的度量值较小，因此在线性加权中作用被低估，而采用路段赋值法则将目标函数标准化，更能体现目标之间的关系，有多条最优线路倾向于目标3的最优路线。

图6 赋值法最短路Fig. 6 Shortest path of assignment method

λq路径目标1目标2目标31∶1∶120→10→6→17→131 8921 966246∶3∶120→9→14→5→18→16→1→135681 8373916∶1∶320→10→6→17→131 8921 966243∶6∶120→10→7→11→21→12→2→1→133 5761 3571803∶1∶620→10→6→17→131 8921 966241∶3∶620→10→7→6→17→132 6091 573361∶6∶320→10→7→6→17→132 6091 573364∶4∶220→10→6→17→131 8921 966244∶2∶420→10→6→17→131 8921 966242∶4∶420→10→7→6→17→132 6091 57336

5 结 论

1)提出了求解多目标最短路问题的路段赋值法，并证明了该方法的可行性。路段赋值法综合考虑了路线的距离及路段数对路线选择的影响，对最短路和非最短路的不同赋值符合出行选择规律。路段赋值法能有效地消除各目标所对应度量值的差异造成的影响。

2)为减少计算工作量，结合K-最短路算法和路段赋值的过程，给出了路段赋值法求解多目标最短路的计算步骤。

3)通过实例研究比较了各单目标、不同权重下常规线性加权与几何加权算法、路段赋值法计算所得的不同结果。结果表明，常规线性加权法中对于度量值较小的目标在线性加权中作用被低估；而在几何加权法中，度量值较小的目标所造成影响被过度放大；笔者所提出的路段赋值法则将目标函数标准化，更能体现多目标之间的关系，对现有研究方法进行了改进与优化。