优秀9多目标道路寻优问题研究

Dijkstra乘模型。为此，路线分为：不经过地铁、仅在地铁站进行换乘和乘坐地铁这们根据得出的结果进行了灵敏度分析，总结出当公车行驶速度和换乘等待时间变化时，着08年奥运会的到来，大量将涌入，使本就接近饱和的交通市场需求，某公司准备研制开发一个解决线路选择问题的自主查询计算机系统。系统的设计是线路选择的模型与算法能满足查询者的各种不同实际需求。络图论中的网络图，然后通过图论中的网络分析理论来实现网络中的最优路径分在网络中，所有站点是通过线络连接在一起的，可以将整个城市的所有站点的出行需求最终可归结为两种形式一种是总出行时间最少，另一种是乘客的出行总成道路、系统承载能力、道路状况、满意程度、择流等因素的影响。 存在交通堵塞、自然、物价上涨等影响系统的情况。SlSi

tnt 从第

j站换乘

n0,1,

从第ijMnM 从第

j

n

n0,1, 从第ij G(V,

从第ij

V=(SDE 相邻两站之间的通路构造边集{E}。构造交通拓扑图G(SE)Eij为有向边，表示车站Sj（i,j表示车站编号） 3min在实际情况中，人们选择路径不仅要考虑出行时间t、出行花费M，而且要考虑到地，同时花费尽量少，而换乘次数在能接受的范围内即可。在本文中，始终将时间t作为首要的优化目标，出行花费MN作为限制条件⑴将G中的每一个站点用站点和线路的点集代替⑶新的结点连接成的子图为一个完全图，子图的每一个边权为5min疏松处理之后，新结点构成集合V，其中一个结点表示为V(SiLjV，则上述疏 网络图边集，lj,lklSi⑵E((Si,Lj),(Si,Lk))E，WijtijE(Si,Lm),(Sj,Ln)Ei E(SiSj) 图1图2由此可构造出新的拓扑图G(VE)。那么经过处理之后，出行的时间花费就仅与3几乎可涵盖所有乘车情况。这样换乘次数k只有40123k次换乘路线中的最短路为klsi}为站点Si{

}是从S是经历N次换车到达S

从起始站到终止站的时间花费的为Msd，从SS经历N次换车到Sd用的最少时间为MNSkRsk是SS到SkSk到SdRkd是Sk到SdSS，Sd之间的最短路的假设。证毕假定从SS到Sd第一个换乘点为Sp，则根据定理一，经过Sp的最短路由SS到Sp的0短路和Sp到Sd的k-1

tsd{tN}，当N=0，若lsslsd，则t0=m(sd)*3；否则t0 当N=k(k=1,2,3),tk=min{t0+5+tk1},n为第一次换乘的车站号， 以 Stk 算法步骤t0=m(SS)*3Rk}可直接找到；否则，t0Rk} ii求出t0R0。若t0，则t1t1=t0+5+t0。若r0=null，则r1 否则r1r0r0 iStep3:N=2(换乘两次):SS为起始点广度优先搜索所有在lS}Sk，返回Step2求出t0R0。若t1=无穷，则t2=；否则t2=t0+5+t1。若r0=null，则r2=null；i 否则r2r1,r0} Step5:Min {t0,t1,t2,t3}，比如 =tk,则 =rk。算法终止 0∞∞∞∞∞∞1∞∞233次，632次下3次以上的乘车线路，处理较为

Min {MN}，当N=0，若 ，则t0=1或依照所选线路中S与S间距离而定；否则t

