乘公交,看奥运模型的建立与求解

1、乘公交，看奥运模型的建立与求解【摘要】本文在对大量数据的分析并结合乘客乘坐公交车的心里，建立了以最小换乘法为基础的公交换乘模型。乘客选择公交出行首先是考虑到公交的舒适性和方便性，其次才会考虑时间和费用的最大合理性。因此，本文以最小换乘为首要目标建立基本的公交换乘模型。我们首先想到的是广度优先搜索，即欲查找从起始站点A 到目的站点B 的最短路径,可以从A点出发, 以公交车路线为基础进行广度优先搜索，到B 站点即结束。此时找到B 站点时，一定是转车次数最少的。在广度优先搜索的基础上，我们建立了问题一的数学模型：I） BusA为途径A站的所有路线的集合，BusB为途径B站的所有路线的集合。如果Bus

2、ABusB，说明A到B站可以不用转车就能到达。直接可以得到A，B站的直达路线。II） 如果BusABusB，再依次从与BusA有公共站点的公交线路Bus（i为从A站转乘i次可乘坐的公交路线，i=1,2）中查找是否与BusB有公共路线，若存在则算法结束，若不存在则按此步骤继续直到查找到为止。III） 如果存在多种方案的转乘次数相同，则依据次要目标费用最少和时间最短选取最佳路线。由于实际生活中人们往往对转乘次数有一个可以承受的范围，为减少计算量，本文中我们假设转乘次数为i<=3次为可以接受的乘坐方案，若i>3则认为路线不可达。对问题二的模型是建立在问题一模型的基础上，我们把地铁线路当成

3、特殊的公交线并入公交系统，在路线的选择上同一规划，仍以最小转乘代价为首要目标，对问题一的模型进行了合理的修改。问题三加入了步行的因素，使得可以乘坐的路线大大增加。步行换乘通常有以下的两种类型：1、两条公交线路相交, 但不存在相交的站点，行人需要下车后步行到邻近的站点进行换乘。2、两条公交线路不相交，但两行车路线上有相邻站点, 行人选择下车步行到邻近站点进行换乘。如果步行的代价足够小，而且可以有效减少换乘次数，完全可以把步行考虑进路线选择中。【关键词】公交最佳路线最小转乘法 广度优先搜索一、 问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部

4、分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828

5、 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、 模型假设1. 假设乘客都能搭上自己想要乘坐的公交车或地铁；2. 假设交通顺畅，没有拥堵现象；3. 采用同一站点名的站点均认为是同一站点，没有空间上的差异；4. 假设公交车都按时发车、按时到达，乘客无需花费多余的时间等车；5. 假设整个公交网络是一个连通图，任意两个站点都有路可达；6. 假设超过三次转乘次数的路线被认为是

6、不可达。三、 符号说明编号为i的公交站点 编号为i的公交路线编号为i的地铁站T从源站到目的站花费的时间，单位为分钟M 从源站到目的站花费的金钱，单位为元BusA途径A站的所有路线的集合，A为站点名Line 公交及地铁线路集合四、 问题分析乘客出行选择公交路线时，首先考虑的是转车次数，其次才是路径的长度。因为转乘次数的增加必定会导致乘车费用的增加，同时也会增大时间的开销，如转乘途中步行花费的时间，等车的时间等等。空间上距离最短的路径, 对于公交乘客来说并不一定是最合理的路径。转车途中各种不确定因素也会大大增加。乘客往往会选择尽量少的转车路线以避免各种不必要的麻烦。对于大多数选择公交车出行的人们来

7、说，尽量少的转车次数才应当是被首先考虑的，其次才是时间和费用。本文也是基于乘客的这种想法，在寻求最小转乘次数的基础上考虑时间和费用的最优配置。在附件给出的数据中光公交线就有520条，公交站点更是多达3957个，如此大的数据量如果用手动的方法根本是没法完成的。解决问题的根本是要有一个好的算法，借助计算机求解来实现乘车路线的优化。传统的Dijkstra算法求的是从某一站到其他所有站点的最短路径，因此，要查找A站到B站的最短路线，先要求出A站到其他所有站的最短路线，然后才能在求出的这些线路中找出到B站的路线。在本题中，我们要求的只是A站到B站的最优路线，而花费大力气求出的A站到其他站的路线都不是我们

