多目标优化-改进遗传算法路径规划模型

孙睿 黄海超 霍欣婷 陈景雅

摘 要：优化智能算法进行路径规划可以有效缓解用户出行拥堵问题，为此，设计了多目标优化-改进遗传算法（multi-objective-improved genetic algorithm， M-IGA）组合模型。采用Dijkstra算法改进种群初始化策略，完全规避了断路和环路，提高了初始种群质量；设计基于邻接矩阵的深度优先遍历交叉策略、邻接限制半随机变异策略，兼顾算法全局搜索和局部寻优能力，解决了种群多样性降低、过早收敛的问题。同时，在设计适应度函数时，引入个体用户偏好权重系数，综合考虑了平均行驶时间、交叉口延误、道路拥挤状况、道路等级4种因素来进行多目标优化，为用户寻找符合个体期望的最优路径。研究结果表明，所提出模型相比于蚁群算法路径寻优效率提高了54.322 0%；相比于单目标路径寻优，最优路径综合代价降低了23.609 1%，有效避开了拥堵及交叉口多的路段。

关键词：多目标优化；改进遗传算法；路径规划；层次分析法

中图分类号：U491

文献标志码：A

随着社会经济的不断发展，人民生活水平不断提高，城市路网上私人汽车数量不断增加，由此带来的道路拥堵、停车困难等现象日趋严重［1］。路径诱导及导航服务是智能交通系统的重要组成部分［2］，是解决用户出行交通拥堵问题的有效方法［3］，而合理选用和优化智能算法进行路径规划是实现路径诱导及导航服务的核心［4］。

遗传算法是一种采用种群搜索策略的全局性寻优算法，该搜索机制使求得最优解的可能性和效率大大提高，故该算法被广泛应用于包括路径规划在内的众多问题的求解。但传统遗传算法存在早熟收敛、种群多样性降低等问题［5］。同时，由于目前的路径规划研究大多以单一目标（时间最短或者距离最短）进行最优路径搜寻［6-11］，忽略了道路等级、道路拥堵情况等影响因素，使其对现实路网应用意义不大。

为解决以上问题，本文在改进经典遗传算法的基础上，针对路径规划应用进行了多目标优化：一方面，改进遗传操作解决传统遗传算法在路径规划中的局限性（断路、回头路、种群多样性降低、早熟收敛等）；另一方面，在算法中加入反映个体出行偏好的权重系数，综合考虑平均行驶时间、交叉口延误、道路拥挤状况、道路等级4种影响因素，更好地解决出行交通拥堵问题。

1 模型构建

1.1 算法编码

区别于传统的二进制编码，采用实数编码方式，更贴近路径规划现实问题。一条路径就是一个染色体个体，路径上的每一个道路交叉口或是单独路段的起终点就是染色体上的基因［12］。如染色体“1-3-5-8-9”代表了路网上由起点1到终点9的一条路径，1、3、5、8、9都是路网节点。传统遗传算法为了满足交叉、变异的要求，使用的染色体长度相同［13］。本文采用变长度方式，更能丰富种群的多样性，也符合现实路径长度灵活多变的特点。

1.2 初始种群的选取

初始种群的质量在遗传算法中起决定性作用，而遗传算法采用完全随机方式产生的初始种群虽然多样性丰富［14］，但会包含大量的断路、回头路，这会导致算法寻优效率降低，迟迟无法收敛。

为了保证初始种群的质量，避免断路、回头路的产生，本文设计了Dijkstra算法改进的半随机方式种群初始化策略。具体步骤如下：

Step1 将路网中每一节点与其余节点的连接作标记，通路标记1，断路标记0，构建邻接矩阵；

Step2 从起点O开始，选择下一节点时，按照邻接矩阵选择标记1的通路，避免断路产生；

Step3 标记已选择过的节点，禁止下次选中，避免回头路产生；

Step4 如果当前节点已无未标记的连通节点，则退回上一节点重新选择；

Step5 重复Step2—Step4，直至扩展到终点D为止，形成一条不包含断路、环路的染色体；

Step6 重复Step2—Step5，直至染色体个数达到初始种群规模。

1.3 适应度函数的构造

遗传算法中适应度函数也叫评价函数，是用来判断群体中个体的优劣程度的指标［15］。本文选用时间单位作为适应度函数的统一量纲，综合考虑平均行驶时间、交叉口延误、道路拥挤状况、道路等级，采用层次分析法 （analytic hierarchy process， AHP）［16］計算个体用户对以上4种影响因素的偏好权重系数。

