环岛优化模型论文-交通环岛的优化设计问题.docx

论 文 题 目： 交通环岛的优化设计问题 姓 名：学 院：专 业： 年 级 、 学 号： 指 导 教 师： 交通环岛的优化设计摘要本文围绕交通环岛优化问题，建立了基于SVD与SJF调度算法的交通优化模型、基于MFQ调度算法的交通优化模型，并设计了先来先服务算法、短进程优先算法和多级反馈队列算法，利用MATLAB实现对问题的求解。基于SVD与SJF调度算法的交通优化模型的建立，首先建立了简单信号灯模型，设计车流量矩阵，通过对指标的建立来测试环岛各路径的权重，权重高的路径应给予更高的优先权，让更多的车更快的通过环岛，提出控制信号灯秒数控制入岛车流量和规范岛内车辆行驶来调节各个道路车况，同时考虑司机遇到情况时的反应时间。然后建立改进的信号灯分配模型，使用短进程优先调度算法，在环岛从越近干道出岛的车辆优先权越高，优先权越高就提供各种方式使其优先出岛。基于MFQ调度算法的交通优化模型，设计改进的多级反馈队列调度算本文建议两种模型交错实行，在高峰期时使用模型一，在非高峰时期时关闭信号灯，使用模型二，提高环岛内车辆通过效率，缩短平均通过时间，缓解若环岛有多条车道则驶入的交通流与驶入出的交通流存在的冲突。当环岛容量趋于饱和时，这种冲突越发明显。因此可尝试使用一些辅助手段如交通信号灯、“停”“让”指示牌等来优化环岛的交通流。关键词：信号灯分配、路径权重比、多级反馈队列调度算法1. 问题重述目标是提出换到交通优化控制的模型，定量的分析如何更好的控制环岛的交通状况，以及需要进入环岛和希望离开环岛的交通流。伪有穷Jackson网络模型是基于单车道环岛建立的，对于多车道环岛是否也可以构建类似的排队论模型呢？一种模型思路认为，可以将每个车道抽象为一个服务系统，进而一个多车道环岛可以抽象为一个多级服务系统。请问这个思路可行吗？若可行请建立模型，若不可行，请说明理由。2. 模型假设与符号说明2.1 模型假设1.到达事件和离开事件指数分布2.模型的到达和离开事件建立在具有指数分布间隔时间的泊松过程之上。泊松模型被广泛的应用于很多具有随机到达的场合。泊松过程的参数由一段时间内的到达和离开事件数进行平均求得。3.在理想状态下，无论车辆从哪个路径离开，环岛模型都能够成功满足4.通常车道宽为3.75m5.到来率恒定6.理性驾驶行为2.2模型一符号说明进/出路径的个数n第i行之和Ai i=1n第j列之和Bj j=1n每个路径单位时间内出现车的概率pIn_i i=1n每辆车从i路径进入j路径离开的概率pOut_(i,j) i,j=1n奇异值i i=1n车道的个数m车道距环岛中心的距离( rroad_i与vcar有关) rroad_i i=1m车速( rroad_i与vcar有关)vcar环岛的平均半径r环岛的周长为p平均车长l车道宽度lroad标记星号的小汽车从等待的车队末尾至进入环岛的时间t1标记星号的小汽车从进入环岛至离开环岛的时间t2环岛平均宽度rroad到达时间（车驶向环岛的时间）t_arrive服务时间（车从驶向到最终离开环岛的时间）t_serve完成时间（车在环岛内行进的时间）t_finish周转时间（车在排队的时间）t_waste带权周转时间t_quan环岛平均周长 p_road 容纳车辆数n_contain 将环岛填满需要的时间t_cost2.3模型二符号说明车道宽度lroad带星号的小汽车从车队队末至进入环岛的时间t1带星号的小汽车从进入环岛至离开环岛的时间为t2路径数n3. 模型的建立3.1模型一 基于SVD与SJF调度算法的交通优化模型3.1.1简单的信号灯分配模型1.建立车流量分布矩阵设ki,j为从第i个路径进入、从j个路径流出的车流量期望值，得到车流量的分布矩阵为:K=ki,j= k1,1k1,nkn,1kn,n则分布矩阵中,第i行之和Ai表示从第i个路径进入环岛的车流量，Ai=j=1nki,j,第j列之和Bj表示从第j个路径流出环岛的车流量, Bj=i=1nki,j,令 A=i=1nAi ，此时pin_i=AiA ,令 B=j=1nBj ，此时pout_j=BjB ,在理想情况下 ， 每个路径双向车道比应为 pIn_ipout_j 2.指标设计现在假设存在服从泊松分布的矩阵K。现在的目标就是：在n维空间中找一组正交基，使得经过K变换后还是正交的。假设已经找到这样一组正交基：v1,v2,vn则K矩阵将这组基映射为：Kv1,Kv2,Kvn如果要是他们两两相交，即 KviKvj=(Kvi)TKvj=viTKTKvj=0根据假设，存在 viTvj=vivj=0所以，如果正交基选择v为KTK的特征向量的话，由于KTK是对称矩阵，那么 viTKTKvj=viTivj这样就找到了正交基使其映射后还是正交基了，现在，将映射后的正交基单位化： KviKvi=Kvi2=iviTvi=i所以取单位向量 ui=Kvi|Kvi|=1iKvi即Kvi=iui其中 i=i =100n为K的奇异值矩阵在此，我们将i , pIn_i 和pOut_j 作为衡量路径i权重的重要指标，权重高的路径应当给予更高的优先权。可以通过适当的方式来增加优先权，比如对于权重较高的路径处红绿灯增加绿灯时间，增加路径的车道宽度等。3.信号灯秒数设计图1-1图1-2影响信号灯秒数的因素包括：环岛半径，路径车道数，车辆长度，安全距离等。在此假定平均车辆长度为4m，等待红绿灯期间平均安全距离为0.5m。图1-2为主干道的车辆示意图 令标记星号的小汽车从队末至进入环岛的时间为t1t1=4Ai-1+0.75Aimv_car 令标记星号的小汽车从进入环岛至离开环岛的时间为t2，在这里t2是一个n*1的列向量 t2=2rroad4vcarrroadvcar3rroad2vcar2rroadvcar标记星号的小汽车的从驶入到离开环岛时间分布为t1+t2。主干道信号灯的绿灯秒数则在t1到t1+t2之间。当绿灯为t1秒时，能够保证主干道车辆恰好全部进入环岛；当绿灯秒数为t1+t2时，能够保证车辆在环岛行驶过程中不受其他道路车辆的影响，所有的车都能够顺利离开环岛。4.结果分析我们假设路径数n=4，环岛的平均半径为25m，限速25km/h，用MATLAB生成服从泊松分布的4*4随机矩阵K，并通过上述方法比较各个路径的各项指标。如图1-3（代码见附录1）图1-3由于在正常情况下驾驶员从视觉感知到踩制动器的动作中间的反应时间为0.75秒,为了保证模型的合理性，我们在计算红绿灯秒数时考虑了反应时间。在这里，我们假设权重和绿灯秒数成正比。如图1-4图1-4在此，我们优先考虑路径数为偶数的情况，即连接环岛的路径近似对称。如图1-5图1-5为了衡量模型的合理性与稳定性，在此，我们提出一些指标，到达时间t_arrive，服务时间t_serve，完成时间t_finish，周转时间t_waste，带权周转时间t_quan。假设，所有车辆t_arrive近似相同 t_serve=j=1n0.75ki,j+ p_road |j-i+1|v_cart_finish=t_serve+t_arrivet_waste=t_finish-t_arrivet_quan=k(i,j)t_servet_waste图1-6令环岛平均周长为 p_road ,容纳车辆为 n_contain ,将环岛填满需要的时间为t_costp_road=2r_road n_contain= p_roadlt_cost=p_roadv_carK=3935855257709701设在某时刻车流量的服从泊松分布的矩阵K，我们对这组数据进行检测，观察不同路径的带权周转时间。此时，为了最大限度放行车辆，信号灯取t1+t2，绿灯秒数分别为47s，15s。遵守优先放行主干道的原则，我们将主干道的初设信号灯设为绿灯。在不知道初始路径的情况下，我们认为路径足够的宽，能够顺利进入环岛。在此，我们着重考虑每个路径队尾的车的情况（见表1-1,表1-2,表1-3）。表1-1路线名K(1,1)K(1,2)K(1,3)K(1,4)等待车辆3935等待次数0000达到时间0000服务时间43212936完成时间43212936周转时间0000带权周转时间0000主干道的车辆恰好全部走完表1-2路线名K(2,1)K(2,2)K(2,3)K(2,4)等待车辆8257等待次数1111达到时间0000服务时间37442330完成时间84917077周转时间47474747带权周转时间6.301.872.454.47由于次干道绿灯时间较短（15秒），22辆车只有20辆车能够顺利通过红绿灯，剩余的两辆车只能等待下一次绿灯，我们考虑这两辆车的周转时间表1-3路线名K(2,1)K(2,2)K(2,3)K(3,4)等待车辆2222等待次数2222达到时间0000服务时间37442330完成时间146143132139周转时间109109109109带权周转时间6.982.682.875.02通过数据的比较，可以发现通过此模型使主干道的交通状况良好，基本可以满足车流量，无需二次等待。但对于其它干道而言，周转时间将达到两分钟甚至更久。由于车流量较小的缘故，带权周转时间也并不是很大。3.1.2改进的信号灯分配模型在此，称在相邻的下一个路口离开路径称为短作业，在之后第二，三，四个路口离开路径称为长作业。对于多车道的环岛，由于在实际情况中，短作业占很大比例，为了能使短作业能够更加高效的执行，我们在此考虑短作业优先调度算法。SJF算法是以作业的长短来计算优先级，作业的服务时间越短，其优先级越高。因此，我们可以将每个路径处的红绿灯设立标志，在相邻的下一个路口处离开的车辆走外车道，并且不受红绿灯的制约，在第二、三、四个路口处离开的车辆优先走内车道，以此减少车辆变道引起的交通堵塞。因此，在考虑车流量的分布矩阵K时，我们可以忽略ki,i+1对矩阵的影响，即在相邻的下一个路口处离开的情况。此时，重新比较指标 i， pIn_i 和 pOut_j ，判断各个路径的权重。如图2-1各个路径权重= i + pIn_i+ pOut_j3图2-1各个路径的权重比示意图（如图2-6）图2-2由图1-4与图2-2之间的比较易发现，通过短进程优先算法，排除短进程车辆对权重的巨大影响，结果会显得更加合理。将权重高的路径看做主干道，在主干道路线处设置交通信号，主要从控制入岛车流量和规范岛内车辆行驶两个方面解决在交通量的急剧增大时环岛内车辆的合流和分流行为引起的交通紊乱的情况。在此，我们对改进的模型进行了一次测试，各项数据与上次测试相同，我们选取十组随机样本，比较主干道与次干道时间花费情况。如图2-3图2-3由图看出，在随机测试的是个样本中，主干道车辆平均花费时间为25s，次干道为47s，效果比上一次测试要好。3.2模型二 基于MFQ调度算法的交通优化模型3.3.1模型的提出 考虑到环岛进出规则： 1、进环岛车辆让出环岛车辆； 2、环岛内侧车辆在出环岛路口前，应该提前并线至外侧车道。 因此，可以将每个车道抽象考虑成一个服务系统，进而一个多车道环岛可以抽象为一个多级服务系统。3.3.2改进的多级反馈队列调度算法1改进的多级反馈队列算法的调度机制可描述如下：1）设置多个就绪队列，每一个就绪队列对应着一个车道（通常使用三个就绪队列），并为每一个队列赋予不同的优先级。第一个优先级最高，第二个次之，其余队列的优先级逐个降低。如图3-1所示图3-12）每个队列都采用FCFS算法。当车辆进入车道后，首先将它放入第一队列的末尾，按FCFS原则行驶。如果它能够在该时间片内完成，便可离开环岛。否则它将转入第二队列的末尾等待进入。如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三个队列，依次类推。3）特别的，需要在各路径与环岛的交界处设立减速标志牌，以防止车辆变道发生的碰擦。2. 判断多级反馈队列算法的合理性在多车道车辆行驶问题上与进程调度问题有着很大的相似性，每一个道路对应着一个服务器，当一个服务器在规定时间片内无法完成进程，则将其转至下一个服务器。但是二者之间也有着很大的区别，人需要一定的反应时间，车辆频繁变道会导致减速，从而引起连锁反应，因此会延长带权周转时间。3.在理想状态下求解MFQ调度算法模型图3-2 在MFQ调度算法模型下，由于车辆从路径进入环岛只能通过就绪队列1，无论主干道有多少车道，最终将并为一列。因此，不妨假设主干道只有一个车道。 车道宽度为lroad 令标记星号的小汽车从队末至进入环岛的时间为t1t1=4Ai-1+0.75Aiv_car 令标记星号的小汽车从进入环岛至离开环岛的时间为t2，在这里t2是一个n*1的列向量 t2=2rroad4v_carrroadv_car3(rroad-lroad)2v_car2(rroad-2lroad)v_car4.结果分析我们假设路径数n=4，环岛的最大半径为40m，车道半径为5m，限速25km/h，用MATLAB生成服从泊松分布的4*4随机矩阵K，并通过上述方法比较各个路径的各项指标。最优情况为车辆较少，无需排队即可进入环岛的情况；最差情况为车辆较多，需要排队才可以进入环岛的情况。图3-3 由图可知，当车流量变大时，车辆花费时间明显增长。这对于在高峰时期车流量的较大的主干道是不利的，但在非高峰时期则会节省很多时间。鉴于交通环岛具体情况的复杂性及较强的地域、 民族、 文化、 历史性， 对其道路结构、 通行能力进行了分析， 制定相应的岛内车辆环绕方式， 并针对不同路口采用不同的信号控制方式， 在减小车辆发生冲突的几率、 避免发生交通事故的基础上，将交通环岛的通行能力最大化。本文建议两种模型交错实行，在高峰期时使用模型一，在非高峰时期时关闭信号灯，使用模型二，提高环岛内车辆通过效率，缩短平均通过时间，缓解若环岛有多条车道则驶入的交通流与驶入出的交通流存在的冲突。当环岛容量趋于饱和时，这种冲突越发明显。因此可尝试使用一些辅助手段如交通信号灯、“停”“让”指示牌等来优化环岛的交通流。参考文献附录附录1：function huandao(n) K=random(Poisson,n,n) colsum=sum(K); %第j个路径流出环岛的车流量之和 rowsum=sum(K,2); %第i个路径进入环岛的车流量之和 colmean=sum(colsum); %第j个路径流出环岛的平均车流量 rowmean=sum(rowsum);%第i个路径进入环岛的平均车流量 colproportion=colsum/colmean; rowproportion=rowsum/rowmean; U,S=svd(K); character=diag(S); x=1:n; figure (1) plot(x,rowproportion,b); hold on plot(x,colproportion,r); hold on plot(x,character/sum(character),g); hold on quanzhong=(rowproportion+colproportion+character)/sum(rowproportion+colproportion+character); scatter(x,quanzhong,*); hold on legend(进入比率,离开比率,特征值比率,权重); scatter(x,rowproportion); hold on scatter(x,colproportion); hold on character=character/sum(character); scatter(x,character); grid on set(gca,XTick,1:n); title(各路径权值指标比); xlabel(路径); ylabel(百分比/%); figure (2) label=第一条路径,第二条路径,第三条路径,第四条路径; explode=diag(eye(n); colormap(cool); pie3(quanzhong,explode,label); title(单个红绿灯最佳秒数比);%建议红绿灯秒数% r=25;% p=2*pi*r;% v=20000/3600;% t=p/v;%当环岛半径r=25m时，知周长p=126，车速度5.5米每秒，需耗费t秒% n2=p/4;%周长除以车长=环岛一个车道内能够容纳车的数量% plot(x,floor(quanzhong*(t+n2*0.75);%驾驶员从视觉感知到踩制动器的动作中间的反应时间为0.75秒% hold on% scatter(x,floor(quanzhong*(t+n2*0.75);% hold on % grid on % set(gca,XTick,1:n);% title(单个红绿灯最佳秒数比);% xlabel(路径);% ylabel(绿灯秒数); pre_road=zeros(1,floor(n/2); for j=1:floor(n/2) pre_road(1,j)=(character(j)+character(2*j)/2;%选取平行路径权值的平均值 end p_pre=pre_road/sum(pre_road);%权值比 figure (3) label=第一条路径,第二条路径; bili=p_pre/sum(p_pre); baifenbi=num2str(bili); explode=diag(eye(floor(n/2); pie3(p_pre,explode,label); title(红绿灯最佳秒数比（平行路径红绿灯秒数相同）); %建议红绿灯秒数（平行路径红绿灯秒数相同） %plot(1:floor(n/2),p_pre*(t+n2*0.75); %set(gca,XTick,1:floor(n/2); %xlabel(路径); %ylabel(绿灯秒数); %grid on %基于SJF算法 for i=1:n-1 K(i,i+1)=0; endK(n,1)=0;colsum=sum(K); %第j个路径流出环岛的车流量之和rowsum=sum(K,2); %第i个路径进入环岛的车流量之和colmean=sum(colsum); %第j个路径流出环岛的平均车流量rowmean=sum(rowsum);%第i个路径进入环岛的平均车流量colproportion=colsum/colmean;rowproportion=rowsum/rowmean;U,S=svd(K);character=diag(S);x=1:n;figure (4)plot(x,rowproportion,b);hold onplot(x,colproportion,r);hold onplot(x,character/sum(character),g);hold onquanzhong=(rowproportion+colproportion+character)/sum(rowproportion+colproportion+character);scatter(x,quanzhong,*);hold onlegend(进入比率,离开比率,特征值比率,权重);scatter(x,rowproportion);hold onscatter(x,colproportion);hold oncharacter=character/sum(character);scatter(x,character);grid onset(gca,XTick,1:n);title(基于SJF算法各路径权值指标比);xlabel(路径);ylabel(百分比/%);figure (5)% r=25;% p=2*pi*r;% v=20000/3600;% t=p/v;%当环岛半径r=25m时，知周长p=126，车速度5.5米每秒，需耗费t秒% n=p/4;%周长除以车长=环岛一个车道内能够容纳车的数量% plot(x,floor(quanzhong*(t+n*0.75);%驾驶员从视觉感知到踩制动器的动作中间的反应时间为0.75秒% hold on% scatter(x,floor(quanzhong*(t+n*0.75);% hold on % grid on % set(gca,XTick,1:n);% title(基于