当N=k(k=1,2,3)，Mk=min{M0+Mk-1k为第一次换乘的车站号，可以从S 后沿各个线路顺次任意取站点。可用迭代的方法求出所有的Mk 结果如下0∞∞∞∞∞∞13∞32∞22333333333232费的路线时，换乘次数N3的情况不再考虑。333232333333343443这三个问题也选择换乘2次的最短时间成车路线。323232323232站合并到一起作为站点总集{V}{S}{D}，地铁线路和线路合并到一起作边集{E}tii1表示从站点V到相邻站点V所花的时间。若VVS，tii1 若ViVi+1Dtii1=2.5。记公汽换乘地铁的时间为t1=6min,地铁换乘公汽的时间为t27min，在地铁站进行公汽换车的时间为t3=11min，tsd为从起始站Ss到终点站Sd定理二：如果Ss到Sd的最短路径Rd属于第二类，那么在Rsd中有且仅有一次公汽换到Dq的地铁线路替换Rsd中Dp到Dq的路径，从而得到花费时间更少的路径，与Rsd是定理三：如果Ss到Sd的最短路径Rsd属于第三类，那么在Rsd

tsd=t(Si,S(Di))+t(S(Di),Si)+记为S(DiDi进行唯一一次换乘。于是有tsdtsDitDid。记站点集S(Dit(S(DiSi为站点集S(Di中某站点到站点Si花费的时间。若使乘车总时间tsd最小，它的子问题都应取到最小，那么问题就转化为求汽换乘，Mintsk可用问题一中基于换车次数受限的通用模型求解。Step2:Sk搜遍集合S(Di，求出t(SsS(Di))minStep3:同理求出t(S(DiSdmin =Min{t(D

tsd=t(Ss,S(Di))+tij+t(S(Dj),Sd)+t1+t点集为S(DiS(Dj。t(SiS(Di为站点Si到站点集S(Di中某站点所花费的时间，tij为地铁站DiDj间的行驶时间。那么乘车总时间为tsd=t(SsS(Di))tijt(S(DjSdt1t2=t(SsS(Ditij+t(S(DjSd+13

min、t(SsS(Dimin和t(S(DjSd)min两次,用基于换车次数受限的通用模型求解，求出tijmin)))Step3:对于选定的(Di,Dj),记tsd(Di,Dj)为在地铁站Di,Dj进出地铁的线路乘车总时间，将各子问题最优解相加即可求出tsd(Di,Dj) Step4遍历搜索全部的进出地铁站的站点对DiDj，比较得出第三类线路中的

min=Min{t(D,

min=MIN{tsdmin，t

，m

min 7.0编程进行搜索求解(程序见附录)，求得的比较求出tsdmin

min，t

，m

铁仅会节省不足10分钟，又考虑到人们希望尽可能不换车，且乘地铁会另外花费3元，时乘地铁还是节省费用乘车。333665将原有的拓扑图G(VE)变换，站点集合{V不变，扩充集合{E为{E，{EG(V,E)变为完全图G(V,EijHij

EijEEijE，则EijDjikstra同。特别的，如果Vi{D}，即Vi是地铁站点，则不需要对其进行疏松处理。G(VE)经过疏松处理之后，点集和边集都极大得扩充了，可以预见该模型的补充假设 2）存在步行换站的时间上限th那么在站点集{V}中遍历搜索站点对(Vi,Vj，记他们的步行换站时间为t(Vi,Vj。把1换站的站点对就设为(Vi,VjMintsd=tSVi+t(Vi,Vj)+t(Vi,Vj)为一已知的值。由子问题定理得：t(V,V) =

+t(Vi,Vj)+tVjd SVi

|min我们把所有线路所需的行驶时间在原来的基础上增加和减少&t后，用原模63t，观察行驶时间对最优时间的边际影响t=|tt|和换乘次数的影响。结合多方因素考虑&t从0.1—0.9 -----99图3：随&t增加的ti-&t图 图4：随&t减少的ti-&t图同样，有与铁需的驶间在来的础增加减$t问最优解t，观察换乘时间对最优时间的边际影响t=|t-t |和换乘次数的影响，

-----1----------1----- t=|t 当发生如塞车等导致行驶时间变长的情况时，乘客应考虑的换乘路