1.3.1 4种因素的权重系数计算

1）构建判断矩阵

在用户现实选择时，经典9种标度可能会因为重要性区分不明显而产生困扰，故模型采用简化后的3种标度，规定如表1所示。

根据表1构建4种因素的判断矩阵并计算权重，其随着用户对4种影响因素重要性排序不同而改变，此处只是举例说明。D1、D2、D3、D4分别对应平均行驶时间、交叉口延误、道路拥挤状况、道路等级4种因素，判断矩阵如表2所示。

用和法计算D1影响因素权重：

w1=14×11+15+13+15+55+1+53+1+

33+35+1+35+55+1+53+1

=0.576 9

同理可得其余3种影响因素权重分别为：0.115 4、0.192 3、0.115 4。

2）一致性检验：

λmax=1n∑ni=1∑nj=1dijwj/wi

=14∑4i=1∑4j=1dijwj/wi

=4.000 2

CI=λmax－nn－1

=4.000 2－44－1

=0.000 067

CR=CIRI=0.000 0670.90

=0.000 074<0.10

式中：λmax为n阶判断矩阵的最大特征值；n为影响因素个数；dij为判断矩阵中因素i对因素j的比重；wj、wi分别为影响因素j、i的权重；CI为一致性指标；CR为检验系数；RI为随机一致性指标，判断矩阵阶数为4时取值为0.90。

判断矩阵通过一致性检验。

1.3.2 4种因素量纲统一

1）交叉口延误与道路拥挤状况

对于交叉口而言，在现阶段研究中它的主要评价指标是延误时间。美国道路通行能力手册给出了交叉口的评价标准，将服务水平分为六级［17］；对于道路拥挤状况，已有研究采用模糊数学中的综合评价方法计算道路拥挤度系数对城市路网的交通拥堵状态进行评价，并将其分为6个服务水平等级［18］。鉴于交叉口和道路拥挤状况的服务水平等级都是六级，汇总得到表3。

本文通过地点速度［19］计算拥挤度系数S来判断服务水平等级，通过线性插值法计算路网交叉口的平均延误时间t2；量化道路拥挤状况影响因素至时间量纲，以表3中拥挤度系数S为折减系数，则拥挤延误时间t3可在平均行驶时间t1的基础上通过折减计算得到。

2）道路等级

曼彻斯特是英国重要交通枢纽，本文选取其局部公路网作为模型实验对象，路网包含50个节点，交通流数据来自英国公路交通数据集［20］。在《Guidance on Road Classification and the Primary Route Network》（《道路分类和主要路网指南》）中，全英道路划分为4个分类等级：A类道路，B类道路，分类未编号道路，未分类道路［21］。本文选取的曼彻斯特局部路网只包含A类道路和B类道路2种。图1为简化路网示意图。

将道路等级转换为时间量纲t4是通过将其转换为折减系数以在平均行驶时间上进行折算。若每一条染色体个体中包含的A类道路数量≥B类道路数量，则t4=0，否则按0.2的折减系数对t1进行折减。

1.3.3 适应度函数计算

综上，考虑平均行驶时间、交叉口延误、道路拥挤状况、道路等级后的适应度函数计算如下：

f=w1∑m－1i=1t1（i，i+1）+w2∑m－1i=1t2（i，i+1）+

w3∑m－1i=1t3（i，i+1）+w4t4（1）

t1（i，i+1）=L（i，i+1）（Vi+Vi+1）/2（2）

t2（i，i+1）=t2b+（t2u－t2b）（S（i，i+1）－Sb）×

（Su－Sb） （3）

t3（i，i+1）=S（i，i+1）L（i，i+1）（Vi+Vi+1）/2（4）

t4=0，NA≥NB0.2∑m－1i=1L（i，i+1）（Vi+Vi+1）/2，NA

式中：m为染色体个体中包含的路网节点数量；w1、w2、w3、w4分别为4种因素的权值；L（i，i+1）为节点i到节点i+1的距离；Vi、Vi+1分别为节点i， i+1的速度；S（i，i+1）为节点i到节点i+1路段的拥挤度系数；t2b、t2u分别为表3中不同服务等级对应t2的下限值和上限值；Sb、Su分别为表3中对应拥挤度系数S的下限值和上限值；NA、NB分别为一条染色体中A类、B类道路数量。

