南京市公交转车优化问题

理学院专业实践报告

题 目： 南京市公交转车优化问题

专 业 信息与计算科学 学 生 姓 名 班 级 学 号 指 导 教 师

实 习 单 位 理学院

日 期 2014年2月28日

一、 问题描述

问题3 在转车次数最小的情况下，设计南京市地铁转乘的算法。南京市任意两个公交站点的最小转车次数的最大值是多少？即最多只要转乘几次公交，即可从南京市的任一站点乘到其它任一站点。解决此问题时，假设相邻公汽站平均行驶时间(包括停站时间)，相邻地铁站平均行驶时间(包括停站时间)，公汽换乘公汽平均耗时，地铁换乘公汽平均耗时，公汽换乘地铁平均耗时都是一个定值。

对以下站点给出乘车方案： 南京邮电大学仙林校区——新街口 南京邮电大学仙林校区――中山陵 南京邮电大学仙林校区――夫子庙 南京邮电大学仙林校区——湖南路 南京邮电大学仙林校区——玄武湖公园

二、 问题分析

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

三、 问题假设

解决此问题时，假设相邻公汽站平均行驶时间(包括停站时间)，相邻地铁站平均行驶时间(包括停站时间)，公汽换乘公汽平均耗时，地铁换乘公汽平均耗时，公汽换乘地铁平均耗时都是一个定值。 公汽票价： 2元。

地铁票价：3元（无论地铁线路间是否换乘）。

四、 建模分析

（1） 最小转车次数模型。

设n表示问题中的两目的地之间的站点数,其中矩阵 B=

表示直达0-1矩阵，即

设m为从

的最小转车次数

最小转车次数模型为：

（

（2） 最小乘车站数模型

对于本模型建立只需对最小转车次数模型进行简单修改即可。 设n表示问题中的两目的地之间的站点数,其中矩阵 D=

表示直达站数矩阵，即

，

）。

设m为从

的最小转车次数

最小乘车站数模型为：

（

，

）。

（3） 最小乘车费用模型

设一趟线路公交转m1次，地铁转m2次。F为乘车费用 建立模型为F=

，其中m1+m2=m。

五、 问题解决及总结

（1）将问题三的各站点进行编号，并添加一些必须经过的站点。

南京邮电大学仙林校区——1，仙林中心——2，新街口——3，下马坊——4，中山陵——5，新庄广场东——6，三山街（夫子庙）——7，湖南路——8，玄武门——9，。

在以上站点经过的公交线路为：

其中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）最小转车次数模型。

将站点设为有向图中的结点.若i可以直达j ,我们就设一条有向边从结点i指向结点j.对于每一条有向边,指定其权为1,显然求

就转化为有向图中结点到结点的最短路径问题。对任意给定的i,j,我们可以采用Dijkstra算法求最小转车次数及乘车路线

（3）最小乘车站数模型

将站点设为有向图中的结点.若i可以直达j ,我们就设一条有向边