8、想要的，可见用Dijkstra算法在求解公交线路时的效率是非常低的。而Dijkstra算法求出的最短路径并不一定适合乘客的出行，为了达到最短路径的目的，乘客往往要不停的转车，这样的结果是没有实际意义的。因此，Dijkstra算法不适合本题的求解。本文以转乘次数最少为首要目标建立公交路线模型，在满足最小转乘次数的条件下以最少时间、最少费用为次要目标进行求解。五、 模型建立与求解一、模型建立问题一：1）问题一中只要求出6组站点的最优公交转乘路线即可。我们首先考虑直达的情况，即不需转车就可到达目的站。（如图-1所示）设BusA为途径A站的所有路线的集合，BusB为途径B站的所有路线的集合。如果Bus

9、ABusB，说明A到B站可以不用转车就能到达。取Line=BusABusB，只要计算经过Line中的路线到达B站的所有情况，从中选出最少时间或最少费用的路线即可。若BusABusB=，即转入步骤2）。AB图-12）需要经过一次转车时BusABusB=，设Bus为所有与BusA有公共站点的路线的集合，若同时满足BusBusB，说明A站到B站只需经过一次转车就可到达。取Line1=BusBusB，依次遍历Line1中各种情况，找出最优解即可。（图-2）ACB图-23）若BusBusB=，则A到B需转车2次或2次以上，设Bus为所有与Bus有公共站点的路线的集合，也即Bus为所有在A站转车两次能够搭

10、乘的公交路线。同步骤2），计算Line2= BusBusB的所有情况，若Line2=，类似的计算Bus和Line（i为转车次数），依此类推。如果存在多种选择，则以时间和费用为第二目标进行排除，选出最优路线。ACDB图-3问题二：问题二中把地铁转乘纳入最优线路的选择中，对问题二的求解并不需要重新建立模型求解，只需在问题一的求解出的几条最优线路中考虑，对模型进行适当的修改即可。我们把2条地铁路线当成特殊的公交线并入整个公交系统中，同样在满足最小转乘的基础上考虑时间和费用的最优，因为地铁与地铁，地铁与公交之间的转乘代价也是相当高的。二、模型的求解问题一：为了利用计算机求解，我们按照上面的模型和算法设

11、计了程序（见附录）用于计算公交线路。所得的结果分析如下：(1)S3359S1828第1条：S3359S1241S1828，T=107分钟，M=3元S3359S2026S1132S2266S2263S3917S2303S2301S3233S0618S0616S2112S2110S2153S2814S2813S3501S3515S3500S0756S0492S0903S1768S0955S0480S2703S2800S2192S2191S1829S3649S1784S1241S1784S1828第2条：S3359S1784S1828，T=101分钟，M=3元S3359S2026S1132S2266

12、S2263S3917S2303S2301S3233S0618S0616S2112S2110S2153S2814S2813S3501S3515S3500S0756S0492S0903S1768S0955S0480S2703S2800S2192S2191S1829S3649S1784S1828第3条：S3359S2606S1828，T=125，M=3S3359S2026S1132S2266S2263S3917S2303S2301S3233S0618S0616S2112S2110S2153S2814S2813S3501S3515S3500S0756S0492S0903S1768S0955S0480S

13、2703S2800S2192S2191S1829S3649S1784S1241S3695S2606S2599S3512S3695S1241S1784S1828第4条：S3359S0519S1828，T=140，M=4S3359S2026S1132S2265S2654S1729S3766S1691S1383S1381S1321S2019S2017S2159S0772S0485S2385S2810S3189S0964S0464S0271S0297S1555S0519S1893S3496S1883S3400S1159S1160S0576S0578S3095S0096S0095S1193S0105S1

