页脚. 最优公交线路选择模型
摘 要
本文讨论了公众出行时多条线路选择的问题，给出了在已知公交系统中任意两公交站点之间线路选择的模型和算法，使得出行时的时间、费用和换乘次数都尽量的少。
在问题1中，我们仅考虑公汽线路，将520条公汽线路信息读入到两个矩阵当中，利用矩阵表示站点间的直达经过站数和线路，用matlab编程求解分别得到换乘1次和换乘2次时6对起始站→终到站之间的最佳路线。仅在此给出S3359→S1828的最佳路线，其余结果见正文。
表1：换乘1次时S3359→S1828的最优线路方案
起点站 终点站 线路1 中转站 线路2 时间（分） 费用（元）
S3359 S1828 L436(下) S1784 L167(下) 101 3
表2：换乘2次时S3359→S1828的最优线路方案
起点站 终点站 线路1 中转站1 线路2 中转站2 线路3 时间 费用
S3359 S1828 L015(下) S2903 L027(环) S1784 L167(下) 73 3
问题2要求同时考虑公汽与地铁线路，我们首先将增加的地铁线路信息添加到问题1建立的两个矩阵中，利用与问题1相似的编程思路，求解得到换乘1次和换乘2次时6对起始站→终到站之间的最佳路线。S3359→S1828的最佳路线与问题1的相同，其余结果见正文
问题3要求同时考虑公汽、地铁和步行，我们建立了全局替换模型和局部替换模型。
最后我们对模型进行了推广，给出了线路“满载度”的定义，在考虑“满载度”之后，建立了新的模型。
关键词： 多目标规划 最少时间 相关矩阵 满载度
页脚. 一、问题提出
我国人民翘首企盼的第29届奥运会明年8月将在举行，届时有大量观众到现场观看奥运比赛，其部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：
1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。
(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485
(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676
2、同时考虑公汽与地铁线路，解决以上问题。
3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。
【附录1】基本参数设定
相邻公汽站平均行驶时间(包括停站时间)： 3分钟
相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟
公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)
地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)
地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)
公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)
公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元
地铁票价：3元（无论地铁线路间是否换乘）
注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。
【附录2】公交线路及相关信息 （见数据文件B2007data.rar）
页脚. 二、问题假设
1．假设题目给定的公交线路均合理有效；
2．假设题目中所给的基本参数合理有效，不会对最终结果的准确性造成影响；
3．假设不存在因公汽或地铁满载，使公交到站后，等车的乘客无法上车的情况；
4．假设公交行驶过程中不受地形、天气、路况和上车人数的影响，相邻公交站的平均行驶时间（包括停站时间）固定不变；
5．假设乘客选择乘车路线时仅考虑三个因素：时间、费用和换乘次数；
6．假设每个乘客从出发地到达目的地最多乘坐3辆公交车（在能够到达的情况下）；
7．假设环行的公汽没有始发站和终点站，在客观情况允许的情况下，会绕着环行线路一直开下去，即乘客上车后无需下车再乘，就可以从环行线路的一站到达环行线路其他任意站；
8．假设地铁直接换乘地铁时只需购买一次地铁票，花费3元，当地铁换乘公汽后再换乘地铁时需要购买两次地铁票，花费6元。
三、符号约定
ija：仅考虑公汽线路时，从公汽站i到公汽站j（ij）直达（只乘坐一辆公交就可到达）行驶所经过最少的路段（相邻两公交站的路程称为一个路段）数目，当不能直达或i=j时，ija=0；
ijb：仅考虑公汽线路时，从公汽站i到公汽站j直达行驶所经过最少的路段数目的公汽线路，当不能直达或i=j时，ijb=0；
A ：公交站点相关矩阵，其中存放元素ija；
B ：直达公交线路矩阵，是矩阵A的对应矩阵，其中存放元素ijb；
n ：从起点到终点所利用的公交线路总数；
s ：换乘的次数，s=n-1；
km：乘客第k次乘坐公交时所乘坐的站数（由假设6知k可取1，2，3）；
kP：乘客第k次乘坐公交时所需要的费用（由假设6知k可取1，2，3）；
ijT：从起点i到终点j的所需要的时间；
ijP：从起点i到终点j的所需要的费用；
t汽：相邻公汽站平均行驶时间（包括停站时间）；
页脚. t铁：相邻地铁站平均行驶时间（包括停站时间）；
t汽汽：公汽换乘公汽平均耗时；
t铁铁：地铁换乘地铁平均耗时；
t铁汽：地铁换乘公汽平均耗时；
t汽铁：公汽换乘地铁平均耗时；
t汽铁汽：同一地铁站对应的两公汽之间通过地铁站换乘的平均耗时。
四、问题分析
奥运会明年8月将在举行，届时有大量观众到现场观看奥运比赛，其部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。怎样才能在众多的公交线路中找出既省时又省钱的公交线路，是人们所关心的问题。此文即要求给出线路选择的模型与算法，从实际情况出发考虑，满足乘客的各种不同需求。
4.1 问题1的分析（仅考虑公汽线路）
某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。问题1要求在仅考虑公汽线路的情况下，给出任意两公汽站点之间线路选择的一般数学模型与算法。在文本文档公汽线路信息中一共给出了520条公汽线路，3957个公汽站点。乘客选择乘车路线时主要考虑三个方面的因素：时间、费用和换乘次数。三者之间是既有联系又有区别的，一般情况下，换乘次数比较少时所用的时间也比较少，同时花费的费用也比较少；换乘次数比较多时所用的时间也比较多，同时花费的费用也比较多。但也不排除换乘次数多时花费的时间反而比较少的情况。考虑到人们的心理因素，人们对换乘次数有一个最大的承受上限，不能无限制的换乘下去，所以我们限定最大换乘次数为2，即最多利用3条公交线路从起点站到达终点站。即使换乘次数大于2时存在需要时间和费用更少的路线我们也不再考虑（其实我们有理由相信这种事件的概率是非常小的，甚至是不存在的）。所以我们先建立模型，搜索出换乘次数小于或等于2的所有的可行线路，再分别计算出这些线路学要的时间和费用，根据乘客不同的需求，即不同的目标函数，选择最优解。
从起点i到终点j的所需要的总时间ijT由两部分构成：一是公交的行驶时间；二是乘客换乘时的耗时，包括换乘时的步行时间和等待时间。公交的行驶时间等于相邻站点间的平均行驶时间乘以公交行驶的站数，即ktm汽，多次换乘时 只
页脚. 要将每次乘坐的行驶时间求和即可，即1nkktm汽。乘客换乘时的耗时等于换乘次数乘以每次换乘所需的时间，即st汽汽。所以总的耗时ijT可以用下面的表达式来表示：
1nijkkTmtst汽汽汽
乘客从起点i到终点j的所需要的总费用ijP为乘坐每一辆公交所需费用的加和。乘坐公汽时的收费分为两种情况：一种是单一票价的，无论乘坐多少站均收费1元；另一种是分段计价，分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元。将收费方式用数学表达式表示可写成以下的形式：
120kkkPmk乘客第次乘坐的公汽为单一票价时乘客第次乘坐的公汽为分段计价时
其中：20km表示对20km上取整，即取不小于20km的最小整数。乘客从起点i到终点j的所需要的总费用ijP为乘坐每一辆公交所需费用的加和，即：
nk=1ijkPP
4.2 问题2的分析（同时考虑公汽与地铁线路）
问题2在问题1的基础上增加了地铁线路，乘车时间和乘车费用的表达式都将改变。在从起点i到终点j的所需要的总时间ijT由三部分构成：一是公交的行驶时间；二是乘客换乘时的耗时，包括换乘时的步行时间和等待时间；三是当起始站和终点站乘车为地铁时需要先由公汽站进地铁站或从地铁站走到公汽站点的步行时间，这个步行时间我们定义为修正时间，而在中途遇到进地铁的情况则没有修正时间，因为步行时间已经包含在换乘时间。公交的行驶时间等于相邻站点间的平均行驶时间乘以公交行驶的站数，但公交此时分为公汽和地铁，而且两者相邻站点间的平均行驶时间不同：为t汽和t铁。每一次乘坐公交的行驶时间可表示为以下形式：
kkkmtkTmtk汽铁行乘客第次乘坐的公交为公汽时乘客第次乘坐的公交为地铁时
换乘也存在5种情况，5种换乘的时间分别为：t汽汽、t铁铁、t铁汽、t汽铁和t汽铁汽。每一次的换乘时间表示如下：