公交线路转乘选择的优化模型数学建模论文.docx
《公交线路转乘选择的优化模型数学建模论文.docx》由会员分享，可在线阅读，更多相关《公交线路转乘选择的优化模型数学建模论文.docx（29页珍藏版）》请在冰点文库上搜索。
公交线路转乘选择的优化模型
摘要：
本文以奥运会的公交线路换乘为大背景，建立了在公汽线路、地铁以及步行三种方式中综合进行路线转乘的模型。
此问题可以归结为两个站点之间的最短路问题，由于直接以站点构建最短路问题计算量较大，本文在处理三个问题时分别提出了相应的模型与求解算法，以乘坐时间最短为标准回答了问题一与问题二，对问题三提出了最短路模型。
在问题一建模过程中，我们以任意两条线路是否可以直接换乘为突破口，建立了以每条线路为顶点，两条线路之间的换乘信息为弧的图，将问题一归结为弧长可变的最短路问题，提出了结合动态规划方法与分枝定界思想的算法。
首先将题目所给出的路线与站点信息翻译为两条线路是否可以直接相交以及在何处相交的信息矩阵；其次以换乘时间最短或者费用最小为决策函数，建立动态规划问题；再次设计相应的算法进行求解。
通过求解，以最短时间为目标，问题一的结果如下所示（以
（1）,
（2）组为例，其它见正文表1）：
组
（1）：
S3359→S1828，S3359¾¾L15®S2903¾¾L¾201®S458¾¾L¾41®S1828，最短时间
73分钟，费用3元；组
（2）：
S1557→S0481，S1557¾¾L¾84®S1919¾¾L1¾89®S3186¾¾L4¾60®S481，最短时间
106分钟，费用3元。
同时文章对运算结果进行了相关分析。
在问题二建模过程中，沿用问题一的求解思想，将新增加的地铁视为新的线路，将所有线路信息转化为新的转乘矩阵，同时按照新的背景得到新的乘车时间与费用计算方法，同样以最短时间为目标，相同的算法可以得到问题二的结果（以（5）,（6）组为例，具体见正文表2）：
组（5）：
S0148→S0485，
S0148¾¾L¾24®S1487-D02¾¾T1®D21-S466¾¾L¾51®S485最短时间87.5分钟，费用5元；
组（6）：
S0087→S3676，S0087-D27¾¾T2®D36-S3676，最短时间28分钟
（已经加上地铁站到地面站点的步行时间，其中地铁运行时间20分钟），费用3元。
在问题三建模过程中，由于增加了步行的信息，问题一、二的方法无法直接使用，文章建立了一个新的最短路问题。
以每个站点为顶点，以两个顶点之间的最短路径（最短达到时间或者最小到达费用）为弧构造有向图，其中最短达到时间由问题二得到的两个站点之间使用公交网络的换乘时间与步行时间的最小值决定。
从而将问题三归结为一个有向图的最短路模型，文章对此模型给出了算法建议。
最后文章对所提出的模型进行了优缺点分析与推广评价。
29
关键词：
城市公交线路、图与网络、最短路模型、动态规划
一、问题重述：
近些年来，城市公共交通系统有了很大发展，使得公众的出行更加通畅、便利。
绝大多数市民出行时首先会考虑选择公交设施，同时也面临如何在众多条线路中如何选择合适线路的问题。
针对市场需求，要求开发一个解决公交线路选择问题的自主查询计算机系统，可以满足查询者的各种不同需求，对不同的起点和终点给出最佳的公交转乘路线。
竞赛要求设计线路选择的模型与算法，解决以下三个问题：
1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。
并根据附录数据，利用模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。
（1）、S3359→S1828
（2）、S1557→S0481 （3）、S0971→S0485（4）、S0008→S0073 （5）、S0148→S0485 （6）、S0087→S3676
2、同时考虑公汽与地铁线路，解决以上问题。
3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。
二、问题分析：
（1）从影响出行选择的因素看，每个人主要会从两个标准对线路进行选择与优劣衡量：
从起点到终点所需要的总时间最短；从起点到终点需要花费的费用。
（2）从本质上讲，选择线路的问题可以归结为最短路问题，但是考虑到转乘线路需要时间，并且一条公交线路不能按照站点进行拆分，因此以每个站点构造路线图不利于解决问题。
注意到从起点站到目标站关键是选择乘坐哪些公交线路，需要在公交线路中如何选择转乘线路，因此可以以公交线路为顶点，以两个站点之间是否可以转乘为弧构造图，而点到点之间最佳路线的选择可以转化为经过分别两个端点的公交线路集合之间的最短路问题。
同时我们需要任意两个线路之间是否可以转乘的信息。
（3）在给出的线路信息中，我们发现主要有三类线路：
下行线路与上行线路不同，下行线路是上行线路的原路返回，环形线路。
为了区分同一条线路不同的运行方向，我们人为地将每一条线路变为两条线路，这样做既可以分清楚所换乘的是那条线路的哪个方向，同时也可以将两条线路换乘点的信息与每个站点在本条线路上的位置相联系，这样可以用来判断乘坐某条线路公交车从某个站点出发时，可以换乘哪些公交线路（换乘站点必须在乘车点沿着公交车运行方向的后方）。
（4）在公交线路信息中，与决策目标有关的元素还有每条线路的计费方式及每条线路乘坐时花费的时间。
对于计费方式，我们按照单一票价与分段计价进行识别，分段计价与乘坐的站点数有关，这也是我们需要每个站点在每条线路上具体位置的原因；同样运行时间也与站点的具体位置有关。
（5）问题一仅对公共汽车进行分析，可以转化为一个图论问题，使用动态规
划方法进行算法设计与计算。
问题二增加两条地铁信息后，对问题一模型的影响仅在于需要考虑线路数的增加，也只需要将地铁线路与公车线路是否可以换乘的信息表现出即可。
问题三增加步行信息后，问题变得较为复杂，因为我们并不知道在哪些地方将会步行，因此我们采用简单列举的方法建立模型。
三、 模型假设：
1.乘客在乘坐公交线路过程中，以平均耗时为实际乘车、等车、转乘耗时；
2.乘客在选择转乘线路时，考虑的因素有两个：
花费的时间最少与费用最小；
3.在计算换乘时间时，由公交车换公交车、地铁换地铁、公交车换地铁以及地铁换公交车时不单独计算步行时间；
4.由起点所在站点直接乘坐地铁及从地铁直接到终点时，需单独计算步行时间。
四、 符号说明及定义：
LS（i,j）：
衡量每条线路在每个站点是否停靠的0—1矩阵；
LSN（i,j）：
衡量每条线路经过的每个站点是从起点起算的第几站的矩阵；
i
Li=LS（i,:
）：
线路L的停靠站点向量
C：
存储每条线路的收费信息；
SB（Si）：
停靠Si的所有公交线路的集合；
LB（Li）：
线路Li停靠的所有站点；
Cost（i,a,b）：
乘坐Li从其第a站到第b（b>a）站的费用
Tim（i,a,b）=Tb（b-a）：
表示从线路L的第a站到第b站的时间函数
b i
b
Tb：
表示相邻公汽站平均行驶时间，本题为3
Time（Sm,L,Sn）：
从站点Sm经过一系列线路到达Sn的总时间
TCost（Sm,L,Sn）：
从站点Sm经过一系列线路到达Sn的总费用
TR：
所有线路的转乘矩阵
tr（i,j）：
公交线路Li，Lj两两转乘集合；
V：
为所有站点集合；
E：
有向图中表示两个站点之间最短距离（最少时间或者最少费用）信息
五、 问题一建模与求解
一个城市所有的公交线路和停车点构成了一个复杂的网络图,这些停车点
可以看作该网络图的结点,这些结点由相应的公交路线相连。
结点之间的边就是公交路线。
有的结点之间有边相连（即在某一条公交线上）,有的结点之间无边相连（即这两个结点不在任何一条公交线上）。
因此,城市的公交路线网络图非常复杂,结点很多,公交线路纵横交错。
描述公交线路网络的一个简单方法是以每个站点为顶点，以两个顶点之间的公交线路信息（需要花费的时间、花费的费用等）为弧建立赋权图，本题中站点个数共有3957个，这样得到的矩阵将是3957阶方阵，如此庞大的矩阵在使用计算机处理时，将会遇到很大的困难，我们所拥有的计算机硬件达不到要求。
因此我们需要从另外一个角度重新描述公交线路网络。
进而我们可以使用通过动态规划方法、最短路方法等建模思想构造算法、编写程序，使问题得到圆满地解决。
5.1原始数据处理
（1）公交线路处理
我们将题中给出的520条公交线路进行处理，将每条线路人为地变成两条，每一条代表一个具体的行驶方向，得到1040条起点终点固定的单方向行驶的公交线路。
具体的处理方法如下：
a）对于上行与下行站点相同的线路，如图1中（a），将上行与下行视为不同的两条线路，每一条作为一条新的单方向行驶的公交线路，即
A®B及B®A；由于两个走向站点相同，因此这两条线路经过的站点集合相同，但是每个站点在两条线路中的位置不同，这对衡量从某个站点出发乘坐该线路是否可以换乘其他线路，以及换乘哪条线路非常重要（详细说明见后续命题）；
b）对于上行与下行站点不同的线路，如图1中（b），将上行方向与下行方向视为两个不同的线路A®B及B®A，这两条线路经过的站点集合不同，从而每个站点在两条线路中的站点位置也不同；
c）对于环形线路，如图1中（c），起点与终点为A的环形道路，从中间某个站点断开，作为前一路线的终点以及后一路线的起点，这样就形成两条新的线路。
由于环线中间某些站可能重合，因此分割线路时要保证同一线路中没有公共站点（编程设计的需要）并且兼顾两条新线路长度均等。
A B
（a）
A B A
（b） （c）
图1
通过以上处理，我们将所有情况统一转化为以起点和终点确定的1040条具有单一方向的有向线段。
（2）建立站点与线路关系矩阵
利用
（1）得到的1040条线路及其上每个站点的信息，构造下列两个反映
1040条线路与3957个站点相关信息的矩阵，称为停靠信息矩阵：
LS与LSN。
LS为1040行3957列的矩阵，元素为0或者1，反映每条线路是否经过每个站点，元素取值为：
ì1
0
LS（i,j）=í
î
线路Li经过站点Sj 。
线路Li不经过站点Sj
LSN也为1040行3957列的矩阵，元素为0或者某个自然数k，反映每条线路经过每个站点时，从该线路的起始点算起，该站为第k站，元素取值为：
ìk
LSN（i,j）=í0
站点Sj为线路Li的第k站。
线路L不经过站点S
î i j
定义向量Li=LS（i,:
）为线路L的停靠向量，LB（L）为线路L停靠的站点集
i i i
合：
LB（Li）={Sj|LS（i,j）=1}。
SB（Sj）为停靠站点Sj的公汽线路集合：
SB（Sj）={Li|LS（i,j）=1}。
（3）每条线路的计费信息
定义向量C=（c1,c2,L,c1040）为每条线路的计费信息，按照题中所给出的计费信息，元素取值为
=
ì0
ci í
î1
第i条线路为单一计费。
第i条线路为分段计费
若ci=0，则线路Li为单一收费，票价均为1元；
若ci=1，则线路Li为分段收费，按照题中所给定的公汽票价方案，可以得到乘坐Li从其第a站到第b（b>a）站的费用为Cost（i,a,b）=cik+1，其中
k=min（b-a-1,2）。
20
可以发现单一收费情形可以并入上述公式，因此所有公汽线路（包括单一收费与分段收费）的费用计算可以合并为一个函数Cost（i,a,b）=cik+1，其中
k=min（b-a-1,2）。
称函数Cost（i,a,b）为沿着公交线路L从其第a站到第b站
20 i
的费用函数。
b
相应于费用函数，用函数Tim（i,a,b）=Tb（b-a）表示从该线路的第a站到第
b
b站的时间函数，其中Tb表示相邻公汽站平均行驶时间，在本题中取值为
b
Tb=3。
5.2判别两条线路之间是否可以换乘，得到任意两条线路之间的换乘矩阵
命题1：
乘客从Sm出发，乘坐线路Li可以直接到站点Sn的充要条件为
LS（i,m）=LS（i,n）=1，并且LSN（i,m）同时可以得到花费的时间
Time（Sm,Li,Sn）为
Tim（i,LSN（i,m）,LSN（i,n））=3（LSN（i,n）-LSN（i,m））
花费的车费TCost（Sm,Li,Sn）为Cost（i,LSN（i,m）,LSN（i,n））。
i
命题2：
设线路L的停靠向量为Li=（LS（i,1）,LS（i,2）,...,LS（i,3957））, L的
j
停靠向Lj=（LS（j,1）,LS（j,2）,...,LS（j,3957））,i¹j,那么，线路L可以转乘线路
i
i
j
j
L的充要条件为Li+Lj中有元素2，并且2所对应的站点为L到L
的中转站。
证明：
按照停靠向量的定义，Li,Lj均为元素为0或者1的向量。
因此若
Li+Lj的第k个分量为2，（Li+Lj）（k）=LS（i,k）+LS（j,k）=2，则
LS（i,k）=LS（j,k）=1，说明两条线路在Sk站点相交，从而可以在Sk站点处换乘。
定义：
设Li与Lj在Sk处相交，i¹j,Sk在Li上为第a站，a=LSN（i,k），
在Lj上为第b站，b=LSN（j,k），则称二元数对（a,b）为线路Li到Lj的换乘数对，记tr（i,j）={（a,b）|（a,b）为线路Li到线路Lj的一个换乘数对}。
若Li与Lj不可换乘，
则记tr（i,j）=Æ；同时tr（i,i）=Æ。
注意到换乘数对与换乘线路之间的关系，若（a,b）为线路Li到Lj的换乘数
对，则（b,a）为线路Lj到Li的换乘数对。
将所有线路之间的换乘信息构成矩阵，称此矩阵为换乘矩阵，记为TR，
é
ê
TR=ê
Æ
tr（2,1）
tr（1,2）
Æ
L tr（1,1040）ù
ú
L tr（2,1040）ú
。
ê M M O M ú
ê ú
ëtr（1040,1） tr（1040,2） L Æ û
同时集合TF（Li）={Lj|tr（i,j）¹Æ}表示能够与Li实现直接换乘的线路集合。
命题3：
设线路Li到线路Lj的换乘数对为乘客从站点Sm出发，乘坐线路Li，
通过换乘线路Lj，到达站点Sn的充要条件为在tr（i,j）中存在一个换乘数对（a,b），
使得LS（i,m）=1,LS（j,n）=1且LSN（i,m）b。
同时,花费时间
Time（Sm,Li,Lj,Sn）为：
b
Tim（i,LSN（i,m）,a）+Tim（j,b,LSN（j,n））+Tb，
其中Tb表示公汽换乘公汽的时间，在本题取值为Tb=5。
花费费用
b b
TCost（Sm,Li,Lj,Sn）为
Cost（i,LSN（i,m）,a）+Cost（j,b,LSN（j,n））。
命题4：
若Sm经由Li转乘Lk再转乘Lj到Sn，而tr（i,k），tr（k,j）分别为
Li到Lk，Lk到Lj的换乘数对集合，则必存在（a1,b1）Îtr（i,k），（a2,b2）Îtr（k,j）使得
LS（i,m）=1,LS（j,n）=1，LSN（i,m）b2,b1同时，花费时间Time（Sm,Li,Lk,Lj,Sn）为
Tim（i,LSN（i,m）,a）+Tim（k,b,a）+Tim（j,b,LSN（j,n））+2Tb
1 1 2 2 b
花费费用TCost（Sm,Li,Lk,Lj,Sn）为
Cost（i,LSN（i,m）,a1）+Cost（k,b1,a2）+Cost（j,b2,LSN（j,n））。
按照上面所述的四个命题的规律，可以得到具有任意条中转线路的公汽路线的条件以及所花费的时间与费用。
命题5：
若乘客从Sm出发，通过换乘线路Li1®Li2®L®Lip，到达Sn，
则必存在p-1个换乘数对（a1,b1）,（a2,b2）,L,（ap-1,bp-1）使得：
（a）LS（i1,m）=1，LS（ip,n）=1；
（b）（a1,b1）Îtr（i1,i2）,（a2,b2）Îtr（i2,i3）,L,（ap-1,bp-1）Îtr（i（p-1）,ip）
（c）LSN（i1,m）同时花费的时间Time（Sm,Li1,L,Lip,Sn）为
Tim（i,LSN（i1,m）,a）+Tim（i2,b,a）+L+Tim（i（p-1）,b
a ）+Tim（ip,b
LSN（ip,n））+（p-1）Tb
1 1 2
p-2
p-1
p-1 b
花费的费用TCost（Sm,Li1,L,Lip,Sn）为
Cost（i,LSN（i1,m）,a1）+Cost（i2,b1,a2）+L+Cost（i（p-1）,bp-2,ap-1）+Cost（ip,bp-1,LSN（ip,n））
。
5.3任意两点之间寻找换乘方式的动态规划模型
利用5.1中所得到的元素，构造反映任意两条线路之间的换乘图，如图2所示，其中图的顶点表示每一条线路（一共有1040个顶点），而两个顶点之间的弧表示两个顶点的换乘信息。
L2
tr（i,j）
L1 Lj Lj L1040
L3
图2所有公汽线路的换乘图
需要说明的是，由于tr（i,j）与Li与Lj的顺序有关，因此在后续提出的动态规划模型中，将按照计算的次序与换乘线路的先后次序将换乘图配上不同的方向，这些方向与计算tr（i,j）以及花费的时间与费用有关。
假设某个乘客需要从Sm站点通过公汽网络到达站点Sn，则我们需要寻找从
公汽集合SB（Sm）到达集合SB（Sn）在上述换乘图中的最短路径，这样问题一可以
归结为下面寻求最短路问题：
寻找换乘线路Li1®Li2®L®Lip，使得Li1ÎSB（Sm），LipÎSB（Sn），乘客
从Sm出发，可以通过此线路到达Sn（满足5.2节中命题5），并且在所有可能的
转乘线路中在下列两个目标下最优：
（a）所花费的总时间最短；
（b）所花费的总费用最小；
这两个目标函数由5.2节命题5给出。
5.4求解问题一的算法
由于上述最短路问题中所涉及的数据量较大，并且不同于传统最短路问题之处在于在图中我们得到的并不是相邻两点的路径，而是可以换乘的两条线路换乘的信息，因此不能直接用求解传统最短路问题的算法，如Dijstra算法进行计算。
为了解决上述问题，我们给出下列算法，算法的主要思想如下：
i.使用动态规划的顺序或者逆序算法，将求解此问题的三个主要方面：
a）判断是否能在所给出的两点Sm,Sn实现换乘；
b）计算每次换乘所需要的时间与费用；
c）判别是否达到时间最短或者费用最小结合在一起。
ii.在算法设计过程中，采用整数线性规划的分枝定界思想，以换乘的次数为分枝变量，以已经实现换乘情形下的时间或者费用为定界变量，实现在增加换乘次数的同时判别没有到达终点的换乘序列是否可能达到最优，即若当前存储实现成功换乘的最短时间或者最小费用为a，则以a为剪枝标准，在没有达到终点的线路中，如果所花费的时间或者费用已经超过a，则不需要进一步换乘寻找。
算法I（给定起点Sm与终点Sn，判别两个站点是否在同一条线路上）
1）分别求出停靠Sm与Sn的所有线路集合SB（Sm），SB（Sn）；
2）若SB（Sm）ÇSB（Sn）=Æ，则退出；
3）若SB（Sm）ÇSB（Sn）¹Æ，则对任意的线路LiÎSB（Sm）ÇSB（Sn），计算所需时间与费用；
m
4）返回最小的时间T1或者费用C1，以及对应的线路L。
算法II（给定公汽线路停靠信息矩阵、换乘矩阵，计算任意起点到终点的最优路径）：
1）输入起点Sm，终点Sn，对最短时间后者最小费用变量赋初值T*=inf，
C*=inf，k=1；
2）按照算法1，判断Sm，Sn是否在一条公汽线路上，若在一条线路上，
T=T1，C=C1，MinL存储乘坐信息，k=k+1否则转下一步；
* *
3）写出SB（Sm），FL=SB（Sm）；
4）对任意的LiÎFL，按照换乘矩阵写出能够与Li进行换乘的所有线路
TR（Li），按照5.2节命题3判断TR（Li）中的线路能否实现一次换乘到
Sn；
5）若存在能够一次换乘到Sn的线路，计算需要的最短时间或者最小费用
Tk,Ck，转6），否则转7）；
6）若T>Tk，则T=Tk或者若C>Ck，则C=Ck，MinL存储换乘信息，
* * * *
k=k+1，否则转7）；
7）对于不能实现换乘一次到达Sn的线路Lj中，计算Sm通过Lj能够换乘到
的线路得换乘点Sp需要的时间或者费用，Time（Sm,Lj,Sp）或者
TCost（Sm,Lj,Sp），以T*或者C*为标准判断，若Time（Sm,Lj,Sp）>T*或者T
升级会员 