航空航天乘公交看奥运方案设计Word文档格式.docx
《航空航天乘公交看奥运方案设计Word文档格式.docx》由会员分享，可在线阅读，更多相关《航空航天乘公交看奥运方案设计Word文档格式.docx（45页珍藏版）》请在冰点文库上搜索。
2.5
5/
（2）
4/
（2）
6/（4）
7/（4）
即:
换乘公汽等待３分钟，换乘地铁等待２分钟.公汽站→地铁站（通道）→公汽站.换乘耗时11分钟：
步行4+4=8分钟,等车3分钟.
基本票价参数设定:
单一计价
分段计价
公汽
1元
0～20站：
1元；
21～40站：
2元；
40站以上：
3元
地铁
3元（无论地铁线路间是否换乘）
公交线路及相关信息（见数据文件B2007data.rar）
二、问题分析:
本论文主要研究公交线路选择的问题，即要求:
a如何换车...
b车与车之间的关系...
c满足乘车人关心的问题：
1）换乘次数最少；
2）费用最低；
3）时间最短（初始等车时间2（3）min也不包括在内，最后结果可加上。
）；
......
在众多的条件中，为了切合人们的实际需要，优先考虑是否有直达,若无直达公汽,则我们主要从最方便、最经济、最快捷等出发，建立以换乘次数、费用、时间为最优的数学模型。
三、模型假设:
1、所有公交线路的每天的工作始末时间相同;
2、公汽、地铁均到站停车;
3、各公交车都运行正常，不会发生堵车现象;
4、环线可以看作以任意站作为起点站和终点站，并且是双向的,并且经过终点后要重新收费;
5、假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费；
6、人们对换乘车次数尽量少的偏好程度总是大于对花费时间相对短和花费金钱相对少的偏好程度;
7初始等车时间2（或3）min也不包括在内;
8、同一公交线的往返路线视为两条单行线;
9、考虑两地铁之间不通过公汽乘换（即只：
公汽站→地铁站（通道）→公汽站）。
四、模型建立:
对于公交线路选择，我们主要考、虑乘换次数、费用、时间各因素最优。
在线路选择问题中，将公交路线关系抽象成一个有向赋权图，当从i可直达j时（同为公汽或地铁站点），定义弧（i,j）；
其上的权为：
。
表示由i直达j付出的代价，可以为时间或费用（不包括换乘代价；
多条线路可达时只保留最小代价）；
公交乘换方式：
公汽——公汽，公汽——地铁，地铁——公汽，地铁——地铁，公汽——地铁——公汽。
A）i站点是公汽站点，j站点为地铁站点：
（1）若j站点对应的所有换乘（公汽）站点k，均不能从i直达（不在i站点所在公汽线路L上），则
=∞;
（2）若j站点对应的换乘（公汽）站点k,可从i站点直达k，则费用为
=
；
注：
对于时间则需要加上k到j的步行时间.（若有多种选择，取最小成本者即可）
B）j站点是公汽站点，i站点为地铁站点：
（1）若从i站点对应的任何换乘（公汽）站点k，均不能直达j站点，则
=∞.
（2）若从i站点对应的换乘（公汽）站点k，能直达j站点，则费用为
；
注：
对于时间则需要加上i到k的步行时间.
定义：
矩阵算子“⊙”如下：
设D（k-1）、D均为n阶方阵，
D（k）=D（k-1）⊙D（考虑换乘代价）
当考虑费用矩阵间的运算时，
=0；
当考虑时间矩阵间的运算时，
表示在k的换乘时间。
D（k）=D（k-1）⊙D表示k次换乘的最低代价（费用或时间），即通过修改floyd算法求解。
δi,j,k表示换乘时间：
i=j或k=i，j时，δi,j,k=0
其他情形：
若不可换乘（当i，j为公汽站点而k为地铁站点，或者i，j为地铁站点而k为公汽站点时），则δi,j,k=0
若可换乘，则：
问题一模型：
因为仅考虑公汽线路，为了能得到两站点之间的最好选择线路，将题中所提供的公汽网络抽象成一个有向赋权图,建立直达矩阵D=
当D为时间直达矩阵时，按D（k）=D（k-1）⊙D式重复地进行⊙运算得到
，当
，
时，表示从i站点到j站点最少换乘k次能够到达，且即
表示换乘k次到达所需的最短时间。
当D为费用直达矩阵时，按D（k）=D（k-1）⊙D重复地进行⊙运算得到
，运算适当次数后若D（k）=D（k-1），则表示已得到所有站点间的最小费用，
即表示从i站点到j站点所需的最少费用。
根据最少乘换次数等约束条件，再利用图的邻接搜索法可得出两站点之间的选择线路。
问题二模型：
当还需要考虑地铁时，为了能得到两站点之间的最好选择线路，同样，将题中所提供的公汽（含地铁转换的公汽）网络抽象成一个有向赋权图,建立直达矩阵D=
算法设计基本与模型一相当。
当D为时间直达矩阵时，按D（k）=D（k-1）⊙D式重复地进行⊙运算得到
根据最少乘换次数等约束条件，再利用图的邻接搜索法可得出两站点之间的选择线路。
问题三模型：
问题三是在模型二的基础上添加步行时间进行考虑。
优先考虑乘换次数。
对直达时间矩阵
按D（k）=D（k-1）⊙D式重复地进行⊙运算得到
时，表示从i站点到j站点最少换乘k次能够到达。
在运算过程中可记录下换乘站点信息，随之可得到相关线路信息。
若有若干条最小换乘路线，则比较另外两个目标选择最佳线路（即建立0-1整数规划模型）。
设共有m条单行公交线，构造一个m+2个点构成的完全图。
点：
a为起点（出发点），b为终点（目的地），此外每条公交线也视为一个点。
边：
边表示两点之间的步行关系。
边权：
步行时间为边权。
针对不同的边可分为上车前、下车后和换车时步行时间，构成步行时间矩阵
。
行：
依次表示的是m条公交线与起点，列：
依次表示的是m条公交线与终点。
点权：
第个公交线点还有三个信息为点权。
1）公交线名称及上行或下行；
2）类型
及票价方式；
3）乘车站数表矩阵
，其中
表示从c到d经过i号公交线时需要乘车的站数,c到d利用不上i时
取无穷大。
这个矩阵的行列表示用S。
于是原问题转化为在这个图上求a到b的最短路。
最短的可以理解为换乘车数最少、乘车的总站数最少、总的步行时间最少、总车费最少这样几个目标的各种组合方式。
可以用0-1整数规划解决这个问题，方法是分出恰乘一次公交车，恰乘两次公交车，恰乘三次公交车等等情况分别求出下列模型解然后比较得出最优解。
优化模型：
恰乘一次公交车的模型如下：
变量全部是0-1变量，共有3*（m）个。
表示选不选择去第i条公交线的路；
表示选不选择乘第i线公交车；
表示选不选择从第i条公交车下车后走到目的地的路。
（它们都是取1表示选择而取0表示不选择。
）
恰乘一次公交车的模型如下：
目标函数：
据用户选择的情况用点权和边权构造，共同点都是最小值。
（1）步行时间最少:
目标函数
（2）总时间最少:
其中
（3）车费最少:
约束条件（共2m+1个）：
只选择一条公交线；
要乘第i条公交线就要走相应的两条路。
恰乘两次公交车的模型如下：
步行时间:
时间最少：
费用最少：
约束条件：
可以选择两条公交线路；
乘公交线要走的两条相应的路线。
恰乘乘三次公交车模型:
步行时间的目标函数在的基础上添加
;
时间最少的目标函数在的基础上添加
费用最少:
约束条件即在的基础上添加
的变量即可。
五、模型求解:
问题一：
由于题目所给的公交乘路信息是.txt文本文件，为了将实际问题能用数学模型来解决，我们编写程序将其导入matlab。
（程序见附录1）。
对于问题1，我们仅仅考虑公汽线路，为此，我们将所有的公汽路线与站点（3957个）关系构成一个图网，为了求得最小代价的选择路线，我们先建立起直达矩阵（程序见附录2），再由改进floyd算法（程序见附录3）即可求出两公汽站点之间线路选择的最小代价（乘换次数、时间最短、费用最少），乘换次数为主、时间最短和费用最少为次为约束条件用搜索法（见附录程序5）搜出最优线路，
具体结果如下所示：
起点站→终点站
乘换次数
车费（元）
线路
S3359→S1828
1
89
S1557→S0481
2
112
S0971→S0485
119
S0008→S0073
83
S0148→S0485
106
S0087→S3676
52
问题二：
对于问题2，我们在考虑公汽线路的同时，还需将地铁线路（2条地铁线路，39个地铁站点）考虑进去，同样，将所提供的公汽（含地铁转换的公汽）网络抽象成一个有向赋权图,建立直达矩阵（程序见附录4），再由改进floyd算法（程序见附录3）即可求出两公汽站点之间线路选择的最小代价（乘换次数、时间最短、费用最少），以换乘次数为主、时间最短与费用最少为次为约束条件用搜索法（见附录程序6）搜出最优线路，具体结果如下所示：
50
问题三：
问题3又增设了所有站点之间的步行时间，为了给出任意两站点之间线路选择问题的数学模型。
我们则考虑大众化的想法（优先考虑乘换次数）：
[1]若两个站点之间有直达的公交车，若只有一条，我们毫无条件地选择；
若不止一条，则我们可以利用模型三的优化模型进行时间和费用的比较，取最优解；
[2]同理，若要经过转乘一次、二次等转乘情况，若转乘线路只有一种，则选择之；
若转乘线路有多种，则利用模型三的优化模型进行时间和费用的比较，取最优解。
六、模型优缺点:
将公交图网能用有向赋权图并建立直达矩阵，再利用最短路算法及搜索算法得出线路选择的最优线路（含时间最少、费用最少等）；
对于第三问题中的模型，在加入步行时间后，我们能考虑到在乘换次数最少为优先的条件下，利用优化模型进行比较是全面些。
鉴于公交系统网络的复杂性，我们虽然采用了修改floyd算法，编译运行上不太好，有待改进。
七、参考文献:
[1]蔡志杰，丁颂康数学工程学报-公交线路选择模型2007年12月1005-3085（2007）08-0117-04
[2]朱参世一种Warshall和Floyd算法的优化方法研究2010年第四期1006-2475（2010）04-0043-03
[3]刘韵，何建农基于交通网络最短路径搜索的改进算法2007年1002-8331（2007）14-0220-03
附录:
function[A]=T_SORT（A,n,p）%建立排序函数
%T_SORT（A,n,p）
%A根据第n行排序
%p=1升序，2降
%powered_BY_*
SIZE=size（A）;
ifp==1
[xx,idx]=sort（A（n,:
））;
fori=1:
SIZE
（1）
A（i,:
）=A（i,idx）;
end
elseifp==2
）,'
descend'
）;
1、
%数据处理读入matlab：
%读取数据
clearLa
fid=fopen（'
1.1公汽线路信息.txt'
'
r'
i=1;
while1
tline=fgetl（fid）;
if~ischar（tline）,break,end
ifstrcmp（tline,'
'
）
continue
end
ifstrcmp（tline
（1）,'
L'
str=tline;
elseifstrcmp（tline,'
END'
break
单一票制1元。
P=1;
分段计价。
P=2;
ifstrcmp（tline（1:
2）,'
上行'
L{i,1}=str;
L{i,2}=P;
L{i,3}='
L{i,4}=tline（4:
end）;
i=i+1;
elseifstrcmp（tline（1:
下行'
环行'
环行1'
L{i,4}=strcat（tline（4:
end）,tline（10:
end））;
%计算来回
环行2'
elseifstrcmp（tline
（1）,'
S'
来回1'
L{i,4}=tline;
来回2'
fclose（fid）;
size（L,1）
tline=L{i,4};
t=findstr（tline,'
temp=zeros（1,length（t））;
ifstrcmp（L{i,3},'
）||strcmp（L{i,3},'
forj=length（t）:
-1:
1
temp（length（t）-j+1）=str2double（tline（t（j）+1:
t（j）+4））;
else
forj=1:
length（t）
temp（j）=str2double（tline（t（j）+1:
L2{i,1}=temp;
end
3957
iffloor（i/10）==0
Cit{i}=strcat（'
S000'
num2str（i））;
elseiffloor（i/100）==0
S00'
elseiffloor（i/1000）==0
S0'
Cit{3958}='
D01：
S0567，S0042，S0025'
Cit{3959}='
D02：
S1487'
Cit{3960}='
D03：
S0303，S0302'
Cit{3961}='
D04：
S0566'
Cit{3962}='
D05：
S0436，S0438，S0437，S0435'
Cit{3963}='
D06：
S0392，S0394，S0393，S0391'
Cit{3964}='
D07：
S0386，S0388，S0387，S0385'
Cit{3965}='
D08：
S3068，S0617，S0619，S0618，S0616'
Cit{3966}='
D09：
S1279'
Cit{3967}='
D10：
S2057，S0721，S0722，S0720'
Cit{3968}='
D11：
S0070，S2361，S3721'
Cit{3969}='
D12：
S0609，S0608'
Cit{3970}='
D13：
S2633，S0399，S0401，S0400'
Cit{3971}='
D14：
S3321，S2535，S2464'
Cit{3972}='
D15：
S3329，S2534'
Cit{3973}='
D16：
S3506，S0167，S0168'
Cit{3974}='
D17：
S0237，S0239，S0238，S0236，S0540'
Cit{3975}='
D18：
S0668'
Cit{3976}='
D19：
S0180，S0181'
Cit{3977}='
D20：
S2079，S2933，S1919，S1921，S1920'
Cit{3978}='
D21：
S0465，S0467，S0466，S0464'
Cit{3979}='
D22：
S3457'
Cit{3980}='
D23：
S2512'
Cit{3981}='
D24：
S0537，S3580'
Cit{3982}='
D25：
S0526，S0528，S0527，S0525'
Cit{3983}='
D26：
S3045，S0605，S0607'
Cit{3984}='
D27：
S0087，S0088，S0086'
Cit{3985}='
D28：
S0855，S0856，S0854，S0857'
Cit{3986}='
D29：
S0631，S0632，S0630'
Cit{3987}='
D30：
S3874，S1426，S1427'
Cit{3988}='
D31：
S0211，S0539，S0541，S0540'
Cit{3989}='
D32：
S0978，S0497，S0498'
Cit{3990}='
D33：
S1894，S1896，S1895'
Cit{3991}='
D34：
S1104，S0576，S0578，S0577'
Cit{3992}='
D35：
S3010，S0583，S0582'
Cit{3993}='
D36：
S3676，S0427，S0061，S0060'
Cit{3994}='
D37：
S1961，S2817，S0455，S0456'
Cit{3995}='
D38：
S3262，S0622'
Cit{3996}='
D39：
S1956，S0289，S0291'
2、%建立公汽间的直达矩阵
clearS
S（1:
3957,1:
3957）={zeros（1,1,'
uint16'
）};
%按UInt16格式建立1行1列的零巨阵
1040
t=L2{i,1};
length（t）-1
fork=j+1:
length（t）
temp=S{t（j）,t（k）};
str=L{i,1};
[n,m]=size（temp）;
ifn==1&
&
temp（1,1）==0
temp（n,1）=str2double（str（2:
ifL{i,
升级会员 