1. 问题的重述
城市公共交通运输以其覆盖面广、经济快捷的特点,目前仍然是绝大多数出行者的首选方式,也是各地城市政府大力发展的一种交通方式.
第29届奥运会明年8月将在北京举行,作为城市枢纽的公共交通承担着非常重的运输任务.近年来,北京市的公交系统有很大的发展,公交线路的条数和公交车数量在迅速增多,有时出行往往还需要换乘多辆公交车才能到达目的地.如何在短时间、换乘次数最少、成本最低的情况到达目的地,是人们所关注的问题.因此,我们通过建立线路选择的模型与算法,设计一套自主查询计算机系统,查询到出行时所需的最佳公交路线及换乘方法,给人们出行节约更多的时间和金钱.
设计这样一个系统,应该从实际情况出发考虑,满足查询者的各种不同需求.下面需要解决如下问题：
1、仅考虑公汽线路,建立任意两公汽站点之间线路选择问题的数学模型与算法.并求出以下6对起始站→终到站之间的最佳路线.
(1)S3359→S1828 (2)S1557→S0481 (3)S0971→S0485
(4)S0008→S0073 (5)S0148→S0485 (6)S0087→S3676
2、同时考虑公汽与地铁线路,解决1中问题.
3、如果所有站点间的步行时间已知,建立任意两站点间路线选择问题的数学模型.
2.模型的假设
(1)假设转车次数最多不超过两次.
(2)假设公交车都按时发车、按时到达,乘客无需花费多余的时间等车.忽略初始等车的时间,即初始站乘客到站便能上车出发；
(3)假设交通顺畅,行车过程中不考虑车辆出现意外,即排除车坏了,发生交通事故等意外状况,公车不会因为堵车或天气状况等因素延长行驶时间.
(4)假设乘客不会因天气状况 (如下雨)而对换乘车次的抉择产生影响,途中步行时间不变,红绿灯不影响行车时间.
(5)假设不考虑收费特殊情况,例如婴儿,老人,军人等不收费情况.
(6)假设车始终匀速行驶,并且同种类站点之间行车距离相等,都设为单位1,与实际距离无关.
(7)假设整个公交网络是一个连通图,任意两个站点都有路可达,环线可以以任意站作为起点站和终点站,并且是双向的.
(8)假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘,且无需支付地铁费.
3.符号说明
表示公汽线路
表示公汽线路 上的第 个站点
表示由起始站点到终止站点的距离
表示由起始站点到终止站点的时间
表示由起始站点到终止站点的费用
表示经过站点 的所有公汽线路的集合
表示地铁T1上的站点
表示地铁T2上的站点
表示 的距离
表示 的距离
表示 的时间
表示 的时间
4.问题分析
这是一个比较复杂的多目标优化问题,不同的查询者最优路线的标准是不一样的,而且多数情况下会综合考虑换车次数,行车费用与行车时间问题,查询系统应该给出多种方案供查询者选择.
但乘客出行选择公交路线时,首先考虑的是转车次数,其次才是路径的长度,因为换乘途中需花费步行时间,等车时间等等.人们通常宁愿多乘坐几站也不愿换车,对于大多数选择公交车出行的人们来说,尽量少的转车次数才应当是被首先考虑的,其次才是时间和费用.本文也是基于乘客的这种想法,在寻求最小换乘次数的基础上考虑时间和费用的最优配置.
在附件给出的数据中光公交线就有520条,公交站点更是多达3957个,如此大的数据量如果用手动的方法根本是没法完成的.解决问题的根本是要有一个好的算法,借助计算机求解来实现乘车路线的优化.本题以分别最小换乘次数、最少行路时间、最少费用为目标进行求解.
根据以上分析我们可建立多目标规划模型 ：
目标一：乘客要求换乘次数最少的路径
目标二：要求所提供的路线为时间最短的路径
目标三：车费最低的路径
由于转车途中存在各种不确定因素,乘客往往会选择尽量少的转车路线以避免各种不必要的麻烦,因此我们假定换乘车次数不超过两次.
下面对题中三个问题进行具体分析：
4.1问题一的分析
该问题要求在仅考虑公汽线路的前提下,根据查询者的不同需求目标建立任意两公汽站点之间线路的选择模型以及算法.对公交乘客出行心理进行分析,可知,乘客的需求因素主要有三类：换乘次数、出行耗时、出行费用.利用公交信息帮助公交出行者选择出行线路.
已知相邻公汽站平均行驶时间(包括停站时间)：3分钟;公汽换乘公汽平均
耗时：5分钟(其中步行时间2分钟).
公汽票价：分为单一票价与分段计价两种,标记于线路后;其中分段估计票
价为：0～20站：1元;21～40站：2元;40站以上：3元.
综合对题目的分析,我们优先考虑换乘车次数尽量少,然后再考虑花费时间相对短、花费金钱相对少,建立多目标规划模型,分三种情况分别进行讨论：直达,换乘一次,换乘二次.最后对得出的所有结果再进行筛选.
4.2问题二的分析
问题二要求同时考虑公汽与地铁线路,设计任意两公汽站点之间线路选择问题的数学模型与算法.
已知相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟;
地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟);
地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟);
公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟);
地铁票价：3元(无论地铁线路间是否换乘);其它的公汽时间信息与问题一相同.
我们考虑了总时间和总费用两个函数,讨论方法与一题类似,只是加入了地铁,分为乘坐地铁和完全不坐地铁两种.由于假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费,那么不妨把同一地铁站所对应的几个公汽站合并成一个站. 把地铁换乘纳入最优线路的选择中,对问题二的求解并不需要重新建立模型求解,只需在问题一的求解出的几条最优线路中考虑,对模型进行适当的修改即可
4.3问题三的分析
问题三在问题二的基础上又增加了步行这种情况,已知所有站点间的步行时间,其余信息与问题二相同,题目要求建立任意两站点间路线选择问题的数学模型.
在适当站点步行,可以节省交通费用而且不会消耗过多时间,比如某些乘客在一段分段计价线路上欲乘坐21或41个站点,则可以选择在第20站或第40站下车,步行一站即到达目的地,这样做可以节省1元.当十分钟以内可到达目的地时或者两个站点间的步行时间小于起始站时的换乘时间,可以选择步行.同时也给出乘车方案,人们可根据自己的需求进行选择.
5.模型的建立与求解
算法思路：由于人们的对换乘车次数尽量少的偏好程度总是大于对花费时间和金钱相对少的偏好程度，我们将优先考虑换乘车次数尽量少，然后再考虑花费时间相对短、花费金钱相对少，对得出的所有结果中进行筛选。换乘次数的大概思路及步骤如下：
5.1问题一：
只考虑任意两公汽站点之间线路的选择问题，分为公汽直达和公汽换乘两个问题建立模型。
1.1公汽直达：
(1)若起始站 和终止站 之间有直达车即两站点同时在 这条路线上，且上行与下行路线相同。根据假设由于各站间距离是定值，可以用起始站和终止站之间的站点数表示它们之间的距离，时间及费用。
距离： ，
时间： ，
单一票价时的费用为：
分段票价费用为：
(2)若起始站 和终止站 之间有直达车即两站点同时在 这条路线上，但是上行与下行路线不同，此时我们只能考虑将上行和下行看成不同的两条路线，且仅当行车方向是由起始站开往终止站时才可建立如下模型：
距离： ，
时间： ，
单一票价时的费用为：
分段票价费用为：
反之不能按以上思想考虑，应依具体情况进行分析。
(3)若 是环路，该路线上的两站点（ 和 ）需满足如下关系：
距离：
时间： ，
单一票价时的费用为：
分段票价费用为：
1.2公汽换乘:
同上种情况，最短的路线也就是途经站点最少相应的换乘次数也就最少（本文仅考虑3次以内的换乘），假设从起始站 到终止站 需换乘1次车，这里假设 是经过站点 的所有路线的集合， 是经过站点 的所有有路线的集合，并运用动态规划基本思想和方法找到可以乘换车的所有站点集合 ， 是换乘的站点，则 ，于是
，
，
即为所求。同理换乘两次时，按上述的方法找到所能换乘的站点，然后求出最优解。
问题一的求解结果如下：
基于以上考虑,我们对每道小题都给出了多种乘车路线,以供乘客根据自己的需要进行选择.
评论