14、194S1189S2801S0590S1240S1241S1784S1828第5条：S3359S2364S1828，T=137，M=3S3359S2026S1132S2265S2654S1729S3766S1691S1383S1381S1321S2019S2017S2159S0772S0485S2385S2810S3189S0964S0464S0271S0297S1555S0519S0516S1980S2364S0727S0304S3192S0294S3057S2262S0301S1119S0250S2604S2606S2599S3512S3695S1241S1784S1828 第6条：S33

15、59S0727S1828，T=137，M=3S3359S2026S1132S2265S2654S1729S3766S1691S1383S1381S1321S2019S2017S2159S0772S0485S2385S2810S3189S0964S0464S0271S0297S1555S0519S0516S1980S2364S0727S0304S3192S0294S3057S2262S0301S1119S0250S2604S2606S2599S3512S3695S1241S1784S1828第7条：S3359S0304S1828，T=137，M=3 S3359S2026S1132S2265S26

16、54S1729S3766S1691S1383S1381S1321S2019S2017S2159S0772S0485S2385S2810S3189S0964S0464S0271S0297S1555S0519S0516S1980S2364S0727S0304S3192S0294S3057S2262S0301S1119S0250S2604S2606S2599S3512S3695S1241S1784S1828第8条：S3359S3192S1828，T=137，M=3S3359S2026S1132S2265S2654S1729S3766S1691S1383S1381S1321S2019S2017S215

17、9S0772S0485S2385S2810S3189S0964S0464S0271S0297S1555S0519S0516S1980S2364S0727S0304S3192S0294S3057S2262S0301S1119S0250S2604S2606S2599S3512S3695S1241S1784S1828在上面相同转乘次数的8条线路中我们可以看到费用大都是3元，但是第2条线路上花费的时间最少。所以最优路线为S3359S1784S1828，T=101，M=3。根据第一对起始路线的方法，我们同理可得其他5对起始站之间的最佳路线分别为：(2)S1557S0481：S1557S1919S2424

18、S0481，T=112，M=3(3)S0971S0485：S0971S2184S0485，T=128，M=3(4)S0008S0073：S0008S2083S0073，T=83，M=2(5)S0148S0485：S0418S0036S3351S0485，T=100，M=3(6)S0087S3676：S0087S3469S3676，T=65，M=2问题二：如果出行时考虑上地铁路线，那么我们出行的路线可能会有新的乘车路线。根据假设,同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。也就是说，你只要花上地铁的3元票价就可以在任务地铁路线上进行换乘，而不需要花费多余的费用。在问题

19、一中，我们通过数学建模解决了公交换乘的问题，现在我们在原有公交线路基础上加入了地铁线路。我们可以假设地铁线路是当成是一条新的公交路线，而把所有地铁所能到达的站点连成一体，对于价格上只要多出3元。如果不考虑地铁换乘和行驶的时间的话，我们可以把地铁所能到达的几个点当成一个集合点来处理。对于问题一中的（1）（3）（4）这三个一次公交换乘就能解决的出行问题，由于出发站点和目的站点都不在地铁线路上。如果我们在半路换乘地铁只是会增加出行的麻烦性和价格，故我们不需要做任何变动。对于（6）来说，S0087在地铁的D27站，S3676在地铁的D36站，所以我们可以选择乘坐地铁T2，这样只需要花时22.5分钟和3

20、元的地铁票价。对于问题一中的（2）和（5）。这两种情况属于二次公交换乘情况，由于这两种情况的出发站点点和目的站点都不在地铁线路上，所以出发和最后到达所坐的都必须是公交车，则如果要换乘地铁则要选择中间的那次换车。现在我们来看几个数据的比较：相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其

21、中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）如果仅从价格上考虑，我们选择的应该是公交路线，因为地铁的价格为3元，相当于分段计价公交行驶40站以上的价格，为公交路线最贵的价格。所以从金钱花费上来考虑的话，二次换乘的过程中不选择地铁。如果从时间上考虑的话，只选用公交换乘（2）耗时112分钟，（5）耗时100分钟，改成地铁换乘会增加地铁与公交，公交与地铁以及等车的时间，相应的换乘复杂度也会增加，故不予考虑。 问题三：加入步行因素现实生活中，出行时在选择行车路线时可以通过在部分站点步行小段距离再转车以减少换乘次数的现象。也就是说 ，人们

