第38卷第8期 2017年8月哈尔滨工程大学学报Journal of Harbin Engineering UniversityVol.38 No. 8Aug. 2017实时环境下多目标的路径选择模型陈海鹏1’2，刘陪1’2，申铉京1’2，王玉1，2’3(1.吉林大学计算机科学与技术学院，吉林长春130012; 2.吉林大学符号计算与知识工程教育部重点实验室，吉林长春130012; 3.吉林大学应用技术学院，吉林长春130012)摘要:针对出行者出行需求多样化的问题，本文从时间、费用角度出发，构建了实时环境下基于多目标的路径选择模型。
采用加权求和函数对多维数据聚集得到组合权重，而权重系数可依据出行者需求或喜好设定。
为验证模型的实用价值，在仿真环境下，多目标模型与基于几何距离最短的路径选择模型在时间、费用、距离等评价指标进行了对比。
实验结果证明实时环境下基于多目标的路径选择模型更具有实用价值。
关键词：智能交通系统；动态路径诱导系统；多目标；路径选择模型；加权求和函数；组合优化；广义自适应A'■算法D O I：10. 11990/jheu. 201604080网络出版地址：http://www. cnki. net/kcms/detail/23. 1390. u.20170427. 1510. 076. html中图分类号:TP399 文献标志码:A文章编号:1006-7043(2017)08-1285-08Route choice model based on multi-objective in a real-time environment CHEN Haipeng1’2,LIU Pei1’2,SHEN Xuanjing1’2,WANG Yu1’2’3(1. College of Computer Science and Technology, Jilin University, Changchun 130012, China；2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China；3. Applied Technology College ,Jilin University, Changchun 130012, China)Abstract ；In view of this situation,a route choice model based on multi-objective was constructed and considered from the angles of cost and time in this paper.The weighted sum method was used to aggregate multi-target data objects to obtain the composite weight value,and the weight coefficient can be set based on travelersr needs or preferences.To verify the practical value of the model,the multi-objective-based model was compared with the route choice model on the basis of the shortest geometric distance in terms of time,cost,and distance.Experimental results show that the path of the multi-objective optimal route choice mode has more practical value based on a real-time environment.Keywords ：intelligent transportation system；dynamic route guidance system；multi objective;route choice models; weighted sum method;combinatorial optimizing；generalized adaptive A*algorithm智倉旨交通系统（intelligent transportation system，ITS)是集信息、通信、控制及网络等技术于一体的综合研究学科，可以提供全方位、实时、准确以及高效 的服务信息，ITS是有潜力的研究方向，进一步说将 成为未来相关研究领域的热点[1]。
动态路径诱导 系统（dynamic route guidance system,DRGS)是 ITS 一个重要的分支，利用计算机、通信等现代技术，为 出行者提供实时交通信息以及最优路径。
在DRGS 中，路径选择模型可以确立DRGS的目标m。
路径诱导模型分为静态模型和动态模型，静态收稿日期=2016 -04 -26. 网络出版日期=2017 -04 -27.基金项目：国家青年科学基金项目（61305046);吉林省自然科学基金 项目（20140101193JC，20150101055JC) •作者简介:陈海鹏（1978 -)，男，副教授；王玉（1983 _)，男，讲师.通信作者 :王玉,E-mail ：wangyu001@ jlu. edu. cn.模型以假设出行者获知路网信息为前提，并以随机 期望效用理论或积累前景理论为基础。
而动态模型 包含一些信息获取和学习的过程，以随机虚拟理论 或增强学习理论作为指导[3]。
目前，在国内路径诱 导模型的研究主要还是集中在静态模型且取得了阶 段性的成果。
基于期望效用理论的模型是在确定性 框架下，以几何路径或者出行时间为效用值，以期望 获得效用最大化评价各备选方案的优劣。
孟梦等针 对不同的出行时间，提出了组合出行工具的路径选 择模型，以组合出行工具的模式下为出行者提供最 优路径[4]。
刘艳秋等构建了交通堵塞下基于实时 交通信息的路径选择模型[5]。
相反，积累前景理论 是不确定性情况下的决策行为，决策者以财富的变 化量而不是最终量作为参考依据进行决策[6]，针对 交通信息不确定的特性，诸多学者以积累前景理论•1286 •哈尔滨工程大学学报第38卷为基础提出了路径选择模型[74]。
但是，目前提出 的模型大多仅针对路段行程时间构建的单目标路径 选择模型[6]，显然，与实际存在很大的偏差。
在实 时环境下，交通畅通、拥挤情形下路阻的产生形式有 所差异，因此，分别以交通畅通、拥挤下的路阻构建 了基于时间最短的路径选择模型，进而提高了模型 的可靠性。
Erel Avineri等提出时间是影响路径抉择最重 要的因素，但不能确切地表述所有出行者的意愿[1°]。
由此可见，在实时环境下，路径优化是多目 标组合优化问题[11]，例如，时间、费用、环境等因素。
因此，仅从时间上考虑构建路径选择模型并不合理 而建立基于多目标的路径选择模型是有必要的。
因此，分别从时间、费用两个角度出发，构建了实时环 境下基于多目标的路径选择模型。
在处理多准则优化问题时，一般采取单目标类 和多目标类的策略[12]。
单目标类将多目标优化问 题转化为单目标优化问题，转化过程使用目标聚合 或目标标准策略对其结果进行组合。
而多目标类是 以目标向量间的关系来定义决策向量之间的优劣关 系，一般可获得均勻分布的Pareto最优前端。
但在 高维度下，多标准Pareto最优路径算法运行效率极 低甚至无法运行[13]。
然而，在实时信息下，对反应 速度的要求却十分苛刻，由此可见多目标类在动态 实时路网中并不实用。
评价函数中加权求和函数属 于单目标类，加权求和函数是解决多目标函数优化 问题比较常见的方式之一。
它采用目标聚合策略即 将多维空间中的数据对象聚集转化为单目标空间的 优化问题。
处理过程相对比较简单，但组合权重的 意义及结果的优劣至关重要。
聚合过程中，由于不 同的计量方式，各个目标函数间具有不同的值域。
相应地，当映射到加权求和目标函数时，决策变量间 具有不同的阈值。
在这种情形下，阈值大的决策变 量对组合函数的支配大，反之支配小[14]。
所以，本 文在使用加权求和函数前，对各个目标函数值进行 了预处理，即对其进行类似的量值处理，从而保证支 配能力的均衡即可获取最优路径。
1基于多目标的路径选择模型设计1.1问题描述及分析路径优化问题相当于图理论模型中最优路径的 查找问题，但又存在差异。
在动态路径诱导系统中 含有静态属性和动态属性[15]，静态属性是路网信息 相对固定的部分，例如：地理位置信息、路段间距以 及路段的基本通行能力等。
而动态属性可以反映实 时信息状况，例如，车流量、行车速度等。
所以，路网 数据对象具有多样、复杂以及实时的特性。
以图论为基础，同时结合动态路网信息的特性，路径优化问 题的定义形式：P=!G,r,,Sstart,S e n d|(1)式中：G= (y y.)是静态属性，表示路网结构；F是 从起始点到结束点间的结点集合;&是当前S s t a r t到 s6nd所有无环路集合，其定义形式为\Rij\i,j&V!\ i(2)式中:是体现了动态路径诱导系统中的动态属性，对应（i，j)间的权重值，并以此为优化准则；Sstart是出发节点且随着车辆的不断行驶动态更新，Send表亦目标节点。
1.2基于时间最短的路径选择模型在实时交通信息下，影响路阻的因素多样化。
例如:天气、ITS系统故障、交通事故等偶然事件，也 包含一些不确定因素，例如车速、车流量等。
所以，仅以单一的车辆行程时间为路阻并不合理，交通畅 通或者拥挤的情形下产生路阻的方式有所差异。
在 交通畅通情形下以行驶时间及交叉口转向延误产生 的时间为路阻;而在交通拥挤的状态下，产生路阻最 主要的是延误时间而行程时间可忽略不计。
所以，基于时间最短的路径选择模型的定义形式为min Y,X^>/i K( +d D v)+(1J-X)(J, +£»,)(«其约束条件为R v=f1'^o,i=iK=n, Q/C,e[0,1]_ io,(2C, - Q,)/C,e(1,2)0，(0 < D t j(t) <tj1，(K ^D.j it)^nK)式中均属于^集合且互异。
