城市交通网络设计问题中双层规划模型、方法及应用

第４卷第１期２００４年２月

交通运输系统工程与信息

Ｊｏｕｒｎａｌ　ｏｆ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｓｙｓｔｅｍｓ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　ＴｅｃｈｎｏｌｏｇｙＶｏｌ．　４

ＦｅｂｒｕａｒｙＮｏ．　１

２００４

文章编号：１００９－６７４４　（２００４）　０１－００３５－１０户；；；；；；；；．；；；；＞，１系统工程理论与方法ＶＶ

、．．．．．．．．．．．．．．．．．．……《．产

城市交通网络设计问题中双层规划模型、方法及应用

高自友，张好智，孙会君（北京交通大学交通运输学院，北京１０００４４）

摘要：综述了城市交通网络设计问题中双层规划模型及求腆算法的以往研究成果和最新研究进展及其实际应用中的相关问题，并据此指出了一些需要进一步研尧的问题及未来的研究方向．

关键词：双层规划；城市交通网络；离散交通网络设计；连续交通网络设计；算法中图分类号：Ｕ１２

Ｂｉ一ｌｅｖｅｌ　Ｐｒｏｇｒａｍｍｉｎｇ　Ｍｏｄｅｌｓ，Ａｐｐｒｏａｃｈｅｓ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ　ｉｎ　Ｕｒｂａｎ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｎｅｔｗｏｒｋ　Ｄｅｓｉｇｎ　Ｐｒｏｂｌｅｍｓ

ＧＡＯ　Ｚｉ一ｙｏｕ，ＺＨＡＮＧ　Ｈａｏ－ｚｈｉ，ＳＵＮ　Ｈｕｉ－ｊｕｎ（Ｓｃｈｏｏｌ　ｏｆ　Ｔｒａｆｆｉｃ　ａｎｄ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ，Ｂｅｉｊｉｎｇ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，　Ｂｅｉｊｉｎｇ　１０００４４，Ｃｈｉｎａ）

ＡｂｓｔｒａｃｔａｄｖａｎｃｅｓＩｎ　ｔｈｉｓ　ｐａｐｅｒ，　ｗｅ　ｃｏｎｄｕｃｔ　ａ　ｃｏｍｐｒｅｈｅｎｓｉｖｅ　ｓｕｒｖｅｙ　ｏｎｏｆ　ｂｉｌｅｖｅｌ ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌｓ，ａｌｇｏｒｉｔｈｍｓ ａｎｄｔｈｅ　ｐａｓｔｐｒａｃｔｉｃａｌｓｕｒｖｅｙ，ｄｅｖｅｌｏｐｍｅｎｔｓ ａｐｐｌｉｃａｔｉｏｎｓａｎｄｉｎｒｅｃｅｎｔ

ｕｒｂａｎｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｎｅｔｗｏｒｋ　ｄｅｓｉｇｎ　ｐｒｏｂｌｅｍｓ．　Ｍｏｒｅｏｖｅｒ，ｂａｓｅｄ　ｏｎ　ｔｈｉｓｆｕｔｕｒｅ　ｒｅｓｅａｒｃｈ　ｄｉｒｅｃｔｉｏｎｓ　ａｒｅ　ｐｒｏｐｏｓｅｄ．ｓｏｍｅｏｐｅｎ　ｐｒｏｂｌｅｍｓ　ａｎｄ

Ｋｅｙ　ｗｏｒｄｓ：ｂｉｌｅｖｅｌ　ｐｒｏｇｒａｍｍｉｎｇ；　ｕｒｂａｎ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｎｅｔｗｏｒｋ，ｄｉｓｃｒｅｔｅｄｅｓｉｇｎ；　ｃｏｎｔｉｎｕｏｕｓ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｎｅｔｗｏｒｋ　ｄｅｓｉｇｎ；　ｓｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ．ＣＬＣ　ｎｕｍｂｅｒ Ｕ１２

ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｎｅｔｗｏｒｋ

１简介 一般地，城市交通网络设计问题（ＮｅｔｗｏｒｋＤｅｓｉｇｎ　Ｐｒｏｂｌｅｍ，　ＮＤＰ）是指这样一个最优投资决策问题：在一定的投资约束条件下，考虑交通出行者行为选择情况的同时，改善某些路段或在交通网络中添加新的路段等，以使整个交通网络达到某种系统指标最优的目的（高自友等，２０００）．通常ＮＤＰ被分为两种形式：离散网络设计问题（在现有交通网络中添加新的路段）和连续网络设计问题（改进现有路段的供给能力）．还有些学者提出了混合网络设计问题，即同时考虑在网络中添加新的路段和改进现有路段，混合网络设计问题被认为更切合实

际问题，不过其求解也更加复杂困难，至今这方面的研究成果较少．除此以外，在传统的交通网络设计问题基础上，运用各种交通规划和管理手段，如交通信号设置、拥挤道路收费、辅路匝道控制、公交网络设计等等，改善整个交通网络的系统性能，目前也被认为是综合交通网络设计问题的研究范畴，现已吸引了大批国内外学者在此方面进行了研究（Ｃｅｄｅｒ和Ｗｉｌｓｏｎ，　１９８６；Ｆｅｒｒａｒｉ，　１９９５；Ｙａｎｇ和Ｂｅｌｌ，　１９９７；高自友等，２０００）． 在城市交通系统中，政府部门对交通基础设施投入了大量资金和财政补贴，采用建设新的道路、改善已有路段、优化信号设置、更新交通工具等等

收稿日期：２００３－１１－１２资助项目：国家杰出青年科学基金（７０２２５００５）．高自友：北京交通大学教授，博士生导师，俄罗斯自然科学院外籍院士．交通运输系统工程与信息２００４年２月措施以维护整个交通系统的正常运行，满足日益增长的交通需求；而公众则调节自己的出行行为以适应这些给定的交通设施．也就是说在政府部门为出行者提供交通基础设施之后，出行者根据具体的交通状况来决定是否出行，是乘公交车出行还是乘私家车出行，选择出租车还是骑自行车等．由于ＮＤＰ决策过程中涉及到政府部门和公众的相互作用，是一个典型的双层决策问题，因此双层规划则成为描述交通网络设计问题的理想工具． 过去的３０年间，大批学者用双层规划方法研究了交通网络设计问题．Ｆｒｉｅｓｚ　（１９８５）　，　Ｍａｇｎａｎｔｉ和Ｗｏｎｇ（１９８４），Ｂｏｙｃｅ（１９８４）、Ｙａｎｇ（１９９８，２００１）等人曾分别对ＮＤＰ中的双层规划模型与算法的研究成果作了综述．本文的目的是对双层规划模型、算法在交通网络设计问题中的应用研究进行综述，回顾其过去的重要成果，概述其现在的最新进展，展望其未来的研究方向．中，下层规划一般使用用户最优平衡配流模型．最常用的是固定需求的用户平衡（ＵｓｅｒＥｑｕｉｌｉｂｒｉｕｍ，　ＵＥ）配流模型，也有学者使用基于ｌｏｇｉｔ分布的随机用户平衡（Ｓｔｏｃｈａｓｔｉｃ　ＵｓｅｒＥｑｕｉｌｉｂｒｉｕｍ，　ＳＵＥ）配流模型（Ｃｈｅｎ和Ａｌｆａ，　１９９１；Ｄａｖｉｓ　１９９４）等．考虑到网络设计是长期投资的规

划建设，交通需求会随着网络的改善而变化，研究ＮＤＰ时使用弹性需求的ＵＥ模型和ＳＵＥ模型应能更切合实际（Ｙａｎｇ和Ｂｅｌｌ，　１９９８）．另外也有的学者应用运量分布和流量分配的组合模型（Ｂｏｙｃｅ和Ｊａｎｓｏｎ，　１９８０　）、基于网络能力可靠性的ＰＵＥ（ｐｒｏｂａｂｉｌｉｔｙ　ｕｓｅｒ　ｅｑｕｉｌｉｂｒｉｕｍ）配流模型（许良和高自友，２００３）等等． 考虑网络能力可靠性的ＰＵＥ配流模型如下：

２交通网络设计问题的一般双层规划模型 网络设计过程中，政府部门决定如何设计科学合理的规划方案，以使整个交通系统拥挤程度最小或社会经济效益最大，但是它不能控制出行者的出行选择行为，而出行者随着网络特性的改变及时调整自己的出行方式，以使自己的出行费用最小．这是一个典型的领导者一追随者对策问题，可用数学模型描述如下： ｍｉｎＦ（ｕ，ｖ（ｕ））

