以最小换乘次数和站数为目标的公交线路选择

以最小换乘次数和站数为目标的公交线路选择摘要一、问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具(简称公交，包括公汽、地铁等)出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站一终到站之间的最佳路线(要有清晰的评价说明)。(1)、S3359一S1828(2)、S1557一S0481(3)、S0971一S0485(4)、S0008一S0073(5)、S0148一S0485(6)、S0087—S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、问题分析这是一个公交线路选择的自主查询系统设计问题。为了设计这样一个系统，其核心是线路选择的模型与算法设计。路线是指：S1L1-S2—S3—^^Sn其中S起点，S是终点，s是转站点，乙乘车线路。即是告诉查询者从起点到1ni'终点坐哪列车到哪个站点换乘最终到达终点。对于问题一，仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。一般情况下，选择公交线路时，可行的乘车方案一般有多个。而出行者考虑的因素很多，如换乘次数、旅途时间、费用等，不能简单的抽象为最短路问题⑵。所以可以建立多目标分层最优模型。算法设计方面，考虑将线路进行抽象处理，将分上下行的线路、双向行驶的线路和环行线路抽象为一条，即将上下行的线路和双向行驶的线路连接成一条。而算法设计中确定输出乘车路线和换乘点到查询界面是难点和重点，针对本题数据庞大的特点，如何克服庞大数据给计算机运行带来的重大负荷是有效解决问题的关键。考虑到时间复杂度和空间复杂度的影响，本文的最少换乘算法考虑采用图论中广度优先搜索思想。本算法得出的解一定是最少换乘次数的路径，但可能解并不唯一⑸。得到最少换乘路径——路线序列(「L，「「)，再分情况讨论相邻两线路的关系，以最少站为目12n1n标求出换乘点。综上即可求出乘车路线和换乘点。在此基础上，将出题目给出的六对起始点到终点的最优路线，并作出详细评价。对于问题二，同时考虑公汽与地铁的线路线路选择问题。考虑到题目给出相同地铁对应的公交站点通过地铁站换乘无需支付地铁费，且这些公交站点在地理位置上非常接近，所以可以抽象为一个新的公交站点，由问题一的模型和算法求解。对于问题三，考虑现实生活中公交及地铁站点的实际分布情况，有时会出现步行小段距离再转车的情况更能节省时间或转车次数。因此，研究此种情况下的出行方案对节省出行时间具有重要的实际意义。三、问题假设与符号说明（一）问题假设1.假设各路车发车频率相同。不考虑路途中遇到红灯时间的拖延。假设任一行驶路段行驶时间交通顺畅，不出现交通堵塞的情形。假设任一乘客的换乘耗时相同，即不考虑换乘车辆到达却因乘客过满等原因无法上车的情形。同一地铁站对应的公交站点地理位置非常接近，假设任意两站点间步行时间近似为0。（二）符号说明重要符号符号含义重要符号符号含义四、模型的建立敏求解4.1问题一：公汽线路选择模型的建立及求解4.1.1数据处理一一线路抽象处理由已给数据可知，公交线路一共可分为三种：上、下行线重合线路，环形线路，上下行线不重合线路。考虑到一般情况下，上、下行线终点需乘客全部下车换乘（可以再次乘坐本辆车次，但必须重新收费），为方便统一对数据进行处理，我们将上、下行线重合线路拆分为两条线路，即：TOC\o"1-5"\h\zSSS3S4S5S6►・AA►SSS4S3S2S1*,件►►将环形线路抽象成一条线路

S1S1*S1图2上、下行线线路不重合不变4.1.2模型分析S1S1一般情况下，选择公交线路时,可行的乘车方案一般有多个。而出行者考虑的因素很多，如换乘次数、旅途时间、费用等，不能简单的抽象为最短路问题⑵。研究表明一般出行者以换乘次数为优先考虑的目标⑶，公交网络的设计也以减少平均换乘次数为重要目标［4］。考虑到实际情况，奥运会期间正直炎热夏天，并有大量观众乘坐公共交通工具，换乘麻烦不为大多数人能接受。因此本文考虑以最小换乘次数为第一目标。另外，题目信息已给出的旅途时间，和乘车计费方式。不失一般性，乘车所需时间、费用都与途经的站数正相关，并且考虑到公交站点及公交路线数据过去庞大，计算机在有限时间内实现耗时较长，为避免过于复杂，本文选择最小途经站数为第二目标。即:在所有可行路径中选择换乘次数最小，且在满足此目标条件下使途经站数最少的路径为最优路径（不唯一）。在确定最优路径前提下计算乘车时间与乘车费用，让出行者全面了解线路信息以做出选择。4.1.2模型的建立TOC\o"1-5"\h\z设起点V，终点V的可行路径集合为TR="r\tR=（v,p,v,p,,v）｝，0dii■0i11i2d■TR.表示起点为v，乘坐线路p到达站点v换乘p到达v，最终到达终点v。i0i11i22d设该线路中换乘次数为N，途径总站点数S，总费用为M，总耗时T。则：iiii1）目标函数我们的目标是希望换乘次数、途径总站数、总费用、总耗时越少越好，即目标一：minniTRi目标二：minsiTRi目标三：minmiTRi目标四：mintiTR目标三、四在目标一、二实现前提下实现，即找到起点到终点的最少换乘次数N及途径最少站数S路线的前提下求乘车费用M及乘车时间T。则N+1M=2mkk=1以换乘为结点，其中mk为每段路的乘车费用；t=3min为相邻公汽站平均行驶时间（包括停站时间），t=5min为公汽换乘公汽平均耗时。2）约束条件N=0,1,2,3...S〔=0,1,2,3...'、Z0T>0ii3）综上，公汽线路选择模型为minniTR

