带平衡约束的连续网络设计的模型与算法谌永荣【摘要】建立了包含上、下层问题的带平衡约束的模型以解决连续网络设计问题，上层问题是一个标准的网络设计问题，下层问题是用变分不等式描述的用户平衡配流问题。
针对该模型设计了基于遗传算法的求解方法并通过实例对算法进行验证，试验结果表明：该算法是有效的，能够较快地求解此类网络平衡设计问题。
%A model for continuous network design problem with equilibrium constrains is established in this paper. In the model, the upper problem is a standard network design problem, while the lower problem is a user equilibrium condition stated by a variational inequality. A new algorithm for the model is also proposed, and numerical results show that it is effective and can solve the problem quickly.【期刊名称】《中南民族大学学报（自然科学版）》【年(卷),期】2013(000)002【总页数】3页(P123-125)【关键词】连续网络设计;遗传算法;变分不等式;用户平衡【作者】谌永荣【作者单位】中南民族大学数学与统计学学院，武汉430074【正文语种】中文【中图分类】O221.2网络平衡设计问题[1]可分为两类:一是对已有路段改造以增加其通行能力,另一则是添加新路段.前者被称作“连续网络设计问题”(CNDP)[2,3] ,这里的“连续”是指路段通行能力的增加量是连续的; 而后者被称作“离散网络设计问题” (DNDP)[4-6].对于连续网络设计问题,由于问题中的目标函数是连续的(甚至还可以进一步要求它是可微的、凸的),便于数学处理，所以一直以来受到大家的关注，并且已经有了一些很好的求解算法[7].但在前面的这些文献中，都是假定网络中各路段的行驶费用只与本路段的流量有关，这在很多情况下是合理的，此时问题可建成一个二层规划模型，然后对二层规划模型提出算法.但实际网络中，很多时候各路段的行驶费用不仅与自身的流量有关，还与其他路段上的流量有关，而且路段费用向量关于路段流量变量的雅克比矩阵是非对称的，这时网络设计问题中下层的用户平衡就不能写成一个数学规划模型，本文中将此时的下层用户平衡条件采用变分不等式来描述，并针对该模型设计了求解方法,模型求解中,上层问题采用遗传算法，而下层问题采用对角化方法求解.1 连续网络平衡设计模型考虑道路网络G=(N,A)，其中N为网络节点集，A为有向弧集(路段集合)，xa为路段a上的交通量，它们组成的向量为x=(…，xa,…);ca为路段a的现有容量，即为该路段允许通过的最大交通量；ya为路段a上的能力增加量，它们组成的向量为y=(…,ya,…)；ta(x)为路段a上的行驶时间(或费用)，它是向量x的函数，即路段a上的行驶时间(或费用)不仅与自身交通量有关，还与其他路段交通量有关；它们组成的向量为t(x)=(…,ta(x),…)；为OD对(r,s)间路径k上的交通量；；f=(…,frs，…)；Ga(ya)为路段a的能力增加的投资费用函数；为路段与路径关联矩阵，若路段a在OD对(r,s)间路径k上，则否则为0；Λ=(aij)为OD对与路径关联矩阵，若路径j是O-D对i之间的一条路径，则aij=1，否则aij=0；qrs为OD 对(r,s)间的需求量，q=(…,qrs,…).若以路网的运行费用与投资费用为目标，则有如下模型.上层问题：).s.t.ya≥0,∀a∈A.下层问题：求x*使得∀x∈F′，均有(x-x*)Tt(x*,y)≥0，其中F′={x|x=Δf,x≤c,Λf=q,f≥0}.因模型中既有路段变量x又有路径变量f，因此利用关系式x=Δf可将模型中路段变量x去掉，记T(f,y)=ΔTt(Δf,y)，则下层模型可写为：求f*使得∀f∈F，均有(f-f*)TT(f*,y)≥0，其中F={f|Δf≤c,Λf=q，f≥0}.2 求解算法2.1 求解上层问题的遗传算法由于上层问题没有明确的解析表达式，它里面的变量x是由求解下层问题来给出的，所以求解这类问题一般采用启发式算法.遗传算法[8]，它最早由美国密执安大学的Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究.该算法通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程.(1)适应度函数.遗传算法对个体的评价是通过个体的适应度的大小来实现的，所以算法中适应度函数的选取非常重要.这里的适应度函数我们可以直接取为模型中上层规划中的目标函数，即：).(2)编码.由于实数编码不需要编码和解码过程，且精度高，故本问题的求解采用实数编码.(3)选择算子.本文中采用基本的3种遗传操作算子，即选择、交叉和变异.选择算子采用比例选择算子，也叫赌盘选择，即每个个体被选中并遗传到下一代的概率与该个体的适应度大小成正比.(4)交叉算子.采用凸组合交叉,对于两个母体则采用凸组合交叉产生的两个子代为是[0,1]上的随机数，1≤i,j≤M，M为种群的规模.(5)变异算子采用均匀变异.2.2 求解下层问题的算法下层问题是一个变分不等式问题，本文采用对角化方法[9](松弛方法)来求解，算法中取函数g(f,fk-1)∈RP(P为网络中路径的数目)，其中因为fg(f,fk-1)对称正定，所以线积分定义了一个从F×F→R上的函数h(f,fk-1)，且g(f,fk-1)=fh(f,fk-1).算法步骤如下.步骤1：初始化.从初始可行点f0∈F开始，令k=1，给定迭代精度ε>0.步骤2：对角化.求凸规划子问题：得到解fk.步骤3：收敛性检验.若‖f k-fk-1‖≤ε，算法停止.否则令k=k+1转步骤2.算法步骤2中是一个凸规划问题，可以用任何适合的方法求解.2.3 整体算法的迭代步骤算法实现步骤如下.步骤1：初始化.设置最大进化代数T，群体规模M，交叉概率pc，变异概率pm，置t:=0，随机产生M个个体作为初始群体P(0).步骤2：对每个个体求解下层规划问题的最优解.步骤3：将上层规划的目标函数作为适应度函数评价所有个体.步骤4：根据群体中每个个体的适应度值，对P(t)做选择运算、交叉运算和变异运算，P(t)经过3种运算后得到下一代群体P(t+1).步骤5：终止条件判断.若t≤T，则t:=t+1，转步骤2；否则停止计算，输出最优解.3 数值试验本文中的网络如图1所示，两个OD对(1,3)，(5,3),需求量均为55.图1 道路网络Fig.1 Road network其中t(x)=Ax+b,Ga(ya)=1.5da(ya)2，c=(40+y1,45+y2,40+y3,35+y4,40+y5,35+y6,40+y7),A=b=(2,2,1,1,3,1,2),d1=d2=2,d3=d4=1,d5=3,d6=d7=2.计算可得，路段y1,y2,y3,y4,y5,y6,y7能力增加量分别为1.1085，7.3900，3.7126，1.4956，5.8592，2.6921，8.4106，目标函数值Z=1490.0001.4 结束语本文针对非对称平衡网络设计问题，采用遗传算法求解，从数值试验结果可知该算法是可行的，而且遗传算法求解速度快，对模型没有特别的要求.在求解下层问题时，采用收敛性快的凸规划的最优求解算法，可大大提高算法的运算效率.参考文献【相关文献】[1]Yang H,Bell M G H.Models and algorithm for road network design: a review and some new developments[J].Transportation Review,1998,18:257-278.[2]Gao Z Y,Sun H J,Zhang H Z.A globally convergent algorithm for transportation continuous network design problem[J].Optimization and Engineering,2007,8:241-257. [3]高自友，张好智，孙会君.城市交通网络设计问题中的双层规划模型与算法研究[J].交通运输系统工程与信息,2004,4(1):35-44.[4]Gao Z Y,Wu J J,Sun H J.Solution algorithm for the bi-level discrete network design problem[J].Transportation Research B,2005,39:479-495.[5]刘灿齐.交通网络设计问题的模型与算法研究[J].公路交通科技,2003,20:57-62.[6]桂岚.交通网络设计的优化模型及算法[J].系统工程,2006,24(12):25-32.[7]高自友，宋一凡，四兵锋.城市交通连续平衡网络设计:理论与方法[M].北京：中国铁道出版社,2000.[8]周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社,2005.[9]高自友，任华玲.城市动态交通流分配模型与算法[M].北京：人民交通出版社,2005.。