ｓ．　ｔ．艺ｈ，一ｐｄ－， ｄ　ｗ〔Ｗ ｃ任尸１１艺艺８－，　ｈ，一ｆ　，ｄ“ＣＡｒｓ　Ｅ　ＲＳＰ　Ｅ　Ｐｒｓ

气［Ｅ（Ｔ，）一ａ－＝Ｏ，ｙ　ｐ　Ｃ　Ｐ－，Ｖ　ｗ６Ｗ

ｓ．　ｔ．　Ｇ（ｕ，ｖ（ｕ））镇０其中ｖ　（ｕ）由下面规划求得ｍｉｎ　ｆ（ｕ，ｖ）

ｓ．　ｔ．　ｇ（ｕ，ｖ）簇０这里Ｆ（ｕ，ｖ（ｕ））和ｕ表示政府部门的目标函数和决策向量，Ｇ表示政府部门决策向量的约束函数；ｆ和ｖ表示出行者的目标函数和决策向量，９表示出行者决策向量的约束函数．

３下层网络用户行为选择模型 一般地，网络特征的改善会引起网络交通流量的改变．如果不考虑网络用户的出行行为，一味地在网络中添加新的路段或改进原有路段的通过能力，有时反而有可能导致整个网络拥挤程度的增加，这就是著名的Ｂｒａｅｓｓ诡异现象（Ｂｒａｅｓｓ，１９６８；Ｙａｎｇ和Ｂｅｌｌ，　１９９８）．传统的ＮＤＰ双层规划模型 Ｅ（Ｔｐ）一７ｒ－）Ｏ，ｙ　ｐ〔Ｐ－＇，　｀ｄ　ｗ　ＥＷ ｈ　ｐ　（ＧＯＶＴ，一．ｌ）镇ＯＮ　ｐＥＰ－，ｙ　ＷＥＷ 九镇（ｋａ＋ｕａ）［６󰀀（１一ａ．）＋ａ．］，Ｖ　ａ　Ｃ－　Ａ ｈｐ）。，ｂ　ｐ　Ｅ　Ｐｗ，ｄ　ｗ　ＥＷ式中ｋａ—路段ａ原有能力； ｕａ—上层决策变量； ｄ　ａＥＡ，ｆ，ｈｐ—路段ａ和路径ｐ上的流量； ｄ＇— Ｏ－Ｄ对ｗ之间的交通需求； ７ｒ＂＇— Ｏ－Ｄ对ｗ之间的最小阻抗； Ｐｗ— Ｏ－Ｄ对ｗ之间的所有路径的集合； Ｅ（Ｔｐ）—路径ｐ上期望阻抗； Ｂａ—设计能力的实现率； ａｓ—路段ａ的能力可靠性． Ｇａ。和Ｙａｎｇ（２００３）研究了考虑环境因素下的平衡配流模型，赵彤和高自友（２００３）在此基础上研究了环境污染限制下的网络设计问题，见文献「２３］［２４］［４５］［４６１． 上述配流模型都是假设路段阻抗函数之间是相互独立的，即路段ａ上的阻抗只取决于ａ上的流量ｆａ，而与其它路段上的流量无关．这一假设在某些情形下是无效的一般情况的路段相互影响的非对称平衡配流模型可用变分不等式方法表示．最一第１期城市交通网络设计问题中双层规划模型、方法及应用般的形式如高自友等（２０００）所描述：寻找平衡路段流量ｆ＊　Ｅ　Ｄ，使得对所有的ｆＥｄ２有 ｔ（ｆ＊　，ｕ）＇（ｆ一ｆ‘））０其中 ０二｛ｆ　ｉｆ＝Ａｈ，Ａｈ＝４，ｈ＞，　０｝式中ｔ（＂）—路段阻抗向量函数； ｈ—路径流量； ｑ— Ｏ－Ｄ需求量； △—代表路段／路径关联矩阵； Ａ—代表Ｏ－Ｄ对／路径关联矩阵． 如果ｔ（ｆ，ｕ）严格单调，则平衡路段流向量ｆ’是唯一的，而平衡路径流量向量不一定是唯一的，包含于如下的一个凸的多面体集合中（（Ｐｏｌｙｔｏｐｅ　） ：‘二｛ｈ｝Ａｈ＝ｆ＊，Ａｈ＝ｑ，ｈ）０｝式中ｆ’是由变分不等式模型求出的平衡路段流量・Ｆｒｉｅｓｚ　（１９９２，１９９６）　，Ｉ，ｉｍ　（２００２　）、赵彤和高自友（２００３）等研究了下层为变分不等式约束的ＮＤＰ双层规划模型及求解算法．一个混合整数非线性双层规划问题．４．２上层目标函数 进行交通网络设计的目的就是通过建设新的道路或改善已有道路的能力，从而达到满足日益增长的交通需求量，降低系统阻抗，缓解交通拥挤程度，使社会效益最大等目的一般地说，常用的上层目标函数有如下４种： （１）固定需求条件下的系统出行阻抗最小． 大部分的网络设计问题都假设Ｏ－Ｄ需求量是固定的，因此很自然，网络设计的目的就是在满足投资预算约束及其它约束条件下使系统总阻抗最小，或者使网络系统总阻抗和总的投资额之和最小（高自友等２０００），即 ｍｉｎ　ｚ一艺，“（ｆａ（ｕ），ｙａ）　ｆａ（ｕ）

