南京市公交转车优化问题

《南京市公交转车优化问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、理学院专业实践报告题目：-南京市公交转车优化问题专业信息与计算科学学生姓名班级学号指导教师实习单位理学院H期2014年2月28日、问题描述问题3在转车次数最小的情况下，设计南京市地铁转乘的算法。南京市任意两个公交站点的最小转车次数的最大值是多少？即最多只要转乘几次公交，即可从南京市的任一站点乘到其它任一站点。解决此问题时，假设相邻公汽站平均行驶时间（伍括停站时间），相邻地铁站平均行驶时间（包括停站时间），公汽换乘公汽平均耗时，地铁换乘公汽平均耗时，公汽换乘地铁平均耗时都是一个定值。对以下站点给出乘车方案：南京邮电大学仙林校区一一新街U南京邮电大学仙林校区中山陵南京邮电大学仙林校区夫子庙南京

2、邮电大学仙林校区湖南路南京邮电大学仙林校区——玄武湖公园二、问题分析针对问题，我们要解决的是合理给出两站点间的最佳路线选择问题。根据调查和分析，对影响线路选择的因素进行筛选，最终确定了以下三个影响较大的因素：第一是换乘次数；第二是乘车站数；第三是乘车费用。从实际情况分析，人们通常宁愿多乘坐几站地也不愿换车，为Y解决换乘次数最少，乘车站数相对较少、乘车费用相对较少的问题，选择Dijkstm方法对问题进行解决，由于问题中出现的站数较少Dijkstra的运算量也不会很大。通过Matlab编制程序，给出了任意两站点间的最佳乘车路线以及换车的地点，最后还提出了进一步的意见和建议。三、问题假设解决此问

3、题时，假设相邻公汽站平均行驶时间（包括停站时间），相邻地铁站平均行驶时间（包括停站时间），公汽换乘公汽平均耗时，地铁换乘公汽平均耗时，公汽换乘地铁平均耗时都是一个定值。公汽票价：2元。地铁票价：3元（无论地铁线路间是否换乘）。四、建模分析(1)最小转车次数模型。设n表示问题中的两0的地之间的站点数，其中矩阵B=(b(i,1))wx。表示直达0-1矩阵，即()［細MfoSi直达ttAi时，*i)=ii*(否刻>b(i>1)=设m为从站点iS曲点i的最小转车次数最小转车次数模型为:m=min{b(ljk)+b(k>l)}(1£1,kJ)o(2)最小乘车站数模型对于本模型建立只需对最小转车次数模

4、型进行简单修改即可。设n表示问题屮的两目的地之间的站点数,其屮矩阵D=(d(I,l))表示直达站数矩阵，即存ft从触1腿ft点1时，d(b为腿撤，否ftfd(i,J)=«>•设in为从站点iSflfi点i的最小转车次数最小乘车站数模型为：M=k)+d^k,(1£k■竽1,kJ)o（3）最小乘车费用模型设一趟线路公交转nil次，地铁转m2次。F为乘车费用建立模型为F=mlnfnsil4-m2},其中ml+m2=m。五、问题解决及总结（1）将问题三的各站点进行编号，并添加一些必须经过的站点。南京邮电大学仙林校区——1，仙林中心——2，新街口——3，下马坊——4，中山陵一一5,新庄广场东一一6,

5、三山街（夫子庙）一一7,湖南路一一8,玄武门9,o在以上站点经过的公交线路为：其中97路公交经过：南京邮电大学仙林校区，仙林中心。（1-2:4站）D1路公交经过：南京邮电大学仙林校区，新庄广场东。（1-6:7站）40路公交经过：新庄广场东，夫子庙。（6-7:12站）114路公交经过：新庄广场东，湖南路（6-8:3站）地铁二号经过：仙林中心，新街口，下马坊。（2-3:12站；2-4:7站）地铁一号经过：新街口，三山街，玄武门。（3-7:2站；3-9：3站）游2经过：下马坊，中山陵。（4-5:3站）（2）最小转车次数模型。将站点设为有向图中的结点.若/可以直达7,我们就设一条有向边从结点7指向

6、结点7.对于每一条有向边，指定其权为1，显然求b（1，J）就转化为有向图中结点到结点的最短路径问题。对任意给定的我们可以采用算法求最小转车次数m及乘车路线（3）最小乘车站数模型将站点设为有向图中的结点.若/可以直达y，我们就设一条有向边从结点/指向结点y.对于每一条有向边，指定其权为i到j的直达站数，显然求d(U1)就转化为有向图中结点到结点的最短路径问题。对任意给定的7,我们可以采用Dijkstra算法求最小乘车站数M及乘车路线。(4)最小乘车费用模型因为考虑到实际生活屮快节奏的生活，人家在出行时会希望更加快捷，因此我们在最小转车次数和最小乘车站数的基础上考虑最小费用问题。即在给出乘车路

7、线基础上求最少费用。(5)问题解决方案。我们用表格给出经由程序运行得到的路线。线初始站总站1换乘站•、目标站路数1165ft*.z213.**南京邮电学院站-——一"^仙林中心——新街口2147南京邮电学院站^仙林中心、马坊"中山陵3188r—南京邮电学院站一4山林中心今新街'口"三山街4194di