一种增量式多目标优化的智能交通路径诱导方法

文孟飞　彭军　刘伟荣　李冲　张晓勇

摘要：路径诱导是一种主动引导车辆合理分流来解决城市交通拥堵的方法.本文提出了一种基于增量搜索的多目标优化路径诱导方法.该方法首先利用图论法将复杂路网抽象为点线的赋权图，引入多目标优化变量，建立路网模型；然后在启发式搜索基础上引入增量搜索，结合全局规划和局部动态重规划，实现车辆的实时路径诱导.仿真结果表明该方法能有效地解决复杂路网中车辆的实时路径诱导问题.

关键词：动态重规划；增量搜索；路径诱导

中图分类号：U491.123文献标识码：A

当前，缓解城市交通拥堵问题的方法主要有两种：一是加大城市路网建设力度，提升路网吞吐量；二是发展智能交通系统（Intelligent Transportation Systems，ITS），提高道路运行效率.针对各大城市越来越有限的土地资源，以智能学习的方式，优化城市路网运营和管理，显然是一种最实际的解决方案.动态交通路径诱导系统是ITS的一个重要方向，对城市交通路网管理的效果愈发显著.它采用检测技术、计算机技术、网络技术等高新手段，基于实时交通信息采集、处理与传输，通过中心式、分布式等多种诱导方式，为驾驶员提供交通事件、行程时间和优化路径等动态信息，可引导驾驶员避开拥挤走最佳行驶路线，从而实现路网交通流的均衡动态分配，有效缓解交通拥挤.高效的路径选择算法是动态交通路径诱导系统的关键技术.从本质上来说，路径选择算法需集中式收集整个路网信息，选择恰当的交通流函数，通过高效的算法对路网进行快速更新，动态地找寻满足一定约束条件的最优路径.构建路网模型，选择高效算法，动态地选择源节点到目的节点的最优路径，从局部来说对驾驶员路径选择作出最优安排，从总体上说可优化城市路网流量的均衡分配，解决路网的拥堵问题.

动态路径诱导在ITS、通信系统和机器人等人工智能方面应用广泛.若城市路网是静态网络，路段信息不变且可知，则很容易通过全局规划找寻一条从源状态到最终状态的最佳路径.但实际情况却是，交通信息时刻都在变化，环境信息动态改变，实际行驶过程中的路网情况和初始情况差异很大，此时需不断更新路网信息，实时找寻源状态节点到最终状态节点的动态最优路径.一些学者已研究了在动态环境情况下找寻最优路径的方案和算法思想1-4]，局部重规划就是其中一种关键算法，能有效地实现动态环境下的路径诱导，将历史数据保留，通过算法重用，减少了重新获取整个路网信息的工作量.

经典的路径诱导方案通常只针对单个因素进行优化，但实际上现实问题往往由多方面因素相互制约，单个因素很难正确描述，因而路径诱导往往需对多个因素进行同时处理和优化，即多目标路径诱导.作为人工智能的关键方法，启发式搜索已应用于多目标路径诱导研究，很多学者进行了相关研究.Stewart和White将A*算法延伸到多个优化变量，并利用启发式搜索解决路径诱导，从而提出了多目标启发式搜索模型5]；Dasgupta改进了多目标启发式搜索，引入非单调的启发信息用于解决VLSI设计难题6]；Mandow针对节点难以扩展问题，将路径扩展引入多目标启发式搜索，提高了搜索算法的准确性6-7]；Harikumar和Dasgupta总结了深度优先搜索算法在多目标路径诱导上的应用8-10].通过对多个变量进行优化，多数状态空间搜索规划器改进了智能规划技术11-13].

文献14-16]将增量搜索思想引入路径诱导局部重规划.在许多相似度较高的多目标优化问题中，环境信息只是局部变化，若重新进行全局规划会带来不必要的计算复杂度，若能够对历史信息重用，则可提高算法效率.本文提出了一种当检测到环境信息动态改变时，怎样实时选择最优路径以实现全局最优规划的路径诱导方案，先由当前的静态路网信息利用启发式搜索算法作全局规划，找寻最短路径；车辆行进过程中，一旦路网信息变化，就需不断更新历史信息，在之前规划的信息前提上再作增量搜索，减少计算复杂度，提高算法效率，从而利用动态局部重规划找寻目前状态到最终状态的最优路径方案.

1构建路网模型

城市交通网络错综复杂，但都是由单个交叉路口构成的，可利用图论法抽象为点线的网格拓扑，用点代表平面交叉口，用线代表路段，如图1所示.这样路网可以抽象为由节点集合、弧段集合和路权集合等构成的几何赋权图.

通过将实际交通路网抽象出来，以数学形式存储路网模型.首先根据启发式搜索算法找出从起始状态节点到目标状态节点的最优路径；当车辆在行驶过程中某些路段权重发生变化，若全局更新则会降低系统实时性，本文通过动态重规划算法对经过该路段的局部路径网络进行代价更新，从而可提高算法效率和系统实时性.

2多目标启发式搜索算法

启发式搜索算法应用到复杂交通网路，且当路况变化频繁时，启发式数量急剧增长，算法时间消耗较大，适应性降低.增量搜索算法能很好地利用路网变化的局部变化信息，避免全局更新，对提高算法的效率具有积极意义.

3基于增量搜索交通动态路径诱导

