Dual-objective reliable network design based on particle swarm optimization
-
摘要: 用离散的路段通行能力变量来刻画路网的随机性, 建立了网络设计的双层规划模型。上层模型为基于路网期望总走行时间最小和路网净经济效益可靠度最大的双目标规划模型, 下层模型为弹性需求下的用户平衡配流模型。采用增设多余需求路段的方法求解下层模型, 采用基于向量的粒子群算法(VEPSO)求解整个双层规划模型。计算结果表明: 所得到的解为一组Pareto解, 路网期望总走行时间和净经济效益可靠性为2个相悖目标; 随着期望总走行时间下降, 可靠度也有所降低; 在可靠度不变的情况下, 减少期望总走行时间, 会导致总投资额的增加。在进行网络设计时, 应结合总投资额和现实需要来选取最优解作为网络设计方案。Abstract: A bi-level programming model of network design was established by supposing the capability of road section to be a discrete random variable. The upper model was a dual-objective programming model, which considered the minimum of network expected travel time and the maximum of network net ecoromic benefit reliability. The lower model was a user equilibrium(UE)with elastic demand. The excess-demand formulation was adopted to solve the lower model, and the vector evaluated particle swarm optimization(VEPSO)was adopted to solve the whole bi-level programming. Analysis result indicates that the outcome is a group of Pareto solutions, network expected travel time and network net economic benefit reliability are contradicting objectives. Network expected travel time decreases, the reliability also decreases. When the reliability keeps invariant, total investment amount increases with the decrease of expected travel time. The optimum scheme for network design should be chosen by combining total investment amount with actual situation.
-
0. 引言
近年来可靠性网络设计问题逐渐引起了人们的重视, 随着社会经济的发展, 出行者要求道路网能提供一个相对稳定的服务水平。但是实际的路网经常面临各种随机交通事件, 必将导致路段通行能力、服务水平的下降, 在这样一种不确定环境下, 用户的路径选择将发生改变, 路网性能指标也将发生改变, 因此, 在城市交通网络的设计中, 考虑路网的可靠性至关重要。而路网总走行时间是衡量路网功能的一个最基本的因素, 因此, 在网络设计中, 考虑可靠性和总走行时间是十分必要的。
文献[1, 2, 3, 4]将路段通行能力变量表达为连续变量来描述路网的不确定性, 其中文献[1]假设路段通行能力服从正态分布, 进而通过平衡条件下的交通流量分配, 利用Monte Carlo模拟法得出路段走行时间和路网总走行时间服从正偏态分布; 文献[2, 3, 4]假设路段通行能力服从均匀分布, 路段走行时间服从正态分布, 在网络设计中考虑了OD对出行时间可靠性。这些文献都是从路段通行能力连续变化的角度建立了单目标的网络设计模型。但是用一个稳定的连续概率分布来描述路网通行能力变量和其总走行时间与实际存在一定偏差, 比如交通事故或交通拥挤引起路段通行能力下降通常发生在1天中的某些时候, 而不会呈现连续变化, 因此, 本文将路段通行能力表示为一个离散的随机变量, 从系统角度考虑路网的净经济效益可靠性[5-6], 建立了以路网可靠度和总走行时间为目标函数的双目标双层规划模型。
城市交通网络设计双层规划的求解方法有MINOS算法[7]、H-J算法[8]、EDO算法[8]、BDA算法[9], 然而, 对于大规模网络而言, 即使是确定性环境下的网络设计也是一个高度复杂的问题, 本文建立的模型研究不确定环境下的路网, 而且是一个包含2个目标的双目标问题, 因此, 本文采用粒子群算法(PSO)来求解。
1. 变量定义
A为路段的集合; va为路段a上的流量, 是路段通行能力的函数; v为所有路段流量组成的集合; ta(·)为路段a的走行时间函数, 假设其只与该路段上的流量和实际通行能力有关; ˉca为路段a的设计通行能力; Ca为路段a的实际通行能力; ˉc′a为改建后路段a的设计通行能力; C′a为改建后路段a的实际通行能力; ca为特定时间内路段a的实际通行能力; c′a为改建后特定时间内路段a的实际通行能力; W为OD对集合; qw、tw分别为OD对w之间的交通需求量和总走行时间; Dw(·)为OD对w之间的交通需求函数; D -1w (·)为Dw(·)的反函数; Pw为OD对w之间的路径集合; f kw为OD对w间路径k上的流量; δa, kw为路径路段流量关系的布尔变量, 如果路段a在路径k上, 则其值为1, 否则为0;ya为路网改建后, 路段a的设计通行能力增加量, 其中ya=ˉc′a-ˉca; y为所有路段流量增加值组成的集合; Ma(ya)为路段a的设计通行能力增加ya所需要的费用; ua为路段a的能力增加值的上限; B为总的投资预算; p(ca)为路段a的实际通行能力为ca的概率; c为ca的集合构成的路网状态; p(c)为路网状态为c的概率, 即
p(c)=∏p(ca)
pal为路段a的实际通行能力衰减为qalˉc′a的概率; qal为衰减系数; c′为c′a的集合构成的路网状态。
2. 净经济效益可靠性定义
在实际路网中, OD对间的出行需求往往呈现随机变化, 净经济效益可靠性就是用来描述弹性需求条件下路网的总体性能。根据文献[5, 6], 弹性需求下, 随机路网的净经济效益为
E(c)=U(c)-S(c)=∑w∈W∫qw0D-1w(x)dx-∑a∈Avata(va,Ca) (1)
路网功能函数为
F(c)={1E(c)≥E*0E(c)<E* (2)
式中: E(c)为路网净经济效益; U(c)为总的用户效益; S(c)为总的社会成本; F(c)为路网功能函数; E*为管理者根据需要给定的净经济效益水平。
路网的净经济效益可靠度为
R=∑cF(c)p(c)
3. 考虑可靠性的双目标网络设计模型
城市交通网络设计问题在流量分配上要考虑用户的路径选择行为, 因此, 一般用双层规划模型来描述。上层模型为决策的选择模型, 在投资资金及可靠性等约束条件下使得路网的某个目标达到最优, 下层模型则为上层决策下的用户路径选择模型。在城市交通网络中, 总的出行时间是出行者关心的一个重要问题, 另外, 从路网使用者来看, 希望路网总的净收益能保持在一定水平。本文用离散变量来描述路段的通行能力, 在上层规划模型中考虑路网的两个性能指标, 目标一使得路网的净经济效益可靠度最大化, 目标二使得路网总走行时间的期望值最小化; 在下层模型中, 用弹性需求下的用户平衡模型来描述路径选择行为, 具体模型如下。
上层模型为
min z1(v, c)=E ∑a∈A[ta(va(C′a),C′a)⋅
va(C′a)] (3)
max z2=R(y, v) (4)
s.t. 0≤ya≤ua (5)
∑a∈A[Μa(ya)]≤B (6) E{∑a∈A[ta(va(C′a),C′a)va(C′a)]}= ∑c′{∑a∈A[ta(va(c′a),c′a)va(c′a)]p(c′)}=
∑c′{∑a∈A[ta(va(qalˉc′a),qalˉc′a)⋅ va(qalˉc′a)]∏a∈Apal} (7)
ˉc′a=ˉca+ya
约束条件式(5)表示对路段a设计通行能力增加值要小于给定的ua, 并为正值; 约束条件式(6)表示总投资额要小于给定的最大投资额B。
下层模型为
minΖ(x,qw)=∑a∈A∫va0ta(x,Ca)dx- ∑w∈W∫qw0D-1w(x)dx (8)s.t.∑k∈Ρwfwk=qw (9) fwk≥0 (10) va=∑w∈W∑k∈Ρwfwkδwa,k (11)
4. 求解算法
考虑到模型的复杂性, 本文采用智能算法——粒子群算法(PSO)来求解双层规划, 直接由解的适应值信息来确定搜索方向, 即得到一组路段设计通行能力增加值后, 代入求解弹性需求下的平衡配流模型, 将求得的路段流量代入上层规划的目标函数, 分别求得路网总走行时间和路网可靠度值, 即为这组解的适应值。其中, 弹性需求下平衡配流模型的求解采用增设多余需求路段的方法, 具体求解算法参考文献[10]。双目标的处理及双层规划的求解步骤如下。
4.1 可靠度和路网总走行时间的求解
随着路网路段数的增加, 路网状态数呈现指数增长, 对下层规划平衡模型的求解次数也呈现指数增长, 因此, 需要对可靠度和路网总走行时间进行近似计算[5]。对净经济可靠度的值, 在找到发生概率最大的前r个路网状态ch(h=1, 2, …, r)后, 可用下式来近似可靠度[5], 即
r∑h=1p(ch)F(ch)≤R≤r∑h=1p(ch)F(ch)+ Ν∑h=r+1p(ch) (12)
当误差项
ε=Ν∑h=r+1p(ch)r∑h=1p(ch)F(ch)
小于指定误差项ε0时, 可用
R=r∑h=1p(ch)F(ch)
来近似可靠度。上面公式中N为路网总状态数。
对于路网总走行时间同样做如下近似处理, 在求得前r′个路网状态后, 可用这r′个状态下的总走行时间来近似, 设前r′个路网状态组成的集合为C, 则路网总走行时间为
E{∑a∈A[ta(va(C′a),C′a)va(C′a)]}≈ ∑c′∈C{∑a∈A[ta(va(c′a),c′a)va(c′a)]p(c′)}≈ ∑c′∈C{∑a∈A[ta(va(qalˉc′a),qalˉc′a)⋅ va(qalˉc′a)]∏a∈Apal} (13)
当误差项
ε′=Ν∑h=r′+1p(c′h)r′∑h=1p(c′h)
小于指定误差项ε′0时, 可用其来近似路网总走行时间。求解路网的前K=max{r, r′}个状态, 其中求解最大概率状态的算法可参考文献[11, 12]。
4.2 基于VEPSO的双层规划模型求解
对于多目标的处理, 常见的算法是目标加权法, 其最大缺点在于对加权的权值没有订立的标准, 因此, 最佳方法是求得问题的Pareto解, 然后根据决策人的偏好程度从一组Pareto解中选择最优解。本文采用的基于向量的粒子群算法(VEPSO)是由Parsopoulos等提出的[13], 其基本思想借鉴了基于向量的遗传算法(VEGA), 将基于目标向量的个体评价方法与PSO算法结合而形成的, 即产生2个子粒子群分别优化2个目标, 并利用另一个子粒子群的信息来更新本粒子群中粒子的位置。具体操作步骤如下。
假设有m条路段需要进行拓宽, 将满足约束式(3)、(4)的路段设计通行能力增加向量(xj1, xj2, …, xjm)视为一个粒子。产生2个子粒子群, 每个子粒子群包含n2个粒子。
(1) 初始化。
产生2个子粒子群, 每个子粒子群包含n2个粒子。子粒子群i中第j个粒子的位置表示为
xij=(xij1,xij2,⋯,xijm)
速度表示为
vij=(vij1,vij2,⋯,vijm)
其经历过的历史最优点为
pik=(pik1,pik2,⋯,pikm)
适应值为Zik; 群体内所有粒子经历过的最优点为
pig=(pig1,pig2,⋯,pigm)
适应值为Zig; Vmax为每维变量的变化范围。
(2) 平衡配流模型的求解。
将子粒子群i中第j个粒子所在位置xijs(s=1, …, m)作为第s条路段的设计能力增加值, 计算改建后的路段设计通行能力C′a。找出发生概率最大的前K个路网状态, 将每个路网状态c′下的路段通行能力c′a代入下层模型, 采用增设多余需求路段的方法来求解弹性需求下的平衡配流问题, 得到路段流量va。
(3) 适应值的计算。
对于子粒子群1中的粒子x1j=(x1j1, x1j2, …, x1jm), 按照第2步计算va, 并代入上层规划, 利用4.1的计算方法求解路网总走行时间, 并将其作为粒子x1j的适应值z1j; 而对于子粒子群2中的粒子x2j=(x2j1, x2j2, …, x2jm), 则求解路网的可靠度, 并将其作为粒子x2j的适应值z2j。
(4) 更新子群中个体的历史最优位置。
将第3步得到的zij与pij处的适应度值Zij(i=1, 2)进行比较, 如果zij≥Zij, 则将pij更新为当前位置(xij1, xij2, …, xijm), Zij更新为zij。
(5) 更新子群中群体历史最优位置。
将Zig与max{Zij}进行比较, 如果max{Zij}≥Zig, 则用适应度值为max{Zij}的粒子所在位置更新pig, 用max{Zij}更新Zig。
(6) 更新粒子的速度和位置, 即
{xJ+11js=xJ1js+vJ+11jsvJ+11js=ψvJ1js+c1γ(pJ2js-xJ1js)+ c2η(pJ2gs-xJ1js) (14)
{xJ+12js=xJ2js+vJ+12jsvJ+12js=ψvJ2js+c1γ(pJ1js-xJ2js)+ c2η(pJ1gs-xJ2js) (15)
式中: 变量c1、c2等于2;γ、η为在[0, 1]区间内均匀分布的随机数; ψ为惯性因子; J为迭代次数。
(7) 判断粒子的可行性。
如果更新后的粒子所在位置(xij1, xij2, …, xijm)溢出了变量的容许取值范围, 则粒子仍保持原来的位置。
(8) 迭代终止条件。
设置终止条件为算法迭代次数, 若未达到终止条件, 转第2步。
5. 算例分析
构造一个简单网络来验证模型和算法的有效性, 见图 1, 该网络包含一个从①到④的OD对, 4个节点, 5条路段, 其中路段3为单向路段。
路段走行时间采用BPR函数, 即
ta(va,ca)=t0a[1+0.15(va/ca)]4
式中: ta0为路段的自由走行时间。OD对需求函数为qw=200-tw。假设由于外部原因, 改建后的路段通行能力c′a呈现离散分布, c′a衰减为qalˉc′a的概率为pal。预备对路段3、5进行改建, 设其设计通行能力最大容许增加值为ua, 投资函数为
Μa(ya)=βy2a
式中: β为系数变量。假定总投资限额为400单位, 管理者给定的净经济效益水平为3 000单位, ε0、ε′0均为0.01, 其余各参数见表 1。依据上述算法, 利用MATLAB计算, 得到结果见表 2。
从上述结果可以看出, 所得到的解为一组Pareto解, 解2与解1相比虽然总走行时间有所减少, 但可靠度有所下降, 总投资金额增加, 解2与解3相比, 虽然总走行时间增加, 但总投资金额减少; 解3与解1相比, 总走行时间减少, 可靠度有所下降, 总投资额增加; 模型中只考虑了路网总走行时间和路网可靠度两个目标, 决策者在做出决策时可以结合考虑各个方案的总投资来综合做出决策。
表 1 网络参数Table 1. Network parameters路段编号 t0a ˉca β ua qal pal 1 5 40 1.0 0.20 0.7 0.80 2 4 40 1.0 0.30 0.6 0.70 3 2 80 3 15 1.0 0.25 0.8 0.75 4 5 20 1.0 0.10 0.7 0.90 5 3 40 7 10 1.0 0.15 0.8 0.85 表 2 计算结果Table 2. Computational results解的编号 路段编号 设计通行能力增加值 路网期望总走行时间 路网可靠度 总投资额 1 3 8.142 1 512.7 0.82 210.23 5 1.274 2 3 7.171 1 482.8 0.78 225.22 5 3.183 3 3 4.885 1 454.0 0.78 258.10 5 5.162 6. 结语
在进行道路网络设计时, 往往要考虑多个部门的不同目标, 因此, 通常是一个多目标问题。由于路网的不确定性直接影响出行者的行程质量, 在进行网络设计时, 考虑可靠性显得尤为重要。本文用离散变量来描述路段通行能力的不确定性, 建立了基于路网总走行时间和路网可靠度2个目标的双目标网络设计模型, 并用智能算法PSO进行了求解, 得出了一组Pareto解。该模型在建立时假设路段的供给能力呈现离散分布, 出行需求呈现给定函数关系下的弹性需求, 而事实上需求与供给是相互作用相互影响的, 本文是一种简单化的假设, 因此, 在进一步的研究中, 应探讨需求与供给之间的动态联系, 将两者统一起来再建立模型。在求解算法上, 复杂度较高, 在后续研究中, 对算法细节, 如参数的设置、迭代终止条件等有待进一步改进。
-
表 1 网络参数
Table 1. Network parameters
路段编号 t0a ˉca β ua qal pal 1 5 40 1.0 0.20 0.7 0.80 2 4 40 1.0 0.30 0.6 0.70 3 2 80 3 15 1.0 0.25 0.8 0.75 4 5 20 1.0 0.10 0.7 0.90 5 3 40 7 10 1.0 0.15 0.8 0.85 表 2 计算结果
Table 2. Computational results
解的编号 路段编号 设计通行能力增加值 路网期望总走行时间 路网可靠度 总投资额 1 3 8.142 1 512.7 0.82 210.23 5 1.274 2 3 7.171 1 482.8 0.78 225.22 5 3.183 3 3 4.885 1 454.0 0.78 258.10 5 5.162 -
[1] DI MITRIOU L, STATHOPOULOS A, TSEKRIS T. Reliable stochastic design of road network system[J]. International Journalof Industrial and Systems Engineering, 2008, 3(5): 549-574. doi: 10.1504/IJISE.2008.018232 [2] 许良, 高自友. 基于路段能力可靠性的城市交通网络设计[J]. 中国公路学报, 2006, 19(2): 86-90. doi: 10.3321/j.issn:1001-7372.2006.02.015XU Liang, GAO Zi-you. Urban transport network design based on link capacity reliability[J]. China Journal of High-way and Transport, 2006, 19(2): 86-90. (in Chinese) doi: 10.3321/j.issn:1001-7372.2006.02.015 [3] 许良, 高自友. 基于出行时间可靠性的城市交通网络设计[J]. 系统仿真学报, 2008, 20(2): 494-498. https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ200802054.htmXU Liang, GAO Zi-you. Urban transportation network design based on travel time reliability[J]. Journal of System Simula-tion, 2008, 20(2): 494-498. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTFZ200802054.htm [4] LO H K, TUNG Y K. Network with degradable links: capacity analysis and design[J]. Transportation Research Part B: Methodological, 2003, 37(4): 345-363. doi: 10.1016/S0191-2615(02)00017-6 [5] 刘海旭, 蒲云. 弹性需求随机路网的可靠性[J]. 公路交通科技, 2005, 22(7): 97-100. doi: 10.3969/j.issn.1002-0268.2005.07.025LI U Hai-xu, PU Yun. Reliability of stochastic road network with elastic demand[J]. Journal of Highway and Transporta-tion Research and Development, 2005, 22(7): 97-100. (in Chinese) doi: 10.3969/j.issn.1002-0268.2005.07.025 [6] YANG Hai, HUANG Hai-jun. Principle of marginal-cost pricing: how does it work in a general road network-[J]. Transportation Research Part A: Policy and Practice, 1998, 32(1): 45-54. doi: 10.1016/S0965-8564(97)00018-9 [7] GERSHWI N S B, TAN H N. Hybrid optimization: optimal static traffic control constrained by drivers'route choice behavior[R]. Cambridge: Massachusetts Institute of Tech-nology, 1978. [8] CHIOUS W. Bilevel programming for the continuous trans-port network design problem[J]. Transportation Research Part B: Methodological, 2005, 39(4): 361-383. doi: 10.1016/S0191-2615(04)00085-2 [9] SUH S, KI M T J. Solving nonlinear bilevel programming models of the equilibriumnetwork design problem: a compara-tive review[J]. Annals of Operations Research, 1992, 34(1): 203-218. doi: 10.1007/BF02098180 [10] GARTNER N H. Optimal traffic assignment with elastic demands: a reviewpartⅡalgorithmic approaches[J]. Trans-portation Science, 1980, 14(2): 192-208. doi: 10.1287/trsc.14.2.192 [11] WAKABAYASHI H, IIDA Y. Upper and lower bounds of terminal reliability of road networks: an efficient method with boolean algebra[J]. Journal of Nature Disaster Science, 1992, 14(1): 29-44. [12] YANG C L, KUBAT P. Efficient computation of most prob-able states for communication networks with multimode com-ponents[J]. IEEE Transactions on Communications, 1989, 37(5): 535-538. doi: 10.1109/26.24607 [13] PARSOPOULOS K E, VRAHATIS M N. Particle swarm optimization method in multiobjective problems[C]∥ACM Special Interest Group on Applied Computing. Proceeding of the2002ACM Symposium on Applied Computing. Madrid: ACM, 2002: 603-607. -