1.4 遗传操作的改进

1.4.1 选择操作

本文的选择方法采用轮盘赌选择法，但一般轮盘赌选择法应用中，染色体个体的适应度值越大越容易被选择保留，与本模型的适应度值越小越优化原则相悖，所以将个体被选择概率作如下改进：

pj=1－fj/∑spj=1fj/（sp－1）（6）

式中：sp为初始种群规模；fj为个体j的适应度值。

轮盘赌选择结束后，为了进一步提高选择后群体的质量，采用最佳个体保留策略，即用此时群体池中适应度值最小个体替换适应度值最大的个体，保证种群向最优方向进化。

1.4.2 交叉操作

遗传算法通过交叉操作将种群中2个个体随机交换某些基因，期望有益基因组合在一起；但在路径规划问题中这样的方式极大概率会使后代产生断路、回头路，使得交叉操作无意义，大大降低路径寻优的成功率和效率。因此，本文设计基于邻接矩阵的深度优先遍历交叉策略，不仅完全避免了断路、回头路的产生，同时保证交叉操作使子代优于父代。具體步骤如下：

Step1 在群体池中按事先设定的交叉率pc选取两个父代个体I1，I2。

Step2 在个体I1中随机选取一个节点m1（除起、终点外）作为待交叉点。

Step3 按照邻接矩阵在个体I2中查找所有与m1邻接的点，计算m1与各邻接点的平均行驶时间，选择最小值对应的邻接点作为个体I2中的待交叉点。若个体I2中没有与m1连通的邻接点，则返回Step2重新选取待交叉点。

Step4 父代个体I1，I2分别在各自待交叉点断开，交换前后基因，产生2个子代个体N1，N2。

Step5 计算I1，I2，N1，N2的适应度值，比较四者。若最优个体在子代中产生，说明交叉操作成功，将四者中适应度值最小的2个个体作为交叉后产生的个体；否则交叉操作失败，返回Step2重新选取待交叉点。

Step6 重复Step1—Step5，直至交叉操作结束。

1.4.3 变异操作

遗传算法对变异个体采取随机变异的方式，会破坏交叉操作的全局寻优结果，而且在路径规划问题中并不能达到丰富群体多样性的功能，反而会降低种群质量。因此，本文设计邻接限制半随机变异策略，在保护交叉操作全局搜索能力的基础上，兼顾变异操作的局部搜索能力，同时维持群体的多样性，防止出现未成熟收敛现象。具体步骤如下：

Step1 对群体池中个体按事先设定的变异概率pm判断是否要进行变异。

Step2 在变异个体中随机选择除起、终点外的基因位置作为待变异点，d为待变异点在该个体中的基因位置序号。

Step3 按邻接矩阵寻找基因位置d-1，d+1上节点的邻接点，去除d基因位置上的节点，确定二者的交集B。

Step4 若B不是空集，则将待变异位置d上的节点随机变异为B中包含的节点；若B是空集，返回Step2，重新选择待变异点。

Step5 变异后检查此时个体中是否有节点重复出现，若有，返回Step2。

Step6 若该个体中始终没有符合要求的待变异点，则返回Step1，进行下一个体是否需要变异的判断。

2 实例应用

2.1 模型参数选取

在本模型中，种群规模过小会导致算法难以收敛，同时得到的最优路径的综合代价过高，不满足用户现实需求；种群规模过大会浪费计算资源，增加用户等待时间。为选取最优参数，进行多次实验模拟，模拟结果如图2所示。由图2可以看出：随着种群规模增大，收敛迭代次数呈下降趋势，最优路径综合代价先降低后不变。因此最终确定：种群规模为40，交叉概率为0.9，变异概率为0.1，最大迭代次数为120。

2.2 实例实验

本模型采用多目标优化-改进遗传算法（multi-objective-improved genetic algorithm， M-IGA）。为了验证改进算法和多目标优化的性能以及二者组合后模型的整体性能，进行以下4组对比实验：单目标-改进遗传算法（single-objective-improved genetic algorithm， S-IGA）与单目标-经典遗传算法（single-objective-genetic algorithm， S-GA）；多目标-经典遗传算法（multi-objective-genetic algorithm， M-GA）与单目标-经典遗传算法（S-GA）；M-IGA与S-GA；M-IGA与多目标-蚁群算法（multi-objective-ant colony algorithm， M-ACA）。每组实验选取曼彻斯特局部路网上5个起终点（origin destination，OD）对，每个OD对分别做20次實验，对比实验结果见表4。由表4可知：