ｓ．　ｔ．艺Ｇ．　（ｕ．）　Ｇ　Ｂ

４上层优化问题４．１上层问题决策变ｆ 交通网络设计问题可分为在现有网络中添加新路段的离散形式、扩展原有路段能力的连续形式和把二者相结合的混合形式．下面分别介绍其决策变量． 离散形式的上层决策变量用来表示如何选择要在网络中添加新的路段，它主要应用于新道路系统的设计问题中・ＬａＢＬａｎｃｅ　（１９７５），　Ｂｏｙｃｅ和Ｊａｎｓｏｎ（１９８０），Ｃｈｅｎ和Ａｌｆａ（１９９１）等先后研究了离散网络设计问题，上层问题极小化系统总阻抗，下层问题前者使用运量分布和流量分配的组合模型，后者使用随机增量配流技术． 连续形式的上层决策变量表示如何改善现有路段的能力，它特别应用于信号优化设置和拓宽道路等问题中．事实上，国内外学者关于ＮＤＰ的研究大部分都是集中于连续网络设计问题，因为其决策变量是连续的，可以用灵敏度分析等方法计算出平衡路段（径）流量对它的导数，相对比较容易设计算法，遗憾的是难以求解大型交通网络设计问题． 实际交通规划活动中往往需要同时决策如何在网络中添加新路段和如何改善原有路段，而不是将二者分开考虑，此即所谓的混合网络设计问题．混合形式的上层决策变量既包括离散决策变量又包括连续决策变量．混合网络设计问题一般表述为或 ｍｉｎ　ｚ式中一艺Ｃａ　（ｆ．（，），．ｖａ）ｆａ（，）＋０，万ＧＱ（，、）ｔａ（ｆａ（ｕ），ｕａ）—路段ａ的阻抗函数；ｆａ（ｕ）—路段ａ的流量，ａ　Ｃ－　Ａ； Ｇａ（ｕａ）—路段ａ能力增加的投资函数，ａＣ－Ａ； Ｂ—投资预算； Ｂ，—匹配投资费用与系统总阻抗单位的系数； ｕ—网络设计问题上层决策变量，满足相应ＮＤＰ约束． （２）固定需求条件下的网络备用能力最大． 采用网络备用能力最大作为网络设计的目标函数有许多优点，例如可以明确避免困扰网络设计问题的能力诡异现象，能够简化计算，能够预测改进后的网络所能容纳的最大需求量（Ｙａｎｇ和Ｂｅｌｌ，１９９８；Ｇａｏ和Ｓｏｎｇ，２００２）． （３）弹性需求条件下的用户盈余（ＣｏｎｓｕｍｅｒＳｕｒｐｌｕｓ）最大． 如果在弹性需求条件下网络设计问题中仍然将目标函数设定为使系统总阻抗最小或使网络系统总阻抗和总的投资额之和最小，由弹性需求的基本概念可知：为了达到使系统总阻抗最小的目的，就会导致Ｏ－Ｄ需求量降低至最小，当然相应的投资费用也会很少，而这一结果并不是交通规划人员所希望的．用户盈余这一概念最初是由Ｋｏｃｕｒ和Ｈｅｎｄｒｉｃｋｓｏｎ在１９８２年提出的，是一个经济上的