22、转车的时候并不是在所下的站点，而是在所下站点的附近站点换车的。通常有以下的两种类型：1、两条公交线路相交, 但不存在相交的站点，行人需要下车后步行到邻近的站点进行换乘。2、两条公交线路不相交，但两行车路线上有相邻站点, 行人选择下车步行到邻近站点进行换乘。所以在选择两站点最佳路线的时候如果需要考虑到现实情况，则要加入步行因素。步行类型I步行类型II步行路线根据这种因素，我们对我们前面的模型进行适当的修改。将问题一模型中所有的BusA设为经过A站点及其周边站点的公交线路的集合，同理BusB设为经过B站点及其周边站点的公交线路的集合，其余部分同问题一的模型。六、 模型评价和改进本题所做的模型完全是

23、建立在数据的基础上，与实际情况可能存在不一致。在实际中，最少换乘数并不一定是时间最少或者价格最省的路线。因为，对于公交线路来说，同样的两个站点在不同的路线中，两站点之间的站点数会不一样。而且实际生活中，相邻的两个站点有可能出现没有路线直达的情况，这时我们可以选择步行，这样对最少换乘算法的选择也会产生不一致。如果知道一个城市公交线路的数据，同时得到这些数据所形成的实际路线图形，我们可以在图上画出两站点相连的直线，通过围绕直线附近的行车路线来选择我们换乘的车次。同样，我们可以把出发站点设置为圆心，以一定量的时间或者是金钱为单位半径做出行人可到达的范围，通过对半径的依次增加使这个范围得到扩大，最终包

24、括目的站点以得到最优解。七、参考文献1李玉芝,方源敏,城市公交查询系统的设计与实现,地矿测绘, 2006, 22 (1) : 352王建林,基于换乘次数最少的城市公交网络最优路径算法, 经济地理, 2005年9月:6736763孙湧 基于宽度优先遍历树的公交线路换乘算法, 深圳职业技术学院学报, 2004 年第4 期:10114张帅,彭玉青,赵镇,李志强,蚂蚁算法在公交查询最短路径求法中的应用,华中科技大学学报(自然科学版), 2003年10月:3133145闫小勇,王扬,刘海宁,公交乘车路线查询中的换乘识别方法,交通标准化,157期:173174附录：/*主要功能：找经过某一站点的所有公交线

25、路*/#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <vector>using namespace std;class Station public:vector<int> vec;string name;Station () Station (const string& name) (*this).name=name;bool operator = (const Station& sta

26、) const return =name;bool operator < (const Station& sta) const return name<;int main(void) ifstream in("input.txt");ofstream out("output.txt");int i, j, pos=0;string str;Station temp;vector<Station> sta;vector<Station>:iterator it;int k=0;wh