iminsiTRiN+1M=Zmk=1kT=Sxt+10xNt=3min'-<t=5minN=0,1,2,3…iS=0,1,2,3...M>0iT>04.1.3算法设计由模型可知，需设计算法找出最优换乘路径。（一）公交网络描述对公交网络的数学描述是算法设计的基础，本文用四元组Q（V,P,R,L）来表示。其中：V=〈|i=1,2,…，n｝，为节点的集合，包括交通网络中所有的公交站点或可能的出行起始点和终点［1］节点有唯一编号（题目已给出）。P=｛p|i=1,2,...,K｝，为公交线路集合，各线路有唯一编号（题目已给出）。R=（k=1,2,.,K｝，为线路-节点关系集合，假设线路是无方向的。由所该线路包含的站点按通过顺序构成的节点有序序列表示。如第k条线路：r=v,v,...,v"其中v,v是该线路的始发、终点站。k'k1k2kmkk1kmL=(lj=1,2,...,K)，为节点-线路关系集合。如l=S，p.,…，pm为所有经过的节点七线路编号的集合。特别的，若l=O，表示无线路经过该节点。算法准备1。为判断两条线路的相交情况，定义线路相交矩阵C⑸：CA!xK其中'1,若线路？r,■有公共站点C—[0,若线路r，r,.没有公共站点2o确定换乘上界矩阵h1可由Floyd算法求得任意两站点间最少站点数，组成矩阵h，。H'矩阵代表当任意给定的始点、终点匕,七经过最少站点到达时，最多可换乘H，次。而实际路线经过的站点数大于等于H，，即可换乘次数可能会大于或等于H，。考虑到实际情况中，一般情况下，出行者所能接受的换乘次数将十分有限。所以，我们考虑将任意两站点间换乘次数构成的换乘上界矩阵等于两站点到达时的最少站点数矩阵，即H=H'3o公交线路集合的扩展建立起公交线路集合Ak和AD，根据相交矩阵c最优乘车路径的搜索算法设在公交查询网络上，出行者任给定始点、终点vo,七可达，需要确定最优乘车方案输出到终端。首先需要确定换乘次数上界TN，然后根据Q(V,P,R,L)按换乘次数递增进行搜索，算法必在不大于TN次换乘的某此循环中找到可行路径。若可行路径有多条，则寻找总站数最小的为最优路径并输出。算法步骤：Step1输入始点、终点vo,七，确定换乘次数上界tn=HdStep2判断直达线路是否存在10=^pV/p,j=1,2,...，K},

ld=^p,vdGp..,j=1,2,…，k}若lonld尹①，则由直达路线。计算各路线站数，最小者即最优路径，转step5。否则，需要换乘，继续。Step3令A0=l0,i=0Step4若不存在i次换乘的可行路径，则搜索i+1次换乘的可行路径。1o扩充A到A］即寻找所有的路别单元pk(k=1,2,...，K)st.pnp.尹中「.A=AU^p|pnp尹①，peA,k=1,2,…，K}i+1ikkiii即将所有满足与A中路线p相交的路别并到A中构成新的集合A。iiii+12oifA^ni尹中，则有可行路径。对每条可行路径回溯确定线路序号，计算每一条可行路径的总站数，总站数最小的为最优路径。转step5。否则，「=i+1，重复执行step4。Step5根据最优路径上的路线序列确定换乘方案，输出到终端，结束。算法补充：上述算法中的换乘方案确定的算法设计。由上述算法可确定线路序列(不唯一)，选择不同的换乘方案可能导致总站数不同，因此需确定换乘点以保证总站数最少。不是一般性，设上述算法中回溯确定的从起点到终点的线路序列为p,p,…，p；，其中相邻的两线路p,p的12m'ii+1相交关系可能存在以下四种，而相交关系的不同将影响换乘点的度额定，进而影响总站数。单交叉点重合区段多个分离交叉点多个分离交叉点和重合区段由图3所示，实粗线表示线路，，虚线表示线路、。♦'J.L_*>•**■(a)'(b)(c)(d)图6对四种情形换乘点的确定如下：情形(a):换乘点唯一，即交叉点［1］。情形(b)：重合区段中的任一节点都是换乘点，且对站数无影响［1］。情形(d)归类到情形(c):在换站次数为1的前提下，利用穷取法对换乘点进行搜索。五、模型评价及改进六、参考文献赵巧霞，马志强，张发.以最小换乘次数和站数为目标的公交出行算法.计算机应用，24(12)：136-137，146.2