多用户弹性需求网络的双准则系统最优交通分配

第 31 卷增刊 1 2011年 10 月 系统工程理论与实践 S y stem s E n gin eerin g 一 T h eo ry & P raetiee VO 1 3 1, S uP .1 O et., 2 0 11 文章编号:1000-- 6788(2011)51一009今09 中图分类号: u 491 文献标志码: A 多用户弹性需求网络的双准则系统最优交通分配 王 听 �,2, 黄海军 � (1.北京航空航天大学经济管理学院, 北京 1001 91 ;2.北京信息科技大学理学院, 北京 10 01 92 ) 摘 要 针对存在异质用户的弹性需求交通网络, 当用户时间价值呈离散分布时, 给出了系统时间 最优和系统费用最优的双准则优化模型及其帕累托有效前沿.证明了存在正的匿名路段收费 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 , 支持除系统时间最优解之外的其他帕累托解与多用户均衡解达到一致, 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 了帕累托最优解处的 系统性能与各自的单目标最优系统性能之间的偏差.研究 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明, 该偏差的上界仅依赖于用户的时间 价值分布, 而与路段流量分布和路段出行时间函数无关. 关键词 多用户弹性需求网络;双准则系统最优;用户均衡;帕累托最优 B i一 e r it e r ia sy s te m o P t im u m tra ffi e a ss ig n m e n t in n e tw o rk s w ith m u lt i一 u s e r e la ss e la st ie d e m a n d s W A N G X in l,2, H U A N G H ai一unl (1. SehoolofE eonom ies and M an路em ent, Beihang U nive rsity, Beijing 100191, C hina; 2. S eho ol o f A P P lied Seien ee , B eij in g In fo rm ation Seien ee an d Te eh no logy U n ive rsit从 B eij in g 100 192 , C h ina A b str a et Fo r elastie d em an d tra n sp ortat io n n etw ork s w ith h etero gen e ou s u sers d iffe ren tia ted b y v alu e of tim e , a b i一 e riteria op tim izatio n m o d el a im in g at m in im izin g th e to ta l trav el tim e a n d to tal trav el eo st 15 p ro P o sed . T h e P a re to op tim a l fr o nt ier o f th e m o d e l so lu tion 15 d eriv ed . It 15 sh ow n th at an y P areto oP tim u m , ex eeP t th e tim e一 b as ed o n e , ea n b e d e een tralized in to a m u lti一 elas s u ser e q u ilib riu m by a seh em e w ith p o sitive a n o n y m o u s tolls o n a ll lin k s. T h e g ap s b etw een th e sy ste rn P erfo rm a n ees giv en by P areto oP tim u m a n d sin g le erite ria oP tim u m a re b o u n d ed . It 15 fo u n d th at th e u P P er b o u n d 15 in d eP en d ent of th e lin k fl ow d istrib u tio n an d lin k trav el tim e fu n etio n , b ut so le ly d ep en d ent u p o n th e va lu e o f tim e d istrib u tio n . K e y w o rd s m u lti一 u ser elas s elas tie d em an d n etw ork ; b i一 eriteria sy ste m oP tim u m ; u ser eq u ilib riu m ; P areto oP tim u m 1 引言 随着社会经济的迅速发展和城市化进程的加剧, 交通供需不平衡的矛盾变得日益尖锐 , 交通拥挤已经成 为各界普遍关注的热点问题. 拥挤道路使用收费作为交通需求管理的有效 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 之一 , 通过对特定时段和路段 的车辆实行收费, 从时间和空间上疏散交通量 , 达到缓解交通拥挤的目的. 在拥挤道路收费理论的研究中, 时间价值 (va lue of ti m e)起着至关重要的作用 , 它反映了出行者的社会 经济特征和收入水平差异, 在一定程度上表明了出行者能够或愿意为一次出行支付时间或金钱的程度, 是出 行者在时间和费用之间做出权衡的重要影响因素.传统的网络用户均衡 (lls e: equl libr tu m )交通分配模型中 假设用户具有一致的时间价值 , 即网络中的用户都是同质的.实际生活中, 由于出行者的收入水平差异 , 其时 间价值不尽相同, 对影响出行选择的准则的偏好也不相同, 因此需要考虑其异质性.此外 , 出行者可以依据时 间和费用两个指标来选择出行工具或路径, 系统性能也可以用时间最小或费用最小两种准则进行考量, 因此 多准则 (或称多目标)交通行为决策间题成为近年的研究热点. 收稿日期:20 11一0今� 资助项目:国家自然科学基金委创新研究群体基金 (7052一06一);2011 年度北京市优秀人才资助 (ZoliD oosoo70000os):北京信 息科技大学校科研基金 (5026010950) 作者简介:王听� (1978一), 女, 河北邯郸人, 博士研究生, 研究方向 交通运输规划与管理;黄海军 (l 964一), 男, 湖南人, 教授, 研 究方向:交通行为与决策, E一m ail :haij un hua ng @ bu aa �ed u ��n � 增刊 1 王听, 等:多用户弹性需求网络的双准则系统最优交通分配 Ya ng 和 H uang[�一2]利用最优化方法深入研究了固定需求和弹性需求下的边际成本道路收费理论. Le ur - en t[3] �M aye t和 H ans en [�] �N ag ur ne y[s] 建立了异质用户网络均衡分配模型, 研究了离散时间价值下的确定 性交通均衡分配问题.Ya ng 和 H uan g[0] 研究了离散时间价值和固定需求情形下, 基于时间或费用度量的单 目标系统最优问题与多用户均衡间题的等价性.Di al[ 7一�]假定出行者的时间价值为连续分布, 研究了实现用 户均衡流量与系统最优流量一致的道路收费问题.M ar oo tte 等 [0] 用无穷维变分不等式方法讨论连续时间价 值分布的双准则确定性交通均衡问题.N ag ur lle y 和 D on g[l �}运用有限维变分不等式方法研究了具有弹性需 求和非对称出行成本函数的双准则交通问题. zhan g �Ya ng 和 H ua ng[l �]考虑了多用户多准则的混合均衡问 题 , 其中每类用户的出行负效用表示为出行时间以及与时间无关的其他负效用的加权和 , 应用对偶理论证明 了支持用户均衡 一古诺纳什 (us er eq ul libr tu m 一 C ou m ot N as h) 混合均衡等价于系统最优的匿名路段收费的 存在性.G uo 和 Ya ng!�2]证明了离散时间价值和固定需求情形下, 存在正的匿名收费支持基于时间和费用度 量的双目标帕累托系统最优问题与多用户均衡问题等价. Cl ar k 和 Su m al ee[l �}考虑了离散时间价值和弹性 需求情形下, 存在正的匿名收费方案使基于费用度量的系统最优解成为多用户均衡解, 该收费值的经济意义 为路段上出行者的外部负效用乘以该路段上所有出行者时间价值系数的平均值;但基于时间度量时, 不存在 使得系统最优问题和多用户均衡问题等价的正的匿名收费方案.国内学者关于多用户 �多准则均衡交通分配 的研究, 可参考文献 !14一17}. 本文针对弹性需求路网及离散分布的出行者时间价值问题,构建了系统时间和系统费用最小的双目标优 化间题 , 研究了支持帕累托最优解成为多用户均衡解的正值匿名路段收费的存在性.进一步 , 分析了不同度量 准则对系统负效用的影响, 衡量了帕累托解处的系统负效用与最优系统性能的差距 , 并给出了该偏差的上界. 由于 cl ar k 和 sum al ee [�31 已经证明, 帕累托有效前沿的端点之一系统时间最优解不能在匿名收费下转化为 多用户均衡解 , 因此本文的研究仅局限干除该端点之外的其余帕累托解. 2 模型构建 假定交通网络 G 二(N ,助 上有 IM }类具有相同行为方式 �且使用同一交通工具的用户, M 为用户类 别集合, � � M ; N 为网络节点集合;A 为路段集合 , a 任A . 设 w 为起讫对 (or igi n- des 七 ina tion Pa ir) 集合 , 二任w ; R �为 OD 对 tv 之间的路径集合 , r 任R诚 嵘 表示 O D 对 二之间第 m 类用户的需求, q = (� ,q岔, �)T ;思 表示 O D 对 二之间路径 : 上第 7n 类用户的流量 , f 一(� ,摄 , �)T ;:罗表示路段 �上第 二 类用户的流量 , v犷二 E 艺 瓜 凡二, 二M = (� ,v罗, �)T ;v�表示路段 a 上所有用户的流量 ,叨 � W r 任R 切 v�= 艺 v罗, �一(� ,帐, �)T ;队 表示第 二类用户的单位时间货币价值, 口二> 0;凡二表示关联矩阵 �饥 任人了 上的一个元素, 如果路径 r 包含路段 a , 其值为 1, 否则为 0.几表示满足流量守恒条件和非负约束的路径流 量和 O D 需求的集合 , 艺 瓜一:;二:0;q;:0;价�R叨,?��m一} (1), � R 二��尹口qf�了了.� 了.,�l� 一一几 2. 1 系统最优模型 在上述符号定义下, 基于时间度量的系统最优问题 (T SO , tim e一 based system optim ization)表示为 1 1 l lfl (了,q )�只T(r, �)一艺 ��(va)二a- (2)a 任A eo st一b a sed 艺 � 汇与 回d?叨 � W � 飞� M 一甘 基于费用度量的系统最优问题 (C SO , system optim ization)表示为 11 l l n (f ,q )�几c( 了,动一艺 艺a 任A m � 八夕�一:,�(��卜艺 � 厂�岔�一�:(山)d公叨 � 卜F 了n � 几夕 � 甘 (3) 其中 ��(�)是路段流量 v �的可微递增函数 , 表示路段 a 上的出行时间;g器(�)是需求量 q器的单调递减函数, 表示 O D 对 二之间第 � 类用户的逆需求函数. T (了,酌 为系统时间, C (了,酌 为系统费用 , 是路网中所有用 户出行成本与总收益之差 , 前者与用户类别无关 , 后者依赖于每一类用户的时间价值. 当路网中仅存在同质 用户时, 式 (2)和 (3)的最优解相同;但在异质用户情形下, 两者的最优解不相同. 式 (3)除了与路段总流量 �相关外 , 还与路段分类流量 �M 相关. 系统工 程理 论 与实践 第 31 卷 2.2 多用户均衡模型 若路网中所有用户都按照个人成本最小化的原则做出路径抉择 , 当同一 O D 对之间被使用路径的出行 成本相等 �并且小于或等于未被使用路径的出行成本时, 路网达到用户均衡 (U E , us er eq ul libr tu m )状态.在 缺少外部干预的情形下, 50 流量分布通常有别于 UE 流量分布.如何通过收费措施, 在保证均衡择路原则的 条件下实现 50 流量分布 , 是本研究的关键. 匿名路段收费下的多用户均衡 (M U E , m ulti一 elass user equilibrium ) l�W 题可以表示为: (�)对_ rv � _ _ 1 _ _ 严了(耀 �Z一总j0 ���x)ctx +魁息澎砂罗一蕊息j0 嵘(?,d�其中 二�表示路段 a 上的匿名收费, �二(� , ��, �)T .以时间和货币单位度量的第 7n 类出行者选择 OD �之间的路径 r 的广义出行时间和费用分别为 �jl.�ee了��d八0尹了.��了�..�c二:一? 厂,�(:�)+华��二, * :R�,,二:w, ��M e滁�一艺(队��(:�)+ �a)�a�, VroR叨,二任环几m �Ma 任A 当匿名收费方案 �实施时, 基于时间度量的 M U E 条件为 �飞.少�1.了ba阿了�了 了.r��z了.�甄��(二��二+蕙会�二 蕙��(二��二+聂淤�二 = 科黔 , 如果跳 > 0, vr 任R �,, 二�代 二 �M 全拼黔 , 如果岚 = 0, Vr 任R二, 二�议 7n 任M 心 ,�= 嵘 (嵘 ), 如果 q岔> 0 , V二任班 m �M 心 ,�七嵘 (嵘 ), 如果 q器= 0, V二任w, m 任M 基于费用度量的 M U E 条件为 (7e) (7d) ��2..�Zeea,b入八�00/汀.�了!�艺瓜:�(:�)�a二+艺 �� 二 a �A a 任A 艺队��(:�)��二+艺二�占二 = 拼黔c, 如果 溉 > O, Vr 任R二, 二�代 爪任M 全拜黔C, 如果 跳 = 0, Vr 任R 叨, 二任w, 7n 任M 拼黔 � = 口�嵘 (嵘 ), 如果 嵘 > 0, Vm 任W, �,任M 拼淤 �全口�衅 (嵘 ), 如果 q岔= 0 , V二 �W, �任M 其中嵘,�和心,c分别是基于时间和费用度量的最小负效用值, 心 ��一黑 {c黔},醋 �� 户黔 �一队 拼黔 �.显然 , 公式 (7)与 (s) 等价. 二二 11 l ln r 任 R � (se) (sd) {e急c}, 且 3 双准则系统最优模型 系统时间和系统费用都可以用干度量系统的性能 以往的研究主要是对系统时间或系统费用进行单目标 优化, 或是针对固定需求下的双目标优化.下面, 我们考虑弹性需求情形下的双目标优化问题, 并研究是否存 在正的匿名路段收费, 支持该双目标优化问题的帕累托最优解为 M U E 解.双目标优化问题为 (忠:�(:;;:{)一( 艺 t�(:�)v�一 a 任A 艺 E 刀: �岔(�)d� 叨 �W 矶 任M 艺 艺 队v罗��(va)一艺 艺 刀岔瓜�:(�)d� (9) a 任A 爪 � M 叨 �W m 任M ) 对于 M U E 问题 (4), 由于 艺�(v�)的可微递增性及 g牙(q黝 的递减性, 目标函数 z( 了,动关于路段流量 � 和 O D 对需求 q 都是严格凸函数 , 因此其均衡路段流量 �和均衡需求 q 是唯一的, 那么, 在均衡解处有唯一 的系统时间T .但是 , Z (f ,动对于二M 不是严格凸的, 所以, 对干给定的收费方案 �, 均衡路段分类流量 二M 不唯一 (均衡路径流量 了也不唯一), 因此系统费用 C 在均衡解处的唯一性不明确. 将公式 (8a )的两端同时乘以均衡路径流量 溉 , 对所有 r 任R 二,二任w 和 � �M 求和 , 可得 艺 艺 队��(va)v罗+ 艺 �av�一艺 艺 �:, ��岔 a 任A m � M a 任A 叨 �飞f m 任 M 增刊 王听, 等:多用户弹性需求网络的双准则系统最优交通分配 由系统费用的定义, 有 C 一艺 艺a 任A m 任材 一 一 尸才口? �a(va)v罗一乞 乞 /n P7n g洽(国)d� 叨 � W � 乙� M � u 一 艺 艺 心勺器一艺叨 任W 爪 �八了 _ 一 严段�a�a一乙 乞 /n 瓜g;(�)d�叨 � W 7刀任M 一U 在均衡状态下, 艺 % :�是路网的总收费额 , 具有唯一性, 且每个 O D 对之间每类用户的最小出行成本 拜淤� a 任A 和需求 q岔也是唯一的, 上式说明系统费用 C 在均衡解处有唯一值. 引理 1 在收费方案 �下的均衡解处, 路径流量 了和路段分类流量 �M 不唯一, 但路段流量 ��o D 对 需求 q �系统负效用 T 和 C 均有唯一性. 将公式 (8c )两端同时乘以均衡需求 嵘 , 对所有 二任W 和 二任M 求和, 可得 艺 艺 瓜嵘(嵘)嵘一艺 艺 �黔c嵘 叨 任H Z m 任M 叨 �下犷 m � M 再考虑逆需求函数 g岔(�) 的单调递减性 , 有 C 一 艺 艺 心,c嵘一艺 队 夕器(�)d � 叨 �W m �M : 艺 艺 心,c嵘一艺 ��va一恿恿关 �a�一恿蕙关队 夕岔(g器)d �叨任W m �M 一 艺 艺 嵘昭 一艺ua v�一艺 艺 队粼q:) 嵘-叨任W m �人了 a � A 叨任林产m �人f 对于一种正的匿名收费锐一属 风嵘尧瓮业(实现系统费用最优!0]), 且va非负,则系统费用�在均 衡解处必非正�同理可证,当路段收费值为二梦一队v�镖扮过(实现系统时间最优的收费政策 �61,为非匿名收 费)时, 系统时间T 在均衡解处也为非正值, 其中 �罗表示路段 �上对第 7n 类用户的收费. 引理 2 在正的收费方案下得到的均衡解点处, 系统时间 T 和系统费用 C 均为负值. 图 1示意性地说明了目标函数值 (T ,C ) 的有效前沿, 两个端点分别对应单目标最优化下的系统费用和 系统时间, 可以分别通过实施匿名收费和非匿名收费实现 [0] .下面, 我们要证明对于有效前沿上的其他帕累 托点 , 是否存在实现它的匿名收费. 图 1 目标函数值 (T , C ) 的有效前沿 3.1 可行路段流量的分解 对任意一个给定的可行路段流 云= (云�, a 任助 T , 考虑下面的最小化问题: lrl 011一.上�1.f�z�吸�(耀��(,,�卜互霖口一罗ta(@a,一恿蕙关队 夕器(�)d �s.t� 艺 艺 艺 咒 �二一�, �任Am � M 留 �不f r 任 R 二 系 统工 程理 论与 实践 第 31 卷 其拉格朗日函数为 Illa 沉 (f ,q )�几L(f, �, �, �) 一艺 艺 队v罗��(��)一艺 艺a �A m 任M 叨 任W m 任M 尸罄j0 阮g:(公)d� 十�*�(��一艺艺艺二�:)十艺艺�:(�一艺二)(12)a �A \ m E M w �W r 任R � / 叨 �W 饥 �M \ r 任R � /最优性必要条件为 �1.尹�21.�jes�1,了八4J口八氏O,土�.土� 111.了l�Z��Z了.�了�.�艺瓜t�(0a )�r一艺凡�一 �器全0,丫r任R二, � �w, m 任M 二{� ���!�(云��一*�)��:一�:}一�, �二:二,叨�二饥�M气a任A 夕 一瓜 g飘嵘 )十户器全0, V二任W, 二任M q器(一队 g飘q黝 + 拼黝 = 0, 物 �城 二 �M 其中入= (入�, �任A) T 和 拼= (拼器,二 �M , � �w )T 分别是条件 (n )和流量守恒约束 干� 嘿一哈� r � 此切 二�W , m :M }的拉格朗日乘子�目标函数(�0)是关于(f,q)的凸函数(�卜严格凸函数),约束条件均为线性函数, 因此 (13)一(16) 是间题 (10)一(n )的最优性充分条件.令 u �= 一入�为匿名路段收费, 科黔写作 拼黔 �, 最优条件 (13)一(16)即等价于 M U E 条件 (sa)一(sd). 定理 1 对任意给定可行路段流量, 存在匿名路段收费将其分解为多用户均衡解. 证明 对于任意给定的可行路段流量 云, 构造基于费用度量的 50 间题 (10 )一(n ), 并设 (f ,酌为其最优 解 , 显然, (f ,q)满足最优性条件 (13)一(16), 即满足 (sa)一(sd), 因此 (f ,q)也是 M U E 解.实现 (f ,q)为多用 户均衡解的条件是实施 �二一入的匿名路段收费.但是 , 该路段收费的正负性尚未确定. 3.2 非负匿名路段收费的存在性 对于双目标系统最优间题 (9), 本节讨论除系统时间最优解之外 , 是否存在非负匿名路段收费使得其他 帕累托解与 M U E 解达成一致.尽管定理 1能将任意可行路段流分解为 M U E 解 , 但仍不能将定理 1 应用于 帕累托解, 因为帕累托最优解还依赖于路段分类流量 �M 和需求量 q. 因此需要解决如下问题:使用匿名路 段收费分解帕累托最优解对应的路段流量时, 对应的均衡路径流量 了和 �M 是否也是帕累托最优的? 这个 问题的答案是肯定的, 如引理 3 所证. 引理 3 除基于时间度量的系统最优解外, 存在匿名收费方案使得其余帕累托解成为多用户均衡解. 证明 设 (j ,司为图 1中帕累托有效前沿上除Tso 之外的任意一点对应的帕累托解, 云为对应的路段 类解即流量, �为使 云成为 M UE 路段流量的匿名收费方案. 假设 (f,司 不是 M UE 解, 令 云对应的 M u E 为 (f ,q), 由 M U E 条件 (sa)一(sd)与系统费用最优条件 (13)一(16) 的等价性 , (f ,q) 能最小化系统费用, C(了,q):c(f,�);由于�给定,令�:一二{蕙(��(云�)+ �)��},它表示O��? �!可第矶用户的最小路径阻抗, 有 g岔(君) 全拼黔, 又因 q 是均衡需求量, 由公式 (7c )一(7d ) 知 拼黔 �全g岔 夕器(心) 全夕器伪器), 即 君 三g黔, 因此, T (f ,q) 冗 艺穿岔�器(�)d�一T(j, �), 由于(i, �) = 艺 几兔(几)一 艺 冗 j0a : �飘�)d�: 冗 (q器), 可 云�t�(云�) 可得 叨任W 爪 �M 是帕累托最优解, 必有 T (了,酌 = T (j,司 且 C (f,司 = 叨任W 爪 任M C( 了�酌.所以, (f ,司 是 M U E 解. 定理 1和引理 3 保证了在弹性需求下, 除了基于时间度量的系统最优解外, 其他帕累托解可以通过匿名 路段收费方案与多用户均衡解达成一致 , 下面进一步证明这种匿名路段收费方案的非负性. 定理 2 除基于时间度量的系统最优解外 , 存在非负匿名路段收费方案支持其他帕累托解成为多用户均 衡解. 证明 设 (j ,司为图1中帕累托有效前沿上除Tso 之外任意一点对应的帕累托解, 由引理 3,存在匿名 收费方案 �支持 (j ,司为多用户均衡解.将等式约束 (n )替换为不等式约束 (17 ) 艺 艺 艺 岚标三几, �任A (l7) m 任M 叨 � W r � R 二 增刊 1 王听, 等:多用户弹性需求网络的双准则系统最优交通分配 因为 (n )式包含在 (17 )式内, 而其他约束没有改变, 所以新优化问题 (10) + (17)的可行域非空 , 设其最优解 为 (f ,动, 对应的拉格朗日乘子为 (入,川. 由于 (f ,动 满足最优性条件 (13 )一(16 ), 即满足 M U E 条件 (sa) - (8d ), 因此 (f ,动 为 M U E 解, 并由均衡需求的唯一陕可知 叮= q , 且 tL = 一入非负.下面证明最优解 (了,动 使得公式 (17)是一个紧约束. 假设约束条件 (17)在 (了,酌处为非紧约束 , 即 (f ,动 对应的路段流量 �三云, 则存在 乙任A , ��< ��.由 于 t�(v �)为单调递增函数 , 则 t�(v�) < t�(云�), t�(v�)v罗< t�(��)v 罗, m 任M , 且 t�(v�)��< t�(��)��, 因此, 有 下式成立 , ��2..�1苦zQOg廿11曰1.JZ吸�井产t�� ��(��)��一� 艺厂a � A 叨 � 协z m �几7 � U q了 一 一 一�器(�)d� < 乙 ta(�a)云a一乙 乙州 � W m 任 M 尸:j0 �;(山)d公 艺 艺 aTn ��(:�):罗<艺 艺 队��(��)�梦 a 任A m 任M a 任A m �人了 (18 )式即到了,动< 到j ,司.又因为 (f ,司是目标函数 (10) 对应于约束条件 (17 )的新优化问题的最优解, 且 (了,酌在新间题的可行域内, 因此有 聂蕙卿��几,刃罗一蕙蕙关 综合 (19)一(20)两式, 可得 艺 � �t�(V�)V:一艺艺厂a � A 爪 �八1 叨任协 , m � M � U �g:(�)d�: � 艺�,�(��)�:一艺 � 厂a � A m 任八夕 叨 � 不f m �八理 � U 口二夕岔(�)d �(20) �g:(�)d�:艺艺�t�(��)�:一艺艺厂a 任A m � M 叨 任币F 饥 �人夕 � � 队 夕岔(�)d� 此即 C (了,引兰C (j ,动= C (j ,动, 这与 (j ,司是帕累托最优解矛盾.因此约束条件 (17 )在最优解 (了,动处 一定为紧约束, 即 (f ,动 对应的路段流量为 云. 4 系绕性能偏差的上界 本节讨论基于时间和基于费用两种度量方式下, 帕累托最优解处系统性能的偏差.令 Tm i�和 Cm i�分别 表示系统最优时间和系统最优费用 , 用 (介 ,q尸)表示帕累托最优解 , (介 ,q动 表示基于时间度量的系统最优 解 , (fc ,qc) 表示基于费用度量的系统最优解. 令 九 i�= m in{ 风 ,二 任M } 表示所有用户的最小时间价值, 风 一 冗 瓜嵘/ E 嵘 表示 O D 对 二任w 之间所有用户的平均时间价值, 风a�= m ax {风 ,二: w }表 m 任 M 仇 任人f 示所有 O D 对之间用户的最大平均时间价值, 风na� = m ax {风 ,m 任M } 表示所有用户的最大时间价值. 显 然 几 i�兰口max 三瓜 ax. 我们研究 到介 ,q尸)和 c( 介 ,q司 分别与它们的最小值 Tm ,�和 Cm i�之间的差距.为了衡量这个偏差, 定义如下两种比率, 称作系统性能偏差因子: a到f ,动 = 公式 (21 )描述了可行解 (f ,动 Tm in T (介 , q二) T (f , g) ac (f ,动 = Cm in T (f , g) C (f ,q) C (fc , qe ) C (f , q) (21) 处的系统负效用与系统最优值的差距. 由于 T (介 , q尸)和 C (介 , q司 均为负 值, 因此 �式介 , q尸)全1 且 �c( 介 , q尸)全1.令 �奋 上 n llnTmT (fc , qe ) T (介 �q二) T (fc , q �) a乙 以n,� C (jc , qe ) C (介 , q二) C (介 , q二) (22) 引理 4 �州介 , q尸)三 �奋, a c( 介 , q尸)三a乙. 证明 由公式 (21升(22) 知, a抓f尸, q尸) 三 a子等价于 到介 , q尸) 三 T (fc , qc) . 使用反证法, 假设 到介 , qP ) > 洲fc , qc) , 考虑到 C (介 , q尸) 全 C (fc , q动, 这就与 (介 , q尸) 是帕累托最优解矛盾 , 所以 到介 , qP )三洲jc , qc )成立.同理可证 ac( 介 , q尸)三a冬 引理 5 风ax 到介 ,q尸)三C (介 ,q尸)三几in到介 ,q尸). 证明 证明过程分为两个部分.首先证明 口max到介 ,q尸)三c( 介 ,q尸). 因 (介 ,q尸)是帕累托最优解 , 由 定理 1 知, 存在收费方案 tL M 一(� , �梦, �)T , 使得 (介 ,q尸)满足 M U E 条件 �黔亡一琴黯��:琴ta(v�)�一V�任R二,切任城?任Ma 七 .性 住七 广1 (23) 系 统工 程理论 与 实践 第 31 卷 当 (介 ,q尸)拼 (介 ,qT) 时, �M 可以是匿名收费方案, 即 �M = �. 将 (23)式两端同时乘以均衡路径流量 思 , 对所有 r 任R �求和 , 可得 一 一 ? I m z丈7, �, � � f了rL 一 � 二理匕尸叨 � � � J r叨 乙 � 月 一 , � 一 月 了护 Tl乙7 一七 月 {创 a 七 J吸 艺 跳 �二�艺t�(珠)艺 思 ��,丫叨任议m 任M (24) r任几叨 a �A r �R � 由 艺 思 = 嵘 且 E 思 凡:= �乳 , (24 )式可写为 r 任R � 一瓜嵘 r 任R � �m ,七nm 一甲厂切 1叨 � �曰 a �A �乳三艺t�(va ):乳, vw 任城爪任M (25) 将(25 )式两端同时减去f0a 牙瓜g黔(二)d二, a �A 再乘以瓜 , 得到 � _ �皿 , q扮 1瓜 �嵘�嵘一艺器v:w 一/n 娥公)叫L a �A � ��- 一 � 兰艺口m ��(v�)v乳- 队 夕器(�)d� (26) 叨爪儿了尹 由于上式两端已为负值, 且风 三凡ax,所以有 切饥产l湘� _ ,�7n�axI �黔嵘一咎成�森 将 (27)式两端对所有 二 1城 7n 1 M /了":(!)d"}:艺!-"(#")#二 口二夕岔(!)d ! (27) 可得 r和儿了求一 口rn ax 艺 艺心,-嵘一艺艺器嵘 叨任H z 爪 1 材 m 1 八了a 1 A / -甲 一 一 尸岔一乞 乙 人 嵘回d山01任似 叨任W / " : i i !t"(?a)V:一艺艺[m 任人l a 任A 叨 1 H / 饥 任入了 . U 瓜 嵘 (!)d ! (28) (25)式左端即凡axT (介 ,g尸 右端为C (介 ,q尸), 因此口max 到介 ,q尸)三C (介 ,q尸)得证. inT (介 ,q ").将 (26)式改写为 今几 厂厂 然后证明 C( 介 ,qP )三 俨 ,ca , 一甲7 切 l切 - - / a 1 A /梦v乳 关气 "",d!兰人 由于 几i"三瓜 , 且上式两端均为负值, 可得 ! #二一琴"二一关气 " #)d#:gmin [蕙!#(二./:沁 }聂亡#(二.0粼 ":(!)d"8 ";(!)d?8 (29) (30) 将 (30 )式两端对 二1 城 7n 1 M 求和 , 可得 艺 艺 "黔嵘一艺 艺 嵘嵘 叨任W m 任M a 任A m 1 M 一i艺厂fi7n " #,山叨任W m C M 0 u :"min7i亡"(#")#"一i艺厂/:";(#)d国La 任A 切任竹 m 任八J / u (31)(31 )式左端即 C (介 , q尸), 右端为 几 inT (介 , q尸), 因此 C (介 ,q尸)三几 in到介 , q司 得证 # 定理 证明 _ 几 a! _ 尽maxJ 口 甲 口 户 气 ) 气 ). 一 口m in 一 瀚 in 由定义可知 (32) "子Q乙= 到介 ,卯)C (fc , qc )T (jc ,q口) C (介 , q二) _ 厂二应卫丝!厂里鱼)到 !又C (jT , q刘/ 又T (fc , qc) / 将引理5应用到(介,qT ),可知C(方,qT )三几in洲介, "), 因此黯韶 -糕;再将引理5(fc, 州,可知几ax州jc ,q"): C(jc ,q"),因此升鲁昌:瓜ax;两式相乘,即得(/2)式# (33) 应用到 由于 a以介 ,q尸) 全1 且 a c( 介 ,q尸) 七1, 由定理 3 可知 a奋三几 ax口 m in "乙三厩 #因此当路网的系瞰能由时间或费用度量时,厩 黔 ,且min {a子,a乙}兰可作为不同准则下系统性能偏差的上界. 5 算例分析 本节用一个由 2 个 O D 对和 5 个路段组成的交通网络说明两种准则度量下系统负效用最优值的差异以 及系统性能偏差因子的大小.各路段的出行时间函数如图 2所示, 为简单起见, 假设网络上仅有两类用户, 且 增刊 1 王听, 等:多用户弹性需求网络的双准则系统最优交通分配 1 0 1 每个 OD 对上仅有一类用户.O D 对 (1,4)之间有第一类用户, 其时间价值是 口:= 1;O D 对 (2,4)之间有第 二类用户, 其时间价值是 几 = 2. 令 了二(fl,儿,儿,八), 其中fl!九!介 和 人 分别表示路径 1! 4 !2* 4 !1 ! 3 ! 4 和 2* 3* 4 上的流量. "= (!, ,乳), ", 和乳分别表示OD 对(1,4)和 OD 对 (2,4)之间的需求,设逆需求函数为或(",)= "若(QZ)= 夕卫卫 !一3 了旦过生!一2! 1 0 / 图 2 算例交通网络 和=分别求解 T SO 一3536.5, C (fT ,g二)T (fc ,叮") = 一3825.31. C SO 两个系统优化间题, 可得:方 = (o,4.4567, 1.0,1.3532), q二= (l, 5.5399), Tn l:"= 一7630.21: fc = (0.6811,3.4866,O ,2.3533), qe = (0.5811,5.8399), Cm i" = 一7637.1,因此 a今 一38 3 6 .8一3 8 2 5 .3 1 = 1.00 3 ,a乙= 一7 6 3 7 .1 一76 3 0 .2 1 = 1 .0 0 0 9 1 . 算例表明, 两类系统性能偏差因子的上界均大于 1, 且小于 O D 对之间最大平均 V O T 与最小 V O T 的 比值 , 验证了定理 3 的结论.这说明两个系统性能偏差因子的上界与路网的拓扑结构和各个路段出行时间函 数无关,仅依赖于用户时间价值的分布,或者说,仅依赖于黔 这个比值,若不能完全得知路网中每一类用户的时间价值,即所有OD对之间各类用户的平均时间价值不能计算时,还可以将这个上界放松为黔 #若路网中的用户是同质的, 即风a!= 口ma!= 几in, a子一a乙= 1, 则表示基于时间度量和基于费用度量的网络 性能优化结果是一致的, 与度量准则无关. 6 结论 对于存在异质用户的弹性需求交通网络 , 当用户被不同的时间价值区分时, 系统时间和系统费用是两种 意义显著的系统性能度量准则, 因此网络优化的两个目标是系统时间最小化和系统费用最小化.本文建立了 两种度量准则的双目标规划 , 同时考虑了系统性能优化的帕累托最优问题 ,证明了除系统时间最优解之外 ,存 在正的匿名收费方案支持其余帕累托最优解转化为多用户均衡解,分析了在异质用户情形下处理网络优化问 题时, 更值得关注的是路段聚合流量而不是路段或路径上的分类流量, 因为分类流量能够在匿名收费方案下 得到自动优化. 此外, 本文引入了两个系统性能的偏差因子 , 用于衡量帕累托最优解处的系统性能与两种准则单独作用 下的最优系统性能之间的差异大小,并给出了两个偏差因子的上界 ,该上界仅依赖于用户的时间价值分布 ,即 所有用户类别中最高和最低 V O T 的比值 , 而与路网的拓扑结构 !路段出行时间函数 !O D 对需求函数和路 径流量分布无关. 参考文献 {1{ Ya ng H , H u ang H J. p rineiple of m arginal一 eost prieing : H ow does it wo rk in a generalroad netw ork!J 2.肠ans- portat ion R esear eh P art A , 1998, 32(1): 45一54. 12} Ya ng H , H uang H J.M at hem at ieal and E eo:lom ie T heory of R oad p rieing[M }.O xfo rd : E lsevier, 2005. = 3{ Leurent F . C ost versus tim e equ ilibrium over a netwo rk = Jl. E uropean Journ al of O p erational R eseareh , 1993, 71(2): 205一221. [4! M 叮et J, H ansen M . C on gestion prieing w itll eontinuously distributed valu es of tim e =Jl# Journal of Tr ansport E eonom ies and P oliey, 2000, 34(3): 359一370. {5 2 N agurn即 A . A m ulti一elas s, mu lti一 eriteria traffi e netw ork equilibrium m odel!J 2 . M athem atieal an d C o;nputer M odeling, 2000, 32(3/4): 393一411. 1 0 2 系统 工程 理论 与实 践 第 31 卷 [6} Ya ng H , H uang H J.The m ulti一elas s, m uiti一 eriteria traffi e netwo rk equilibrium and system optim um problem =J}. 肠 ansportation R esear ch par t B , 2004, 38(1): z一15. = 71 D ialR B #Netwo rk一 optim ized road prieing part l:A par able and a m odel=Jl#O peratio尹 alResear ch , 1999a, 47(1): 5 4一64 . =88 D ial R B .N etwo rk一 optim ized road prieing part Z: Algorithm s and exam ples= Jl.O perationalR esear eh, 1999b , 47(2): 32卜336. =98M ar eotte P , Zhu D L.Equilibrium w ith infinitely m ally diffe rent iat ed elas sesofeustom ers =C :// Com plem entarity a n d Va riat ion al P rob lem s 一 S tat e of th e A rt, P h ilad elp h ia : S IA M , 2 00 0 : 234一25 8 . = 101 N agtlrney A , D ong J.A m ultielas s, m ultieriteria traffi e netwo rk equilibrium m odelwith elas tie dem and{Jl.肠ans- portat ion Re seareh, 2002, 36(5):445一469.= 11} Zhang X N , Ya ng H , H uang H J.M ultielas s m ultieriteria m ixed equilibrium on netwo rks and unifo rm link tolls fo r system optim um [Jl# European JournalofO perat ionalR eseareh , 2008 , 189(1): 146一158. !12} G uo X L , Ya ng H .Userhet erogeneity an d bi一 eriteria system optimu m [J}.肠 ansportat ion Re seareh part B , 2009, 43(4): 379一390. = 131 C lark A , Sum alee A , Shepherd S , et al. O n the existenee and uniqueness offirst best tolls in netwo rks w ith m ultiple user clas ses an d elastiC dem and =J 8#竹ansportm etriea, 2009, 5(2): 141一157.=148余孝军, 黄海军#多用户类多准则交通分配的势博弈与拥挤定价 [sl .系统科学与数学, 201 0, 30(s) :1070一1080 . Yu X J, Huan g H J.Potential gam e ofmu lti一 elas s m ulti一 eriteria traffi e as signm ent and eongestion prieing =Jl. JournalofSystem s Science and M at hem at ieal Seienees, 2010, 30(8): 1070一1080. = 151 刘天亮, 欧阳恋群, 黄海军. AT IS 作用下的混合交通行为网络与效率损失上界 =J].系统工程理论与实践, 2007 , 27(4): 154 一15 9 . L iu T L , O uyan g L Q , H uang H J.M ixed trav el beh av ior in netwo rks w ith A T IS and upper bound of effi eieney 1055=J 8 .System s Engineering 一 T heo即 & prac tiee, 2007, 27(4): 154一159. 1 16} C hen G Y .O n veetor netwo rk equilibrium problem s[Jl.Journalof System s Seienee and System s Engi neering, 2005, 14(4): 454一61. = 171 LiS J, Chen G Y .O n relations betwe en m ultielas s, m ultieriteria traffi e netwo rk equilibrium m odels and veetor va riat ionalinequal ities= J{.JournalofSystem s Seienee and System s Engineering, 2006, 15(3): 284一297 #