城市复杂交通网络日益拥堵，动态交通诱导思想可以很好地改善交通状况.考虑城市交通环境时刻变化给算法效率带来的问题，可在之前已有的搜索信息上只对变化的部分进行局部动态重规划，从而提高算法效率.增量搜索算法可实现局部的动态重规划，来解决环境时刻变化问题.本文将增量搜索算法引入到启发式搜索算法，提出了动态多目标路径诱导算法DMRGA（Dynamic Multiobjective Route Guidance Algorithm），该算法既保留了启发式搜索快速高效的特点，又能适应于复杂的动态网路环境，进行动态路径诱导.在本文提出的路网模型上，结合启发式搜索算法和增量搜索算法的思想，进行全局规划和动态局部重规划，很好地解决了实时找寻最优路径的问题，解决车辆动态路径诱导问题.

DMRGA算法分为两部分：全局规划及局部动态重规划.全局规划根据已知的静态城市网路信息找寻源状态到最终状态的最优路径；局部规划则是在路网环境信息动态变化时，先在局部做静态规划，然后在原有基础上作增量搜索，进行动态重规划，实时调整最优路径.当检测路网信息发生变化时，须马上作出响应，动态调整目前节点到最终节点的最优路径，以免造成不必要的延时，影响路网全局性能.

实验结果表明，车辆在行驶过程随着路网某路段权重的更新，其最优行驶路径也在不断更新，动态实时地调整行车路线，尽可能减少行车耗时.实验以一个小型的部分路网作为场景，可以扩大到整个路网，实时给出车辆优化路径.

5结论

本文针对时刻变化的路网信息，提出一种基于增量搜索的多目标路径诱导方法.该方法首先利用图论法将复杂路网抽象为点线的赋权图，引入多目标优化变量，建立路网模型.然后在启发式搜索基础上引入增量搜索，结合全局规划和局部动态重规划，实现车辆的动态路径诱导.首先进行全局规划，利用多目标启发式搜索算法找寻最优路径集合；当检测到环境信息变化时，进行动态局部重规划，在尽可能保留前次规划的基础上进行增量搜索，减少算法复杂度，提高效率，实时更新最优路径.最后仿真结果表明该方法能有效地实时解决复杂路网中车辆的动态路径诱导问题.

参考文献

[1]ZHU Q B. Ants predictive algorithm for path planning of robot in a complex dynamic environmentJ]. Chinese Journal of Computers， 2005， 28（11）： 1898-1906.

[2]KOENIG S， LIKHACHEV M， FURCY D. Lifelong planning A*J]. Artificial Intelligence， 2004， 155（1/2）： 93-146.

[3]YANG J， ZHANG M. A twolevel path planning method for onroad autonomous drivingC]//2th International Conference on Intelligent System Design and Engineering Application， Sanya， China：2012：661-664.

[4]XI Y G， ZHANG C G. Rolling path planning of mobile robot in a kind of dynamic uncertain environmentJ]. Acta Automatica Sinica， 2002， 28（2）： 161-175.

[5]STEWART S B，WHITE C C. Multiobjective A*J]. Journal of the ACM， 1991， 38（4）： 775-814.

[6]OLIVEIRA RIOS L H， CHAIMOWICZ L. A survey and classification of A* based bestfirst heuristic search algorithmsC]//Advances in Artificial IntelligenceSBIA.Sao Bernardo do Campo， Brazil： 2010：253-262.

[7]MANDOW L， PEREZ J L DE AL CRUZ. A new approach to multiobjective A* searchC]// Proceedings of the 19th International Joint Conference on Artificial Intelligence. San Francisco， USA：2005：218-223.

[8]DASGUPTA P， CHAKRABARTI P P， DESAKAR S C. Multiobjective heuristic searchM]. Morgan Kaufman，1999

[9]XU Y Y，YUE W Y. A generalized framework for BDDbased replanning A* searchC]// Artifical Intelligences， Networking and Parallel/Distributed Computing. 10th ACIN International Conference on Software Engineering.Daegu South Korea， 2009： 133-139.

[10]HARIKUMAR S， KUMAR S. Iterative deepening multiobjective A*J]. Information Processing Letters， 1996， 58（1）： 11-15.

[11]REFANIDIS， VLAHAVAS I. Multiobjective heuristic statespace planningJ]. Artificial Intelligence， 2003， 145（1/2）： 1-32.

[12]SO M B，KAMBHAMDATI S. Sapa： A multiobjective metric temporal plannerJ]. Journal of Artificial Intelligence Research， 2003， 20： 155-194.

[13]SVEN K， MAXIM L， LIU Y X， et al. Incremental heuristic search in AIJ]. AI Magazine，2004， 25（2）：99-112.

[14]WEI W， OUYANG D T， LU N， et al. A multiobjective incremental heuristic search algorithmJ]. Journal of Jilin University：Science Edition， 2009， 47（4）：752-758.

[15]LU Y B， HUO X M， OKTAY A ，et al. Incremental multiscale search algorithm for dynamic path planning with low worstcase complexityJ]. IEEE Trannactionn on Systems， Man， and Cyberneticspart B： Cybernetics， 2011， 41（6）：1556-1569.

[16]SVEN K， SUN X X. Comparing realtime and incremental heuristic search for realtime situated agentsJ]. Auton Agent MultiAgent Syst，2009， 18：313-341.