公交查询系统最佳路线设计
摘要
本文研究的是在三种不同情况下，确定任意两站点最优路线问题。结合生活实际，我们定义最优路线标准是换乘次数最少，所用时间最短，乘车费用最低，并将其分别位作为第一、第二、第三目标建立多目标规划模型。利用广度优先遍历原理编程得到满意的乘车路线。
针对问题一，只考虑公交的情况下，对公交路线进行抽象化处理。根据网上调查结果，确定多目标规划模型，利用matlab编程求解得到依次满足三个目标的任意两点的乘车路线。以下为6对起始站→终到站之间的部分可行路线： 起始→终到站 路线 转乘 时间/分 费用 S3359→S1828 S1557→S0481 S0971→S0485 S0008→S0073 S0148→S0485 S0087→S3676
针对问题二，将地铁站点与其周围的公汽站抽象为同一站点。同样建立以转乘次数最少的为第一目标，所用时间短和费用低分别为第二、三目标的多目标规划模型。利用matlab编程求解，得到满意的乘车路线。
针对问题三，以乘客所在站点为中心，步行时间上线为半径的区域内站点均考虑步行。将此区域内站点抽象为同一站点，建立多目标规划模型，进行编程求解，并与问题二结果进行比较。
L436（下）L167（下）S3359?????S1784?????S1828
1 2 1 1 2 1
101 130 128 83 130 125
3 3 3 2 3 3
L084（下）L080（下）S1557?????S3389?????S2361 L312(下)?????S0481L013（下）L417（下）S0971?????S2184?????S0485 L159（下）L058下）S0008?????S2683?????S0073
L024（环）L140（下）S0148?????S0345?????S3037 L104(下)?????S0485L216（下）L506S0087?????S0145????S3676
关键字 多目标规划模型 广度优先遍历 抽象化
1、 问题重述
1.1背景信息：
我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。 1.2需要解决的问题：
1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。
(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。
3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。
2、 模型假设与符号说明
2.1模型假设
假设1：相邻站点平均时间一定；
假设2：公交运行不出现交通堵塞，公交准时到达每个站点； 假设3：交通工具票价稳定，不考虑其他因素对票价的影响； 假设4：所有人的步行速度相等；
假设5：不会出现车辆拥挤或超载而使乘客误车的情况。
2.2符号说明 t t? t1 t2 相邻公汽站平均行驶时间t=3分钟 相邻地铁站平均行驶时间t??2.5分钟 公汽换乘公汽平均耗时t1?5分钟 公汽换乘地铁平均耗时t2?6分钟 地铁换乘地铁平均耗时t3?4分钟 地铁换乘公汽平均耗时t4?7分钟 t3 t4
T W y1 从始发站到终点站所用总时间 从始发站到终点站所花总费用 公汽与公汽的转乘次数 公汽转乘地铁的次数 地铁转乘地铁的次数 地铁转乘公汽的次数 从始发站到终点站总共转乘次数 从始发站到终点站乘坐公交所经过的总站点数（不考虑出发站） 从始发站到终点站乘坐地铁所经过的总站点数（不考虑出发站） 从站点p到站点q的步行时间 乘客选择步行的时间上限 y2 y3 y4 Y x x? tpq t?? 3、 问题分析
本文主要研究的交通网络中的寻优问题，要求在三种不同情况下，找出任意两站点之间最佳路线。联系生活实际，考虑公众乘坐公交的出行，确定目标函数，找出乘客满意的乘车路线。
对于问题一，在仅考虑公汽线路的情况下，根据公众乘坐公交出行的考虑因素，建立以换车次数最少为第一目标，所花时间和费用最少分别为第二、第三目标下的多目标规划模型。通过题中给出数据运用matlab编程得到任意两点之间的乘车路线，再结合目标函数对所得路线进行筛选，找出换车次数最少，所花时间和费用较小的路线作为最佳路线。
对于问题二，在同时考虑地铁和公交的情况下。根据问题一中的抽象化方法，将地铁线路 T1抽象为一条单向的公交线路，T2抽象为一条环形的公交线路；对于地铁站点，由于地铁与邻近公汽站点可换乘，我们认为地铁站点与周围的公汽站点距离较近，将其抽象化为同一站点，重新构造站点间的关系矩阵。结合问题一，建立优化模型进行编程求解。
对于问题三，将步行考虑在出行方式中。一般来说，出行者选择步行的目的是为了减少换乘次数或花费时间。当两个站点相邻近时，乘客才愿意选择步行换乘，因此我们需确定一个邻近站点的范围界限。但考虑到本文的目标之一是所用时间最短，为此将邻近站点的范围界限转化为时间界限，即所用步行时间在某一范围之内时，乘客才考虑步行。基于这种思想，再结合问题一，确定多目标优化模型进行编程求解。
4、 数据处理
4.1对站点数据处理
利用matlab编程从文本中按行读取数据，将每一行数据作为一个元胞，按行存放在元胞矩阵中，如下图1示：
元胞1元胞2元胞3元胞...L001分段计价S0619-S1914..?
4.2地铁线路的抽象处理
地铁与邻近公汽站点可换乘说明地铁站点及其周围的公汽站点距离较近，所以考虑将其抽象为新的站点，如下图2：
4.3公交乘客出行心理调查分析：
在研究乘公交出行最优算法时，首先要了解乘客出行时所要考虑的因素。通过对公交乘客的出行心理、行为的调查研究来确定模型的优化目标及约束条件是必要的。
根据网上搜索得到合肥市关于公交乘客出行需求的调查结果，如图3所示：
从图中可以看出公交乘客在出行时，考虑最多的是换乘次数，其次时间最短（在此将时间最短和路程最短统一作为时间最短来考虑）和费用最少。所以在换乘次数已经确定的情况下，选择时间较短和费用较少的路线作为最佳路线。
4.4所能接受的最长步行时间调查表：
结合实际情况，乘客对距离较近的站点会考虑步行换乘，省钱的同时也可能节省时间。当步行时间较短时，才会选择步行。以下是通过网上搜索得到的换乘时乘客所能接受的最长时间调查表，如下图4：
通过观察发现，大多数人所能接受的最长步行时间是6-10分钟。所以对于问题三，我们考虑以步行8分钟为乘客的步行时间上限。
5、 问题一的解答
5.1模型建立
根据问题一的分析，建立以换车次数最少为第一目标，所花时间和费用最少分别为第二、第三目标下的多目标规划模型。 5.1.1确立目标函数： 目标一：转乘次数最少
设从始发站到终点站总共转乘次数为Y，则转乘次数最少的目标函数：
minY
目标二：所用总时间最短
总时间包括转乘时间和经过站点所用时间，得所用时间最少的目标函数：
minT?tx?t1y1
目标三：所花费用最少
判断线路i是否为分段计价：
ui?1单一票价
wi 分段计价?在路线i(i?y1?1)（分段计价）经过站数为xi，则：
??1(0?xi?20)wi??2(21?xi?40)
??3(xi?40)得出所花费用最少的目标函数：
minW??ui
i?1y1?15.1.2确定约束条件