（运筹学与控制论专业论文）带收费的网络系统优化决策方式.pdf

悃翟 摘要 在现代社会中，由于通讯手段，交通方式的日趋发达，人与人之间的联系越来越紧 密，关系错综复杂，社会生产生活当中也出现了越来越多的网络结构。我们常见的基础 网络支撑着我们整个经济和社会活动，提供了商业，科学，技术，社会系统以及教育所 需的各种基础设旌。而无形的逻辑网络，如人与人的信息交流网络等，也是基础网络的 有力补充，帮助人们完成更为复杂的活动或任务。网络结构无处不在，他们的作用超乎 想象，离开了网络。人类将无所适从。 由于网络系统在人类生活占据着越来越重要的地位，其效率就显得尤为重要。然而， 在网络系统中，参与的实体数量很多，各自拥有自己的行为方式和目的，网络经过长期 的运行，所达到的静态用户均衡，只是每一位网络用户不能通过单方面的行动改善自己 的状况而已。网络系统作为一个整体，在大多数情况下，并不能够达到系统整体的最 优。所以，做为政府或者网络决策者，有义务采取一定的措施控制网络系统，使其能够 达到系统的优化，这一背景引发了本文的研究。 本文研究的主要基础是网络均衡理论，即静态用户均衡的一系列均衡条件及求解模 型。站在政府决策者的角度，试图利用道路收费政策来控制网络结构达到理想的用户均 衡状态。文中主要对两类网络进行了介绍及分析，交通网络和供应链超级网络。对交通 网络中负的外部性。尾气污染造成的环境问题通过道路收费进行控制。在其成本函数可 分离的情况下，利用尾气污染定价和双层规划模型达到了两种不同的控制目标，即使尾 气污染不超过某一限制标准和污染最小化的目的。在网络为非对称的情形下，建立了下 层为变分问题的双层规划，利用罚方法对其求解进行了分析。对于供应链超级网络，目 的是通过交易税收，对各个交易路线k 的单位交易量收取一定的税收，各不相同，使得 嘲络系统中实体总的效益最大化，文中是使得所有生产厂商和零售商的利润之和最大。 同样建立了下层为变分闯题的双层规划，并用实例分析了税收政策的有效性。总之，本 文的主要贡献在于，提出网络系统道路收费政策利用双层规划模型确定最优控制目标， 并在双层规划模型下分析了求解方法，这一最优化的系统目标也为决策者提供一定的决 策依据。 关键词：用户均衡，系统优化，双层规划，供应链超级网络 中图分类号：c 9 3 1 1 第i 页洪5 3 页 英土鹄管 a b s t r a c t i nm o d e r ns o c i e t y , v a x i o u sc o m m u n i c a t i o nm e a n sa n dt r a n s p o r t a t i o nm e t h o d sa r ed e v e l o p i n gw i t hv e r yr a p i ds p e e d ，t h e r e8 x em a n ym o r ec o n n e c t i o n sa m o n gp e o p l en o wt h a n s e v e r a ly e a r sa g o ，l o t so fn e t w o r kf r a m e w o r k ss h o wt h e i rb e n e f i t st oo u rp r o d u c t i o na n d l i f em o r ef r e q u e n t l y , a n dt h e yh a v em a n yf o r i n s b a s i cn e t w o r k ss u p p o r to u re c o n o m i c a n ds o c i e t ya c t i v i t i e s ，a n dp r o v i d ev a r i o u si n f r a s t r u c t u r e sf o rb u s i n e s s ，s c i e n c e ，t e c h n o l o g y , a n de d u c a t i o n t h o s en e t w o r k sw h i c hh a v en od e f i n i t ef o r m s u c h i n f o r m a t i o ne x c h a n g e n e t w o r ka m o n gp e o p l e ，a r ea l s ot h es u p p l e m e n t st ob a s i cn e t w o r k ，a n dt h e yh e l pu s8 c o m - p l i s hm o r ec o m p h c a t ea c t i v i t i e so rt a s k s n e t w o r ki se v e r y w h e r e ，i n c l u d i n gt r a n s p o r t a t i o n n e t w o r k ，c o m p u t e rn e t w o r k ，f i n a n c i a ln e t w o r k ，a n dc o m m u n i c a t i o nn e t w o r ke t c ，a n dp e o - p l eu t i l i z en e t w o r kt or e a h z em o v e m e n to fg o o d sa n df u n d s ，t r a v e lo fp e o p l e ，a n dm a n y i n f o r m a t i o ne x c h a n g e w ec a ns a yt h a to u rs o c i e t yw i l lb ei nm e s sw i t h o u t n e t w o r k s i n c en e t w o r ks y s t e m sb e c o m em o r ea n dm o r ei m p o r t a n ti nh u m a ns o c i e t y ，t h ee f f i c i e n c yi nn e t w o r ka l s ob e c o m eac r i t i c a lp r o b l e mt h a tp e o p l es h o u l dc o n s i d e ra b o u t i n n o r m a ln e t w o r ks y s t e m ，m i l l i o n so fe n t i t i e sa r ei n v o l v e di no n en e t w o r k ，a n dt h e yh a v en o c o m m o nb e h a v i o ra n do b j e c t i v e a sar e s u l t ，t h en e t w o r kc a r lj u s tr e a c hau s e re q u i l i b r i u m ( n o tt h es y s t e mo p t i m i z a t i o n ) ，w h i c hm e a n st h a tt h e r ea r en on e t w o r ku s e r sw h oc a n i m p r o v eh i s h e rs i t u a t i o nt h r o u g ha n yu n i l a t e r a la c t i o n s h e n c e ，a sa w h o l es y s t e m ，i nm o s t c a s e s ，n e t w o r kc a nn o tr e a c hi t ss y s t e mo p t i m i z a t i o no b j e c t i v e a sg o v e r n m e n to rn e t w o r k p o l i c ym a k e r t h e yh a v et h er e s p o n s i b i l i t i e st ou s es o m em e t h o d st oi n f l u e n c et h en e t w o r k u s e re q u i l i b r i u m ，a n df i n a l l ym a k ei tt or e a c ht h es y s t e mo p t i m i z a t i o n h e r e ，t h es y s t e m o p t i m i z a t i o no b j e c t i v e si n c l u d et o t a lo p e r a t i o n sc o s tm i n i m i z a t i o n ，n e t w o r kn e g a t i v er e - s u l t sm i n i m i z a t i o n ，o rm a x i m i z a t i o no fr e v e n u e so fa l le n t i t i e si nn e t w o r k t h i sb a c k g r o u n d i n v o k e dm yr e s e a r c ho nt h i st o p i c t h eb a s i so fr e s e a r c ho ft h i st h e s i si so nn e t w o r ke q u i l i b r i u mt h e o r e m ，i n c l u d i n gs o r t i e e q u i l i b r i u mc o n d i t i o n sa n ds o l v i n gm o d e l si ns t a t i cu s e re q u i l i b r i u m f r o mt h ep o i n to f p o l i c ym a k e r w et r yt on s et o l lp o l i c yt oi n f l u e n c et h eu s e re q u i l i b r i u mi nn e t w o r k ，a n dl e t i tt or e a c ht h es y s t e mo p t i m i z a t i o no b j e c t i v e s w em a k es o m ei n t r o d u c t i o na n da n a l y s i so n t w ok i n d so fn e t w o r k ，o n ei st r a n s p o r t a t i o nn e t w o r k ，t h eo t h e ri ss u p p l yc h a i ns u p e r n e t w o r k w em a i n l yc o n s i d e ra b o u tt h et r a n s p o r t a t i o nt o o l s e m i s s i o nn e g a t i v er e s u l t s ，a n dc o n t r o l t h ee m i s s i o nt h r o u g hs t r e e tt o l lp o l i c y w h e nt h et r a v e lc o s tf u n c t i o n sa r es e p a r a b l e w e 第i i 页，共5 3 页 d e t e r m i n et h ep r i c eo fu n i te m i s s i o nt om a k et h et o t a le m i s s i o nn o te x c e e d i n gt h es t a n d a r d ， a n dw ee s t a b l i s h e do n eb i l e v e lp r o g r a mt om i n i m i z et h et o t a le m i s s i o ni nt r a n s p o r t a t i o n n e t w o r k w h e nt h en e t w o r ki sa s y m m e t r i c ，w ee s t a b l i s h e da n o t h e rb i l e v e lp r o g r a mw h o s e l o w e rl e v e li sav a r i a t i o n a li n e q u a l i t yp r o b l e m ，t h e nu s e dp e n a l t ym e t h o dt oa n a l y z et h i s m o d e l a sf o rt h es u p p l yc h a i ns u p e r n e t w o r k ，t h es y s t e mo p t i m i z a t i o no b j e c t i v ei st om a x - i m i z et o t a lr e v e n u e so fa l lm a n u f a c t u r e r sa n dr e t a i l e r s t h r o u g ht a x e so ne a c ht r a n s a c t i o n l i n k ，i n c l u d i n gc l a s s i c a lt r a n s a c t i o nm o d ea n de c o m m e r c et r a n s a c t i o nm o d e ，w er e a c ht h i s o b j e c t i v e w ea l s oe s t a b l i s h e da b i l e v e lp r o g r a mw h o s el o w e rl e v e li sav a r i a t i o n a li n e q u a l i t y p r o b l e m ，a n dt h e nu s e da 1 1e x a m p l et ov e r i f yt h ee f f e c t i v e n e s so ft r a n s a c t i o nt a xp o l i c y k e yw o r d s ：u s e re q u i l i b r i u m ，s y s t e mo p t i m i z a t i o n ，b i l e v e lp r o g r a m m i n g s u p p l yc h a i ns u p e r n e t w o r k 第i i i 页，共孙页 第一章引言弟一早ji 苗 1 1问题背景 网络系统在人类社会生活中占据着重要地位，支撑着我们整个经济和社会，提供了商 业，科学，技术，社会系统以及教育所需的基础设施。它无处不在，包括交通网络，计 算机网络，金融网络，通信网络等，人们通过网络实现物的运输，人的旅行，资金的转 移，以及各种信息的广泛交流，可以说，离开了网络，人类的生活无法想象。 交通网络为我们提供了穿越空间的方法，我们从而可以去会晤客户，拜访朋友。旅行 并拓展我们的视野等，而且它使我们的生产系统得以实现，使得原材料的运输，以及最 终产品分销到每位顾客手中成为可能，并且我们拥有各种各样的方式实现人和物的空间 转移，如飞机，火车。汽车，轮船等。通讯网络使我们无国界，无地域限制地与同事 朋友，亲人交流感情，信息，数据等，通过通讯方式的一些革新。例如因特网和移动电 话的发展，通讯网络甚至改变了我们今天生活，工作和学习的基本方式。能源网络对网 络经济的存在至关重要，它为交通网络，通讯网络，金融网络等提供必需的动力储备。 金融网络将社会中闲置的资金集中起来，为那些需要资金迅速扩张的企业，实体提供关 键的资金支持，使得他们能够最好的满足顾客的各种需求。 以上所介绍的几种网络只是人类社会中众多网络系统中的很少一部分，由此_ 口j 见，我 们每天都生活在网络系统中，而且网络的确给我们带来了非常多的好处和便捷。但是， 网络系统1 i 光给我们带来好处，它们也会产生负效应，在为我们提供便捷的同时它们产 生了其他成本，或造成不良后果，这是我们希望尽量避免的。以交通网络为例，若道路 容量有限，它会产生交通堵塞成本，并且交通网络的长久运行会产生环境问题，如汽车 尾气是污染大气的罪魁祸首，同时交通工具的过度使用还会造成能源危机。因此，如何 在有效利用网络系统的同时，控制负效应造成的不良影响，使网络系统可持续的发展就 成为至关重要的问题。作为政府或网络设计者，为了达到网络的长久持续发展，这些负 效应的影响是不得不考虑的，本文就是从决策者的角度考虑此j a - j 题，设法使网络作为一 个整体系统达到其最优，尽量减少负效应。 在典型网络中，如交通网络，网络中的客流是旅行者自行决定得出的，每位旅行者 白行选择所行道路，使自己的效用值达到最大，这样选择的结果是，每位旅行者达到了 自己的最优化，即所谓的用户均衡，但做为整个网络系统来讲。并未实现系统整体的最 优化，或者网络系统并为使其负效应最小化。这样的情形，并不是网络设计者希望看到 的，他们需要考虑采取某种手段来控制或影响网络使用者的选择，影响用户均衡，从而 第1 页，共5 ：；页 使网络系统达到系统最优化，这里的系统最优化，可以包括网络系统总成本的最小化， 或网络系统某一负效应造成的不良后果最小化两种最优a 由此，从网络设计决策者的角 度出发，引发了本文的研究。 1 2 研究背景 本文研究的主要基础是网络均衡理论，即静态用户均衡的一系列均衡条件及求解模 型。这一理论目前已受到广泛的关注和应用，尤其在政府制定道路交通的宏观政策方面 发挥着重要的作用。为了克服交通网络中负的外部性，包括交通堵塞，环境污染，等不 利影响，政府制定交通网络相关政策时往往需要考虑非常细致的网络结构及交通用户特 征等因素，因此网络均衡理论的完善和发展为解决这类问题提供了有利的工具。 1 9 5 2 年，w a r d r o p 提出了用户均衡和系统最优两个均衡条件，使得交通系统中的均 衡条件有了明确的定义1 9 5 6 年b e c k m a n n 等人提出的在成本函数可分离情况下的网络均 衡最优化方法，进一步促使了网络均衡理论有了飞跃性的发展，使其在实际问题中的应 用得到了长足的进步。最近，在利用道路收费控制达到系统最优这一研究方向受到普遍 重视，以下几位教授的工作尤为突出。a n n an a g u r n e y 在环境污染的网络外部性方面提 出了一些较新的理论。主要是对汽车尾气污染进行收费，从而控制环境污染的总量，她 采用的工具主要有变分不等式方法和对偶理论，但在道路费加入网络后，她未考虑用户 均衡的稳定性，从而使得最终结果不一定能达到预期的控制污染的目的。h a ly a n g 的研 究领域也是利用添加道路费使得用户均衡达到系统晟优，他这里的系统最优是整个系统 的成本或交通时间最小，但他的研究是在可分离情况下进行的，主要是基于对偶理论 的，对用户旅行时间函数也作了充分的假定，保证了将道路费加入网络后用户均衡的稳 定。d o n a l dw h e a r n 在用户均衡和系统最优的转化上，同样采用道路收费方法，在这一 情形下，研究了非对称情况下的道路收费策略集合的凸性等特征。 a n n an a g u r n e v 的研究成果只是使得交通工具尾气污染不超过某一固定标准，没有进 行尾气污染的最小化分析而且并没有对多类用户的情形进行分析，但是讨论了对称和 非对称网络两种情况。h a iy a n g _ j ：j 论的目标与前者不同，其目标是使得网络系统的总交 通成本或时间达到晟小化。但仅考虑带可分离成本网络的情况，在非对称下无法得到有 效方法。d o n a l dw h e a r n 贝, 1 在非对称情况入手，分析了收费方法的一些可能，但并未得 出具体方法实现最小化系统成本。本文将从对称和非对称网络两个角度考虑，并考虑有 限维多类用户的情形，希望得出有效的模型及解法使得网络负的外部性最小化。 1 3 本文研究的问题 在交通网络中，网络负的外部性较为明显和突出包括交通工具尾气污染问题，堵塞 第2 页 盐5 3 页 成本等。本文将主要针对交通网络当中的收费理论进行分析和研究，着重对尾气污染这 一负效应进行控制，主要手段是通过对交通道路加收道路费，改变交通网络成本结构， 影响网络用户选择道路时所作的决定，从而最终改变网络达到的静态用户均衡，使得减 少尾气污染的目标得以实现。并在论文最后对供应链超级网络的均衡进行了分析，同样 试图利用网络道路收费的方法使得整个供应链超网达到整体系统最优。总体来讲，本文 主要希望通过收费理论控制用户均衡达到网络设计决策者希望的系统最优。 第二章讨论带可分离成本函数的交通网络，首先对尾气污染和系统总成本最小化两个 不同目标分别介绍了简要方法，然后对于尾气污染的最小化控制目标，利用双层规划求 解尾气污染的最小化问题。写出在对称网络下双层规划的模型然后对交通成本函数作 定假定，得出一个有效的求解算法，并通过实例进行验证。第三章则考虑非对称的交 通网络，利用变分不等式表示网络用户均衡，然后将所设道路收费加入均衡当中，达到 非对称网络的双层规划模型，最小化尾气污染，或是一个带均衡条件约束的数学规划， 利用罚方法对其求解进行了分析。第四章介绍了收费理论在供应链超级网络中的应用， 构造了模型并分析了均衡的稳定性等，绘出实例作简要介绍。 1 4 用户均衡与系统最优 控制用户均衡达到系统最优，这是本文讨论的晟终目标，这里将对其中的用户均衡和 系统最优两个概念进行介绍。 用户均衡，即网络系统没有一个统一的决策者，每位网络用户根据自己的实际情况， 以及网络当中各个道路的交通时间，成本以及拥挤程度，决定自己的行走路线，使自己 效用达到最大化。达到这一均衡是需要一个过程的，最初用户凭借自己初次判断进行选 择，之后，每位用户会根据自己选择的情况和其他人选择的情况，以及网络的状况，重 新进行决策，经过一个充分长的时期后，整个网络系统会达到一种静态均衡，每位用户 都没有可能使自己的效用变大了，这是一种相对稳定的状态。 系统最优则是指网络系统的总交通成本，时间最小化，或整个网络系统福利最大化， 负的外部效应最小化，这一目标下的网络状态并非种均衡状态，只是政府或网络设计 决策者希望达到的一种状态。一般情况下，达到系统最优时的网络流状态，同普通的用 户均衡下的网络流状态是不一样的，因此，在决策者的角度上，需要考虑如何控制用户 均衡，使得用户均衡时的网络状态恰好就能够达到系统最优。 1 9 5 2 年，工程i ) 币w a r d r o p t 解了交通网络中用户的几种可能的选择行为，提出了交通 网络中的两个原则，后人命名为w a r d r o p 原则： 在一个o d 对中，所有用到的路线上的旅行时间是相同的，并且不超过未被用到的 那些路线k 的旅行时间 第3 页，共5 3 页 整个交通网络系统中，平均的旅行时间达到最小 第1 条原则就是用户均衡，第2 条即系统最优，如下图所示 而两而鬯鲨塾隔 丰哇十0 加对 中已羽所 有髀姥謦l 拔 删勰相馨 # 且毋小 畦个鬟魏甲 嚣嫒 j 酵删 艇d 1 北 图1 - 1 交通网络中用户的两类行为模式 1 5 本文基本假定条件 以下所列的假定条件为全文所讨论问题的假定条件，每一章节具体的假定在此不作介 绍。 假定l ：木文只讨论网络静态均衡，并不对达到这一静态均衡的过程进行讨论，既本文不 讨论动态均衡的问题。 假定2 ：交通网络中，o d 对己知，并且每一o d 对之间每类用户的旅行需求是确定的。 假定3 ：本文在考虑多类用户时，仅考虑有限维多类用户，不考虑无限维情况，即用户类 别是有限的，并非无限的进行分类。 第4 页，共5 3 页 第二章可分离成本函数的交通网络收费理论 2 1 可分离成本网络及其用户均衡的介绍 首先，对描述交通网络结构的参数和记号进行说明。我们考虑这样+ 个网络g = ，引，表示网络中所有节点的集合，l 表示网络中所有有向边的集合，n 表示连接一 对节点的一个有向边，p 表示连接一个o d 对的一个路径，即一些有向边组成的一个序 列，这里的节点就是城市中的一些目的地或起点，有向边指道路和街道，而路径指连 接一个起始点和一个终点的一个可能路线。r 表示连接o d 对w 的所有可能路径的集 合，p 表示网络中连接o d 对的所有路径的结合，并且我们假定网络中有l ，个o d 对，是 已知的。坼表示路径p 上的用户流量，d 表示有向边a 上流量，路径流量组合成一个路径 流的列向量。碎，n p 表示刚络中的所有路径数，边上流量名也组合成一个边流量的列 向量f 磁，n 表示网络中的所有有向边数。丸表示o d 对 上的旅行需求，本文假定所 有的妃是完全确定的，不考虑弹性需求的问题。 流量守恒等式 路径和有向边间的流量守恒等式如下， 丘= 却，v a l ，( 2 - 1 ) p p 其中，如果有向边。是路径p 中的一条边，则= 1 ，否则= 0 。表达式2 1 表示边。上的 流量等于所有包含边a 的路径p 的流量总和。 另外，流量还必须满足下面的条件， 氏= 昂，物彬 ( 2 2 ) p e 凡 表示在某一o d 对甜之间的所有路径流量的总和等于这一o d 对之间的旅行需求d 。 用户成本函数 用来表示有向边上的用户旅行成本，g 表示路径p 上的用户旅行成本，假定有向边 用户旅行成本函数如下， c a = c d ( ，) ，v a l ，( 2 - 3 ) 这里的成本函数是比较通用的形式，不仅与厶有关，且与其他边上的流量有一定关系。 第5 页，共5 ：) 豆f 乖一量_ 斧葛泛f 、匹簪的：碗嘎嚣敉牵峰。e 另外，g 也可以用下面的等式来表示， 勺2 c g ( ，) ，坳只 ( 2 - 4 ) 那么，做为一个整体系统，网络系统的总成本为，。c 。( f ) f a 。 用户均衡 我们需要确定一组用户路径流量矿( 或用户有向边流量f + ) ，使得它们满足流量守 恒等式2 1 和2 2 ，并且满足非负约束，同时满足w a r d r o p 的第一条用户均衡的原则，即夺 一个o d 对中，所有用到的路线上的旅行时间是相同的，并且不超过未被用到的那些路 线上的旅行时间，这时的交通网络状态就是达到了用户均衡。根据上面介绍的参数和标 记，我们可以将w a r d r o p 的用户均衡原则写成如下形式，以下是刃的用户均衡条件，对于 每一个o d 对w ，和每一个路径p 只。 ( 2 - 5 ) k 表示达到用户均衡时，o d 对加的之间的最小旅行成本。因此，从上面均衡条件可 以看出，用户均衡并不存在明确的最优化概念，因为此时所有旅行者以非合作的方式独 立得行动，直到通过单方面的行动，他们无法再改善自己的状况，此时就得到了上面均 衡条件所规定的用户均衡。 对称网络及可分离成本函数的定义 本章可分离成本函数交通网络收费理论的讨论范围是在对称网络中进行的，这里的对 称网络的定义是这样的。对于交通网络中的旅行成本函数c ( ，) ，若【鼹= 务】，v a ，6 l ， 则这样的交通网络称其为对称网络。在对称情况下，当用户旅行成本函数为c d = c 。( 厶) ，妇l ，即c o 仅与，口相关，与网络中其他道路上的流量无关，则这种旅行成本函数 就称作可分离的。在这种特殊的可分离成本函数的网络情况下，有一个非常好的研究结 果，为了求解满足均衡条件的网络流，1 9 5 6 年，b e c l a n a n n ，m c g u i r e ，和w i n s t e n 对于可 分离成本函数的网络，建立了一个最优化问题来得到这一用户均衡解，规划如下， r a i n 。寸岛( z ) d x s t 艇凡= 九， 厶= p p z p ， z 。0 第6 页 共础页 v w w v a l v p p ( 2 - 6 ) ( 2 7 ) ( 2 - 8 ) ( 2 - 9 ) 0 旺 = 晖 玎盯 知 1 l 一 ，-_j-_l g 在此规划中的目标函数2 6 是为了求解用户均衡而构造的，可以用凸规划算法来求 解，它并不包含任何经济含义。约束条件2 。7 和2 8 是流量守恒等式，最后一个约束条 件2 9 为网络流量的非负约束。在非对称网络中，并不能得到如上的最优化问题来求解用 户均衡，我们将在第三章来讨论这种非对称网络的问题。 2 2 收费理论控制用户均衡达到系统成本最小化 对于网络系统这一整体来说，政府或网络设计者希望系统整体达到的目标是多种多样 的，如系统总体运行成本最小，堵塞成本最小，或者是交通工具尾气污染最小化，也可 能是控制这些成本或负的外部性不超过某个标准。在本节中，我们将讨论系统总体交通 成本最小化的目标，假定交通网络是对称的，成本函数是可分离的，不失一般性，在本 节中将这里的成本函数用时间函数t 。代替，考虑了时间和成本对不同用户的效用问题， 据此对j h j 户分了有限维类进行讨论。讨论的主题是通过道路收费控制用户均衡，使得其 均衡状态恰好是系统成本最小化，我们的f i 的是确定每条道路或街道上的收费标准，影 响网络中的旅行成木函数，从而影响用户均衡来达到目的，同时这一手段并不影响交通 网络的拓扑结构。 2 2 1 一类用户的系统成本最小及用户均衡 在本小节中，主要希望在一类用户的情形下，向大家介绍系统最优的一些概念，以及 控制手段，在下一节将对有限维多类用户情形进行分析，更具理论及应用价值。在这早 将成本函数用旅行时间函数来代替，整个网络的系统最优模型( s o p ) 如下所示， m i n 。lt 。( 厶) 丘 a t 艇忍吻= 如， v w 彬 丘= p p z p ， v oe l ， 0 ，坳j d ( 2 - 1 0 ) ( 2 一1 1 ) ( 2 一1 2 ) ( 2 1 3 ) 在这一模型中，目标函数本应为交通成本最小化，b p m i n 。；l 成。( 丘) 厶，p 表示此 类用户的时间价值，即他们将单位时间等价于卢的资金成本，但南于这里只有一类用户， 所以目标函数简化为上面规划中的形式，而不影响求解的结果。存这里，不失一般性， 我们对时间函数t 。作如下假定，假定t 。c 1 ，为凸函数，且关于厶严格递增。则我们会有 如下结论， 定理2 1若如( 厶) c 1 ，且为凸函数，并关于厶严格递增，则规划( s o p ) 为严格凸规 划。 第7 页，共5 3 页 莩一幸；叮钞隽业：运载曲毫或i 终，电零嚷论 证明：首先证明目标函数。l k ( 厶) 厶为严格凸函数，由于，满足约束条件2 1 1 至l , 1 2 1 3 ， 约束条件均为线性的，则，可行集q 为凸集。即证明目标函数为严格凸就是要证明下式， 彦t ( ，2 ) f t f ： f 1 ) + ( ，2 一 ) r v ( f t t ( f 1 ) ) ，v ，1 ，2 q( 2 1 4 ) 上式等价于 t 。( ，2 。) ，2 。 1 2 t 。( f l 。) f l 。+ 【t 。( ，1 。) + t ：( ，1 。) 。 ( ，2 。一，。) ( 2 - 1 5 ) a e la e ld l 左式一右式= t o ( 2 。) 一t 。( 。) 一t o ( a 。) 。( ，2 。一 。) t ：( 。) ( 如。一f l a ) f z 。一t o ( a 。) 。( 正。一f l 。) = ：( 五。) ( ，五一 。) 2 由于屯( 厶) 为严格递增函数，则上式中艺呖。) 0 ，v a l ，且已知 ，2 ，则上式大 于0 ，故目标函数为严格凸，同时约束条件均为线性的，则这一规划为严格凸规划。口 推论2 1 看屯( ，0 ) c 1 ，且为凸函数t 并关于丘严格递增，则规划( s o p ) 存在犀优解 且唯一，其局部最优解即全局最优，且( s o p ) 的k - t 点必为其整体约束极小点。 据定理2i ，此推论显然成立，不需证明。 接下来，我们写出规划( s o p ) 的k t 条件，即全局最优解满足的条件，z ”，”是最 优解的充分必要条件是，对每一个o d 对w ，每一个路径p ，z ”，f s o 满足如下条件 础e t ( f s o | 、, + 薹c 警艄 冀谋霉三： c 枷， 而用户均衡条件为， 驴艄 茎筹兹描 陋忉 从这两个最优条件的比较可以得1 t i ，当我们给每条道路或街道n 加上一个通行 费= 芦 堕o 世y o a ，a 8 。时，网络上的旅行时间函数就会变为 o ( a ) = t o ( a ) + 紫謦( 2 - 1 8 ) 第8 页共5 3 页 在这种新的旅行时间情况下，用户均衡条件与系统最优条件完全相同，那么用户均衡 得出的网络均衡状态就恰好是系统最优化条件，也就是实现了控制用户均衡达到系统最 优化的目标。这里需要补充的是，存前面k ( 厶) c 1 ，且为凸函数，并关于厶严格递增的 假定下，用户均衡的解存在且唯一，因其化为最优化问题时的目标函数严格凸，保证了 系统所达到的用户均衡就一定是系统最优时的网络流状念，同时，这种用户均衡也相当 的稳定，即使网络流量短期内有剧烈的变动，经过一段时期，最终都会回到这一唯一的 用户均衡状态。这种性质非常重要。失去这种性质，常数收费理论将不能保证达到好的 效果，因为，常数收费理论不能改变时间函数的单调性质，用户均衡解不能确保唯一， 均衡不稳定，政策制定者就可能达不到预期的系统优化效果，收费失去效果。如果希望 在用户均衡不稳定情况下仍然达到控制效果，可能需要采用函数型收费理论，即道路收 费与当时的网络系统状态有关。这一情形在实际应用中很难实现，木文不作讨论。 2 2 2 有限维多类用户网络系统成本最优 本节我们将讨论当有多类用户，他们的时间价值互不相同时，如何通过收费理论控 制他们的道路选择，达到系统最优。首先，我们对多类用户网络某些记号的改变作一 些说明，我们将用户根据他们拥有的不同时间价值分成m 类，如行人，自行车，助动 车，汽车等类别，用m 表示某一类用户，屈。表示第m 类用户所感知的时间价值，口表示 第m 类用户在道路a 上的流量，由于我们可分离的假定条件，这时的时间函数分类别讨 论，髫= 学( 臂2 ) ，z ? 表示第m 类用户在路经p 上的流量，d 翟表示o d 对w 之问第m 类用 户的旅行需求，其他记号同上节所示，在这一网络系统中，对每一个o d 对w ，每一条路 径，每一类网络用户，下面条件成立即为用户均衡， 乏酬胍隹麓搽霉三： 陋埘 在旅行时间函数屯( 口) 可分离的假定下，以上用户均衡可化为最优化问题，利于求 解。其目标函数为， m 膨i n 跗) = a e lm 量= lz 圩脚 ( 2 2 0 ) k 为网络可行流的集合，我们延用上节的假定条件，时间函数亡m ( ，) c 1 ，凸，且 关于，? 严格递增，在这种情况下，用户均衡存在且唯 a 只需证明以上规划模型为严格 凸规划即可，而k 为凸集，则只需证明目标函数严格凸。 定理2 2若学( 口) c 1 ，并关于口严格递增，则函数f ( ，) 为严格凸。 第9 页，共5 ：j 页 焉一晕可铲；再戎寻函数曲：避洲终，蒂理论 证明：t y ( 口) 伊，易知函数f ( ，) 二阶连续可微， 由于是可分离的，则v 2 f ( ，) 为一对角阵，对角元素为当善掣， 而t 8 ( f 2 ) 为严格递增的，则坐：掣 0 ，即对角阵对角元素全部大于o ，即其特征值 全部大于0 ， 则v 2 f ( ，) 为正定阵。 而，k ，k 为开凸集，因此。函数f ( ，) 为严格凸函数。 口 我们现在将网络用户的时问函数转化为成本考虑系统最优的情况，使由时间转化来的 系统总成本最小化，每类客户采用自己独有的时问价值妇k ，这一网络的系统最优化模型 如下所示， m i n 吼。m ：1 风髫( 口) 凹 s t p 凡z 孑= 四， v w w m = 1 ，2 口= p p 够， v a l ，m = 1 ，2 ， 窄0 ，却p ，m = l ，2 ， ，m m ： m ( 2 - 2 1 ) ( 2 2 2 ) ( 2 2 3 ) ( 2 2 4 ) 我们延续使用上节的假定条件，时间函数t y ( 口) c 1 ，凸，且关于口严格递增，在 这种情况下，容易证明上述系统最优化模型为严格凸规划，其全局最优解存在且唯一， 也即上面规划的k t 点。我们写出其最优k t 条件如下， 风a e l 旧( 口) + 口挈】。廊，如果带 。，跏p ，m = l ，2 ，m 风旧( 口) + 口警 蟠，如果带：o ，坳只m 一1 ，2 ，m n l 叫d ( 2 2 5 ) ( 2 2 6 ) 这时，我们制定这样的道路通行费。 口：胁，, 。m _ d t y 而( ：- 2 ) ，v ael ，而：1 ，2 ，m ( 2 - 2 7 ) 能够控制用户均衡状态达到系统总成本最小的最优条件，从而达到管理者的目的。 然而，应该注意到，这里在道路。上所添加的会因为用户类型的不同而收取不同的道路 费，并不是统一的，这主要是由这一网络的实际情况决定的。但是由于行人，自行车， 助动车，汽车等拥有不同的道路，因此对他们实施不同的收费并不矛盾，政策的实施也 比较容易，同时，由于加上道路收费后。并不改变原来时间函数的连续可微及严格递增 的性质，因此达到的用户均衡状态也是唯一的，就是系统最优状态，所以它是稳定的， 收费政策是有效的。 第1 0 页，共5 ： 页 2 2 3 实例分析 在本节中，我们将以一个简单的网络系统为倒，介绍道路收费的求解过程我们考虑 如下图所示简单的网络结构，在这个网络中，仅有1 个o d 对，那就是( 1 ，2 ) ，网络中存 围2 - 1 网络结构1 在两类用户，他们分别具有不同的时间价值卢= ( 2 ，3 ) ，另外这两类用户在o d 对之间的 旅行需求分别为d = ( 6 ，5 ) ，网络中有2 条道路，分别形成1 条路径，对于2 条道路，对于第 一类用户，它们分别的时间函数如下， t ：= 露+ 8 ，瑶= 2 ，：+ 3 对于第二类用户， t ：= 露+ 1 3 ，t 2 _ 2 詹+ 8 由此网络结构，我们写出其系统最优模型如下， 求解得到系统最优解， ，、 ，_ ( 笏笏) 第1 类用户两条路径上面的流量分别为( 1 9 61 7 6 ) ，第2 类用户两条路径上流量 为( 5 25 2 ) 。然后我们确定道路收费，由上节得到的结果2 2 7 ，得出该网络中第一类用 户的道路收费，r 1 = ( 萼警) t ，第二类用户的道路收费，r 1 = ( 萼 1 5 ) t ，当添加上这个 道路费之后，由于不同类用户对道路收费感知不同，我们将这些收费化为等价时间后， 对他们道路选择产生不同的影响，两类用户此时感知的时间函数是不同的，计算后得 知，对第一类用户时间函数变为， 畦：，：+ 罢； 第1 1 页1 共5 3 页 落 + 斤p 侥 + 宏 + 豇& 黝= = n h 露后 蚓“肛， + 蘑p 芦 + 露 十 是 岛 营 “ 蟊：2 矗+ 娑 第二类用户时间函数变为， 龟：甓+ 娶； 埒= 2 疗+ 1 3 在这样的改变过的时间函数作用下，通过检验可以证实，用户最终达到的均衡状态依 然是， 卜1 1 毛9 7 2 61 州7 6 、i 。 这时的所有网络用户耗费的总时间转化为感知的成本数值为3 3 3 丢，而在时间函数未 经过改变时，用户均衡状态为， 气印7 3 驯1 1 。3 ) 所有用户耗费的总时间转化为感知的成本数值为3 4 4 ，可以看出，系统实现了优化， 因此，收费政镶有效。况且，由政府收取的道路费可以重新投入到交通网络的改善中， 2 3 交通工具尾气污染控制的道路收费决策 作为网络政策的制定者，网络系统自身效益最大化只是决策者需要考虑的一方面的问 题，如何让网络系统持久生存发展，长期发挥效用才是最关键的。这就要求网络系统与 周围环境能够互相适应，协调地发展。但是网络系统往往具有其负的外部性，也就是对 周围社会，环境造成不利的影响。这时，就需要我们通过一定手段来控制网络系统这种 有危害的外部性。 城市交通嘲络中产生的汽车尾气有很大的负面影响，据不完全统计，全球二氧化碳释 放量的1 5 来自于汽车等交通工具，5 0 的氮氧化合物来自于汽车尾气，它们与其他污染 物混合可以造成酸雨，大气当中的一氧化碳有9 0 来自交通环节，世界上5 亿辆汽车每年 要产生1 0 万亿立方米的废气( t h ee c o n o m i s t1 9 9 6 ) 。从这些数字可以看出，交通网络中产生 的汽车尾气已经成为最重要的大气污染源之一，不进行切实有效的控制措施，任其发展 下去，人类的牛存王f 境将会受到极大的威胁。要解决这一棘手的问题，一方面从技术的 角度，可以通过改进交通工具效率和使用替代能源来解决，另一方面可以通过有效的交 通网络设计和交通流控制缓解这一问题。在本节中，我们将站在政策制定者的角度考虑 问题，试图通过对交通流的控制达到目的，主要手段是在不同路段上设置尾气污染费。 本节采用成本函数，在道路成本函数可分离，且严格递增的假设条件下，介绍了尾气污 第1 2