27、ile (in>>str) if (str0 = 'L') +pos;else if (str0 = 'S')it=find(sta.begin(), sta.end(), Station(str);if (it!=sta.end() if (find(*it).vec.begin(), (*it).vec.end(), pos)=(*it).vec.end()(*it).vec.push_back(pos);else sta.push_back(Station(str);stasta.size()-1.vec.push_back(pos);sort

28、(sta.begin(), sta.end();for (i=0; i<sta.size(); +i) out<<<<" "<<stai.vec.size()<<endl;for (j=0; j<stai.vec.size(); +j) out<<stai.vecj<<" "out<<endl;return 0;/*主要功能：计算转0次、1次公交的情况*/#include <iostream>#include <fstrea

29、m>#include <string>#include <vector>#include <cmath>#include <algorithm>using namespace std;class Station public:string name;vector<int> vec;bool operator = (const Station& sta) const return =name;bool operator != (const Station& sta) const return sta

30、.name!=name;class BusLine public:vector<string> vec;vector<Station> arrSta(3960);vector<BusLine> arrBus(525);bool isLink(const Station& sta1, const Station& sta2, int& pos) int i, j;bool flag=false;for (i=0; i<sta1.vec.size(); +i) for (j=0; j<sta2.vec.size(); +j)

31、if (sta1.veci=sta2.vecj) pos=sta1.veci;flag=true;break;if (flag) return true;else return false;bool isLink(const vector<string>& vec1, const vector<string>& vec2, vector<string>& vec) int i;bool flag=false;for (i=0; i<vec1.size(); +i) if (find(vec2.begin(), vec2.end(

32、), vec1i)!=vec2.end() vec.push_back(vec1i);flag=true;if (flag) return true;else return false;vector<string> lineChangeToStation(int num) vector<string> vec;int i;for (i=0; i<arrBusnum.vec.size(); +i) vec.push_back(arrBusnum.veci);return vec;int distance (int num, string start, string

33、end) vector<string>:iterator it1=find(arrBusnum.vec.begin(), arrBusnum.vec.end(), start);vector<string>:iterator it2=find(arrBusnum.vec.begin(), arrBusnum.vec.end(), end);return abs(it1-it2);int main(void) vector<string> first, last;string start, end, str;int i=1, j=0, k=0, num, nu

34、m1, num2;ifstream in1("output.txt");while (in1>>str>>num) arrS=str;while (num-) in1>>j;arrStai.vec.push_back(j);+i;in1.close();i=0;ifstream in2("input.txt");while (in2>>str) if (str0='L') +i;else if (str0='S') if (find(arrBusi.vec.b

35、egin(), arrBusi.vec.end(), str)=arrBusi.vec.end()arrBusi.vec.push_back(str);in2.close();int count=0;while (true) if (count+!=0) break;cout<<"Enter start and end:"cin>>start>>end;num1=(start1-48)*1000+(start2-48)*100+(start3-48)*10+(start4-48);num2=(end1-48)*1000+(end2-48)

36、*100+(end3-48)*10+(end4-48);if (isLink(arrStanum1, arrStanum2, i) cout<<"True"<<endl;else int Min=INT_MAX;for (i=0; i<arrStanum1.vec.size(); +i) first=lineChangeToStation(arrStanum1.veci);for (k=0; k<arrStanum2.vec.size(); +k) last=lineChangeToStation(arrStanum2.veck);vec

37、tor<string> temp;if (isLink(first, last, temp) for (j=0; j<temp.size(); +j) num=0;num+=distance(arrStanum1.veci, start, tempj)*3+distance(arrStanum2.veck, tempj, end)*3+5;cout<<tempj<<" "<<num<<endl;if (Min>num) Min=num;if (Min!=INT_MAX) cout<<&quo

38、t;Min="<<Min<<endl;else cout<<"经过转一次，找不到"<<endl;return 0;/*主要功能：计算转两次公交车的情况*/#include <iostream>#include <algorithm>#include <fstream>#include <string>#include <vector>#include <cmath>using namespace std;/站点class Station publ

39、ic:string name;vector<int> vec;bool operator = (const Station& sta) const return =name;bool operator != (const Station& sta) const return !=name;/公交线路class BusLine public:vector<string> vec;vector<Station> arrSta(3960);vector<BusLine> arrBus(525);/判断两条

40、公交路线是否相连bool isLink(const Station& sta1, const Station& sta2, vector<int>& vec) int i, j;bool flag=false;for (i=0; i<sta1.vec.size(); +i) for (j=0; j<sta2.vec.size(); +j) if (sta1.veci=sta2.vecj) vec.push_back(sta1.veci),flag=true;break;if (flag) return true;else return false

41、;/计算两站的距离int distance (int num, string start, string end) vector<string>:iterator it1=find(arrBusnum.vec.begin(), arrBusnum.vec.end(), start);vector<string>:iterator it2=find(arrBusnum.vec.begin(), arrBusnum.vec.end(), end);return abs(it1-it2);int main(void) vector<string> first, l

42、ast;string start, end, str;int i=1, j=0, k, num, num1, num2, sum, min;ifstream in1("output.txt");while (in1>>str>>num) arrS=str;while (num-) in1>>j;arrStai.vec.push_back(j);+i;i=0;ifstream in2("input.txt");while (in2>>str) if (str0='L') +i;else if (str0='S') if (find(