1）S-IGA与S-GA

相比于S-GA，S-IGA的算法运行时间平均增加了14.809 8%，最优路径综合代价平均降低了12.575 0%。

2）M-GA与S-GA

相比于S-GA，M-GA的算法运行时间平均增加了3.807 4%，最优路径综合代价平均降低了21.390 2%。

3）M-IGA与S-GA

相比于S-GA，M-IGA的算法运行时间平均增加了21.182 2%，最优路径综合代价平均降低了23.609 1%。

4）M-IGA与M-ACA

相比于M-ACA，M-IGA的算法运行时间平均减少了54.322 0%，最优路径综合代价平均降低了26.589 4%。

2.3 结果分析

S-IGA与S-GA对比实验结果显示，改进的遗传算法可以有效降低收敛后的路径综合代价。经分析可知：本文设计的Dijkstra算法改进的半随机方式种群初始化策略、基于邻接矩阵的深度优先遍历交叉策略和邻接限制半随机变异策略，可以保证进化向最优推进而并非随机发散式无效迭代，同时避免算法陷入局部最优解，使改进后的算法全局优化出综合代价更低的路径。

M-GA与S-GA对比实验结果显示，引进偏好权重系数的多目标优化可以有效改善经典遗传算法的收敛结果。经分析可知：本文在选择操作的适应度函数设计中引入平均行驶时间、交叉口延误、道路拥挤状况、道路等级的偏好权重系数，可以有效为用户避开拥堵、交叉口多的路径，使得路径规划结果更符合用户预期。

M-IGA与S-GA以及M-ACA的对比实验结果表明，本文设计的多目标优化-改进遗传算法组合模型，虽然牺牲了少部分算法运行效率，但是模型规划出的最优路径的综合代价大大降低，减少了3～6 min。与经典遗传算法纵向比较，最优路径综合代价降低了23.609 1%；与多目标蚁群算法横向比较，最优路径综合代价降低了26.589 4%。

3 结论

本文针对经典遗传算法路径规划的弊端，分别进行了改进算法、模型多目标优化两方面的研究：

1）Dijkstra算法改进的半随机方式种群初始化策略，100%规避了断路、回头路的产生，提高了初始种群质量；基于邻接矩阵的深度优先遍历交叉策略，在完全避免断路、回头路产生的同时，保证交叉后子代适应度值优于父代，提高交叉操作全局寻优能力；邻接限制半随机变异策略，在不破坏群体池内优秀个体基因的基础上，维持种群多样性，防止早熟收敛。

2）在适应度函数设计时引入偏好权重系数，对模型进行多目标优化。用户可根据习惯偏好，在模型的输入中设置平均行驶时间、交叉口延误、道路拥挤状况、道路等级的重要程度排序。实验结果表明，最优路径的综合代价相比于单目标减少了23.609 1%，模型可以按需避开交叉口多、拥堵的路段，得到更符合用户期望的路径规划结果。

参考文献：

[1]《中国公路学报》编辑部. 中国交通工程学术研究综述·2016［J］. 中国公路学报， 2016， 29（6）： 1-161.

［2］ HUANG H C， CHEN J Y， SUN R， et al. Short-term traffic prediction based on time series decomposition［J］. Physica A， 2022， 585： 126441.1-126441.15.

［3］ 詹军. 我国城市交通拥堵问题及治理对策［J］. 关东学刊， 2016（2）： 45-53.

［4］ LIN C， HAN G J， DU J X， et al. Spatiotemporal Congestion-Aware Path Planning Toward Intelligent Transportation Systems in Software-Defined Smart City IoT［J］. IEEE Internet of Things Journal， 2020， 7（9）： 8012-8024.

［5］ 温正， 孙华克. MATLAB智能算法［M］. 北京： 清华大学出版社， 2017： 145-152.

［6］ WANG Q Y， XU L H， QIU J D. Research and realization of the optimal path algorithm with complex traffic regulations in GIS［C］// International Conference on Automation and Logistics. Piscataway： IEEE， 2007： 516-520.

［7］ LIANG W， ZHANG Y， HU J M， et al. A Personalized route guidance approach for urban travelling and parking to a shopping mall［C］// 4th International Conference on Transportation Information and Safety. Piscataway： IEEE， 2017： 319-324.

［8］ 吴红波， 王英杰， 杨肖肖. 基于Dijkstra算法优化的城市交通路径分析［J］. 北京交通大学学报， 2019， 43（4）： 116-121， 130.

［9］ RAHIMI-FARAHANI H， RASSAFI A A， MIRBAHA B. Forced-node route guidance system： incorporating both user equilibrium and system optimal benefits［J］. IET Intelligent Transport Systems， 2019， 13（12）： 1851-1859.

［10］ALPKOAK A， CETIN A. Safe map routing using heuristic algorithm based on regional crime rates ［C］// Artificial Intelligence and Applied Mathematics in Engineering Problems. Cham： Springer， 2020： 335-346.

［11］王寧， 胡大伟， 徐杰， 等. 基于客户价值和满意度的城市冷链物流时变路径问题［J］. 中国公路学报， 2021， 34（9）： 297-308.

［12］董小帅， 毛政元. 基于改进遗传算法的动态路径规划研究［J］. 计算机工程与应用， 2018， 54（19）： 49-55.

［13］马永杰， 云文霞. 遗传算法研究进展［J］. 计算机应用研究， 2012， 29（4）： 1201-1206， 1210.

［14］于莹莹， 陈燕， 李桃迎. 改进的遗传算法求解旅行商问题［J］. 控制与决策， 2014， 29（8）： 1483-1488.

［15］杨从锐， 钱谦， 王锋， 等. 改进的自适应遗传算法在函数优化中的应用［J］. 计算机应用研究， 2018， 35（4）： 1042-1045.

［16］孔祥丽. 多影响因素下的导航路网数据路径规划研究［D］. 武汉： 武汉大学， 2018.

［17］蒋吴廷. 城市道路信号交叉口交通状态判别方法研究［D］. 重庆： 重庆交通大学， 2020.

［18］石征华， 侯忠生. 城市快速路拥挤度判别方法研究［J］. 交通与计算机， 2006， 24（5）： 20-23.

［19］王润泽. 基于实时位置服务的动态路径规划算法研究［D］. 兰州： 兰州交通大学， 2020.

［20］HIGHWAYS ENGLAND. Highways England network journey time and traffic flow data［DB/OL］.（2015-06-22）［2021-06-15］. http：//data.gov.uk/dataset/highways-england-network-journey-time-and-traffic-flow-data.

［21］阴炳成， 于守静. 完整街道尺度下城市道路等级分类［C］// 2017年中国城市交通规划年会论文集. 北京： 中国建筑工业出版社， 2017： 639-647.

（责任编辑：周晓南）

Path Planning Model Based on Multi-Objective Optimization

Improved Genetic Algorithm

SUN Rui， HUANG Haichao， HUO Xinting， CHEN Jingya*

（School of Civil Engineering and Transportation， Hohai University， Nanjing 210098， China）

Abstract：

Optimizing intelligent algorithm for path planning can effectively alleviate the problem of user travel congestion. The multi-objective optimization improved genetic algorithm combination model was designed. The Dijkstra algorithm was used to improve the population initialization strategy， which completely avoided the open circuit and loop， and improved the quality of the initial population. Taking into account the global search and local optimization ability of the algorithm， the depth-first traversal crossover strategy and adjacency -restricted semi random mutation strategy based on adjacency matrix were designed， so as to solve the problems of reduced population diversity and premature convergence. Meanwhile， the individual user preference weight coefficient was introduced in the design of the fitness function， and the four factors of average driving time， intersection delay， road congestion and road grade were comprehensively considered for multi-objective optimization to find the optimal path that meets the individual expectation for users. The results show that compared with ant colony algorithm， the path optimization efficiency of the model is improved by 54.322 0%; compared with single objective path optimization， the comprehensive cost of the optimal path is reduced by 23.609 1%， effectively avoiding congestion and multiple sections of intersections.

Key words：

multi-objective optimization; improved genetic algorithm; path planning; analytic hierarchy process

收稿日期：2022-01-11

基金項目：国家自然科学基金资助项目（52078190）

作者简介：孙 睿（1998—），女，在读硕士，研究方向：智能交通系统中的动态路径规划，E-mail：sunrui@hhu.edu.cn.

通讯作者：陈景雅，E-mail：13805151397@139.com.