公交换乘方案的研究与设计

《公交换乘方案的研究与设计》由会员分享，可在线阅读，更多相关《公交换乘方案的研究与设计（41页珍藏版）》请在装配图网上搜索。

1、第一章 绪论1前言 这些年来,城市的公交系统有了很大发展，北京市的公交线路已达00条以上，使得公众的出行更加通畅、便利,但同时也面临多条线路的选择问题。针对市场需求需要研制开发一个解决公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统,其核心是线路选择的模型与算法,应该从实际情况出发考虑，满足查询者的各种不同需求。其中需要解决如下问题.1)、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法.求出以下对起始站终到站之间的最佳路线。 （1）、S339S88 （2）、S55S041 （3）、S097185(）、S000073 (）、S048S485 ()、0087S3

2、6762)、同时考虑公汽与地铁线路的算法。 3)、当所有站点之间的步行时间已知时，建立任意两站点之间线路选择问题的数学模型。该设计主要研究三种不同情况下，任意两站点之间的线路选择问题。联系实际，公众乘坐公交车主要考虑的因素包括转乘次数、行程时间、车站始发情况、车站的车次负载量及乘车费用等因素。为满足一般公众的乘车需求,主要按照公众对不同乘车信息的重视程度,确定出最佳的乘车路线。仅考虑公汽线路的情况下，首先，需要根据给出的公交线路信息数据,对每条线路进行抽象处理,将分上下行的线路、双向行驶的线路和环行线路抽象为两条。然后，主要考虑公众最关心的乘车因素，即转乘次数。在最少转乘次数的基础上考虑共众对

3、其他因素的需求，按照先后顺序考虑行程时间、车站始发情况、车站的车次负载量及乘车费用,给出供公众选用的多种参考方案。并考虑以时间为主要目标的情况下，建立最优化模型确定任意两站点行程时间最短的方案。 在同时考虑公汽与地铁算法的情况下，根据地铁与邻近站点可换乘的信息,可将每个地铁站点及其对应的所有公交站点抽象成一个点处理。对于两条地铁线路可按照与仅考虑公汽情况下相同的抽象方法处理.在此基础上按照相同的思路确定任意两站点间的最佳方案. 考虑公交及地铁站点的实际分布情况，有时会出现步行小段距离再转车的情况更能节省时间或转车次数。因此,研究此种情况下的出行方案对节省出行时间具有重要的实际意义。 1.模型假

4、设 1 假设车站不重名;2假设各路经上公交车发车频度相同； 假设相邻站点间平均行驶时间一定；4 假设不出现交通阻塞,公交运行顺畅；5 假设不出现车辆故障及道路交通事故;6 假设始发终点出入地铁需要步行4分钟;7 假设公交准点到达，不考虑红绿灯等待时间。1.3 基本参数设定相邻公汽站平均行驶时间（包括停站时间）: 3分钟相邻地铁站平均行驶时间（包括停站时间）： 2.5分钟公汽换乘公汽平均耗时： 分钟(其中步行时间2分钟）地铁换乘地铁平均耗时： 分钟（其中步行时间2分钟）地铁换乘公汽平均耗时: 7分钟(其中步行时间4分钟）公汽换乘地铁平均耗时： 6分钟（其中步行时间4分钟)公汽票价v:分为单一票价

5、与分段计价两种，标记于线路后；其中分段计价的票价为：0站：1元;140站：元;40站以上：3元地铁票价w:3元（无论地铁线路间是否换乘）注:以上参数均为简化问题而作的假设，未必与实际数据完全吻合1.4符号系统 j- 弧（， j)是否在该有向赋权图上;t ij 站点 i j 的总乘车时间; ij 第i 个站点是否为i 的始发站； P ij - 站点i j的乘车费用。第二章 公汽站点之间线路选择模型本章主要研究任意两公汽站点间线路选择的数学模型与算法。在不同需求下找出最佳路线,并给出更为人性化的站点及转乘点是否为始发站的提示.。1 数据库建立2.数据处理三种公汽线路抽象处理目前城市公汽线路主要分三

6、种：上下行线重合、环形线路和下行线与上行线经过站点不同。下面将这三种线路进行数据处理:（) 上下行线重合这种线路有两个端点站，在两个端点之间双向行车,而且两个方向上的行车路线相同,经过同样的站点序列。由于线路的方向不同,因此，下行线和上行线可以抽象成两条线路处理。（) 环形线路实际中环形路线一般是双环，但在对这两条线路进行抽象时，为保证任意两站点距离最近,把每条线路再抽象成2条（如图所示）：(3）下行线与上行线经过站点不同由于下行线与上行线经过站点不同，显然,该种线路需要抽象成两条线路处理.2.12“公汽直达数据库 ”的建立根据公众出行心理，公汽线路选择应优先考虑两站点之间是否有直达车，那么在

7、查询系统内部应设有任两站点的直达线路表，以方便查询时优先快速查询是否有直达车,若有，则直接输出所有直达车辆;若无，再搜索换乘路线。在建立直达数据库的时候，数据结构的选择非常重要,本题共有3957 个站点，若直达数据库内每个队列的每个数据都使用双精度实型储存,实际在MALB等软件内内存占用大约为2GB,这显然超越现阶段个人电脑极限，所以根据实际情况可以采用不同数据结构，本章采用MATLB内建元胞结构，当元胞内队列不存在时不占用空间,具体元胞结构设计如下:Cell1,1Cel1，2车号费用耗时L001227L07631Cell,3Cll2，1Cell，2Cell，3图1.1 元胞结构示意图上图中C

8、ell1，代表中第1行第2个元胞(即从站点S000到站点S002的直达公交线路信息),元胞中队列的每一行代表一辆直达车信息。2.2模型设计从查询系统设计角度考虑,当输入起讫点后，系统内部通过Q查询无结果时，系统内部应自动搜寻换乘次数最少的路线,若换乘次数相同时有多种转乘方案，则系统应显示所有转乘路线方案(包括转乘次数、行程总时间、途径总站点数、转乘站点及路线、是否始发、行程总费用、转承站点负载压力）以供查询者自主选择.同时，系统应向查询者推荐“时间最短”，“费用最省”,“转乘站始发站最多，“负载压力最小”的不同目标下的最佳路线.2。2。基于不同目标的有向赋权图定义引用图论相关知识,将所提供的公

9、汽网络抽象成一个有向赋权图= （， E，W) ,G中的每个顶点为每个不同的站点， 如果从G中的顶点Vi到j有直达路线，那么这两点之间就用有向边相连， 记做( ， j）E，方向i为从j指向,表示可从i直达j，相应的有一个数w(v i， j) 称为该有向边的权, 这样公汽网络就抽象为一个有向赋权图。赋权图中的权可根据不同的目标进行定义，本模型在确定不同目标时，将其分别定义为：2。2目标分析目前用户公汽换乘主要考虑如下几个需求因素: 目标一：换乘次数最少； 目标二:行程时间最短； 目标三:行程费用最少; 目标四：转乘车辆始发最多； 目标五:站点负载压力最小。2.22.1目标一:换乘次数最少基于21建

10、立的有向赋权图，引入01决策变量 j表示弧(i , j)是否在起点与终点的路上,则：若i与v j之间无直接相连的弧，但可通过中间节点转跳，表明由站点i到之间不可直达,但可通过转乘到达,则由v 到v j之间换乘次数为经过的总弧数减1，即换乘次数最小可表示为：.2.2目标二：行程总时间最短时间权值t （u)xn,，则乘车总时间为:公汽换公汽时间固定是5 分钟,则换乘时间为：行程总时间包括起始站点等待的分钟，行程总时间最短表示为：2。2。2.目标三:行程总费用最少设qu 表示ij车辆属性设su表ij所过站数，那么ij直达费用权Wp=(pu）n表示为：行程总费用最少可表示为:。22。4目标四：转乘车辆

11、始发最多为考虑所选路线中转乘站点是否为所需转乘车始发站,我们引入1变量fu表示第i个站点是否为ij发权=（fij）nn:从i个站点的路线中转乘点为所转乘车的始发点最多的路线可表示为:2。22.5目标五：站点负载压力最小首先假设终点站是奥运场馆，乘坐公车的人大多数都到达终点站,因此转车站点离始发站的站点数越少越好(人少）： 负载压力 转乘站点离始发站的站点数 - 转乘站点离终点站的站点数注:若终点站不是奥运场馆则可以通过对负载取绝对值表示离始发或终点越近转车越方便。 如图所示，站点的负载压力 =-3=，显然负载越小越好.根据式11，aj表示进入第i个站点的径数，a表示从第i个站点出站的径数矩阵,

12、以i表示第i个站点的负载压力权Wr=（i)nxl:线路负载压力最小可表示为：.3约束分析22.31换乘次数约束基于对目标一的分析,可得在有向赋权图中换乘次数表达式，以c表示所能接受的最大换乘次数,则换乘次数约束可表示为：其中,参数为人为设定值,分以下三种情况：1 当设定c = 0时,为严格约束不能换乘; 当设定 = 时，为无乘车次数约束,即可无限次换乘； 3 当设定 为不为0的常数C 时,为约束换乘次数在C 次以内的情况； 注：参数c可根据不同的计算需求进行自由选取.仅从数学模型角度考虑，为使模型更具通用性，c的选取可到.从实际角度出发，查询系统中的c 值可由查询用户自己设定，当最小换乘次数小

13、于bu时，输出无解。2.232最短路起讫点约束由于G为有向图,则其中顶点分为“起点”、“中间点、“讫点三类，对于起点只有出的边而无入的边,对于中间点既有入的也有出的边，对于讫点只有入的无出的边。对有向图而言，若求顶点se的最短路径，以表示进入第j个顶点的边,以ji表示出第j个顶点的边，则se中的三类点约束可表示为：2。2。最少换乘次数的确定在用户输入起点与终点后,系统需要立即给出至少要转乘几次才能够到达目的地，这样就需要建立以下矩阵。统计Q中各元素长度，可得任意两站点的直达线路数。由此可构造表示两两站点间直达路线数目的直达线路数矩阵=(a)x,通过矩阵运算可得到任两站点间换乘线路数矩阵，进而得

14、到任两站点间的最少换乘次数矩阵C=(c）xn，从而可得任两站间所需的最少换乘次数.1）直达线路数矩阵的建立引入直达线路数矩阵=(aij)，其矩阵元素aij表示第i个站点到第j个站点直达线路数n，其中，当=j时为无效路径,设定值为0，即：以N表示所有公汽所经过的的站点总数，则直达线路数矩阵可表示为：2）换乘线路数矩阵的建立直达矩阵A为N 阶方阵，矩阵A的次幂中元素表示任两站点间通过1次转乘的路线数，即：其中,Aij2表示第i个站点到第j个站点通过1次转乘的路线数，下面以A第1行第2个元素a22为例对A2中元素意义进行举例说明：例：假设上式中等号右边仅a 13 、a32 = 1,其余为0,说明仅第

15、个站点可直达到第3个站点,第3个站点可直达到第2个站点，那么a1 = 1,即第1 站点可通过一次换乘到达2站点，换乘点为站点3。以An表示方阵A的n次幂，Alg为站点k j 的直达路线数，则：其中，元素A为通过( ）次换乘从站点i j的线路数。如A433 = 表示从站点到站点3 有1 条两次换乘路线，其换乘站点可通过运算参数记录得到。3）最少换乘次数矩阵的建立引入矩阵B=（u)，其矩阵元素为使得Aijn0的的最小值，n1,)，即:则u -1表示从站点j必要的最少换乘次数,以矩阵C=(c）表示最少换乘次数矩阵，则：其中,元素Cij表示从站点i j必要的最少换乘次数。基于最少换乘次数矩阵C，每对起

16、始站终到站的最少换乘次数如下： 2.3模型建立 基于分析，建立多目标最短路模型0-1规划表达式如下（s为起点，e为终点）：模型说明：（1。10） 换乘次数约束, 表示转乘次数应在乘客所能接受的最多转乘次数。 (1。1) 最短路规划中的起讫点约束，其中s为起点，为终点。 xj 弧（i， j）是否在该路径上；j站点 ij的总乘车时间;fij 第个站点是否为ij的始发站; ri 站点的负载压力;pj 站点ij的乘车总费用； c人为设定参数，表示乘客可接受的最多换乘次数,详见约束分析。 模型求解该模型有种方法，基于数据库Q与Diksa算法的“邻接算法”求解和使用Lingo软件求解无转乘次数限制的方案（

17、针对不同目标分别求解)。2.4.1基于数据库Q与Dksa算法的“邻接算法求解 其求解步骤如下：在邻接算法内不考虑转乘次以上主要原因是我们实际上并不是简单计算最短路径,而是把较优方案都记录在U、U2中,这对用户多需求是吻合的，但这样对复杂度为O（2 )的算法来说还是不可行的,但我们权衡了二者的重要性决定用方案的丰富性取代计算的准确性,而且从实际出发用户也不一定非常关心转乘次数大于2次的方案.虽然在本算法内我们不考虑转乘次数大于2次的方案，但最后我们从规划角度使用lingo软件求解了全局最优值，等同于弥补了邻接算法的缺陷。在计算机空间使用方面,我们通过对一些整形数组使用16位无符号整形，定义稀疏元

18、胞数组缩小空间占用，最终求解成功。4。使用Lingo软件求解无转乘次数限制的方案邻接算法可以求出多种方案，但对于转乘次数大于2的情况无法在有限时间内求解。作为一个全面的查询系统必须非常全面,我们认为还是有一些用户会转乘多次且需要时间最短是他们的最重要目的（前提是在代价低于使用专车费用),而且从理论角度考虑仍需要找到求解转乘 次时的可行方法。在求解上述规划模型时,通过基表 建立的数量非常庞大，采用传统求解方法时不可行，但其中有大量元素可以在ng软件内通过稀疏矩阵实现，但求解时间仍然需要20分钟左右，主要为数据导入时间（1。9分钟)，只要开始迭代计算后由于目标与约束线性,Lgo只需要6秒左右即可求

19、解出全局最优解（具体程序见附录1。6）。2。4。3用户终端报表呈现系统:多目标分层序列排序 由于可行方案集U1、U2中的数据出现顺序不一定是用户所期望的,所以有必要根据不同的用户需求对其排序，本文采用多目标分层序列法对方案集排序，实质上就是按关键字顺序依次排序，即对于一个M个字段的表按照给定的N个字段排序(在数据库软件里可以通过标准SQL语句直接操作）,下面给出算法的文字描述：）按第一关键字（即一层目标)对列表排序；2)按第二关键字对列表每个第一关键字相同的组进行排序； 3)按第三关键字对列表每个第二关键字相同的组进行排序;4)按第N关键字对列表每个第N关键字相同的组进行排序。采用多目标分层序

20、列法排序，输出按照用户需求的报表样式，具体方案见下面表格。(默认排序顺序是转乘次数、总时间、总费用、始发站点数、负载，可以根据不同用户 需求而改变）方案报表说明:每行代表一种方案,表中加黑字格表示该方案该项指标全局最优;表中总时间已包括起始点等车3分钟。 上面表中已按多目标分层序列法的默认目标排序（分别是表中转乘次数、总时间、转车站点是否始发、转车站点总负载量、总费用五个字段），一般用户只需要从上到下选取即可，但如果用户希望在转站时乘坐始发车（有座位)那么可以挑选始发字段为1、2的方案,若希望转站时人较少的地方则可以考虑选则站点负载较小的方案。本模型求解的方案集使用于所有用户，具有很强的实用价

21、值。5模型的评价2.。1 邻接算法评价 1）建立在图论基础下能够求解出转乘次数不超过两次时的所有可行方案，并可根据公众的不同需求，给出最佳需要方案，从此角度考虑，模型实用性较强；2） 模型求解基于直达队列Q,采用空间换取时间思想,适合查询系统设计标准能够较强的适应工程应用；3） 在转乘次数超过两次的情况下,运用本模型求解计算过程复杂,计算量过大;故本模型存在一定的局限性。52 1规划Lng求解方案评价 1） 在不限制最小转乘数时可以求得全局最优解,这是其他所有算法无法达到的，例如在第、4、5条线路上其转车次数为3、4、3，但是耗时相对转2次的要节省许多； )在限制最小转乘数时可以求得与邻接算法

22、同样的方案，表明模型的通用性较强，但无法像邻接算法一样求解多种方案是用户所不能接受的； 3)从理论角度分析,最优化模型规划角度可解具有很强的实际意义，例如从全国范围考虑求解，那么转车3次也是可以接受的，只要耗时足够短;） 从计算时间来分析，尽管需要0分钟,但大部分时间为数据导入，只有1%的时间是真正计算耗时，如果将所需数据存放入内存不变，其求解速度将超越邻接算法；5)但Lngo不能求解出多种方案,实用性不如邻接算法。第三章 同时考虑公汽与地铁最佳线路选择模型本章为综合考虑公汽与地铁线路的情况，解决查询系统中混合最佳路径选择问题的模型与算法。1 数据库建立3。1。1数据处理公交网简化模型1）将可

23、互换站点抽象处理为一个站点题中给出了地铁换乘公汽的数据文件，由地铁与公汽互换的时间来看，可互换的两站间地理位置应非常接近且容易换乘，定义这些站点为紧邻站点，可将这些可互换的紧邻站点抽象为一个站点，使问题得到简化. 例：信息数据第一行为“D01:S0567, S02 , 005”,则可认为这四个站点实际距离非常近，为紧邻站点，所以可看做一个点处理,示意图如下:基于这种思想,根据题目中给出关于地铁换乘公交的信息数据,可以将各地铁站点及其紧邻站点在整个交通网络中抽象为一个点处理。2)两种地铁线路抽象处理基于对三种公汽线路的抽象方法，以相同的方法对两地铁线路T1、T 2进行抽象处理如下:T1：为双向线

24、路,故可以根据不同的方向将其抽象为两条单向行驶线路。T 2：为环行线路，实际中环形路线一般是对开，故该种线路可以抽象成两条线路处理。3.1。“公汽、地铁直达数据库QD”的建立将紧邻站点处理为一个新站点,则当综合考虑公汽与地铁时，建立的实质上是新站点与新站点间的直达路线集.认为在新站点所代表的站点集中的任意站点可通过步行到达，且时间忽略。则当用户输入起、讫点后，系统内部首先自动查找这两点所属的新站点，再查找新站点间可直达的线路，并给出起点及其附近站点可直达讫点及其附近站点的路线.采用与2。12相同的思路及方法,把已知公汽线路到达 都映射到 ，计算新直达数据库 ，再结合地铁的费用与地汽换乘等待时间

25、就可以把地铁线与公汽线结合。 具体元胞结构设计图如下：上图中ell1,代表直达队列表中第1行第2个元胞(即从站点0001到站点S000的直达混合线路信息)，元胞中队列的每一行代表一辆直达车信息。.2模型的设计经过数据处理后,紧邻站点被处理为一个新站点,该站点可等同看作问题一中的公汽站点,当用户输入起、讫点后，系统内部通过直达线路队列表查询无结果时，则搜寻转乘路线方案。同时,系统向查询者推荐不同目标下的最佳路线及转乘方案。采用与相同的建模思路及方法，这里在考虑地铁后仍按目标的重要程度将“换乘次数最少”、“行程时间最短”、“行程费用最少、“转乘车辆始发最多”、“站点负载压力最小分设为第一到五层目标

26、，基于对各目标的分析与建立，这里不再复述分析，仅在模型建立时给出具体表达式，这里由于对站点的定义与第二章不同,所以对时间及费用的计算与第二章有所不同。321公汽地铁混合网络图的赋权通过简化,结合图论相关知识，将第二问公汽、地铁混合网络抽象成一个有向赋权图G = (V, E,W），G中的每个顶点为每个不同的站点, 如果从G中的顶点V到Vi有直达路线,那么这两点之间就用有向边相连， 记做（i， j）E ，赋权图中的权可根据不同的目标进行定义 3。22目标分析 3.2.2。1目标一：换乘次数最少 基于对混合网络的抽象,引入决策变量ij表示弧（i，)是否在该路径上：若i与vi之间无直接相连的弧，但可通

27、过中间节点转跳，表明由站点i到j之间不可直达,但可通过转乘到达，则由vi到v之间换乘次数为经过的总弧数减1，即换乘次数最小可表示为:3.2。2目标二:行程总时间最短1）乘车时间(为各站点最快直达时间,基于Q,包括地铁在内）：2）总等待时间:设Zj=表示ij最短直达为公汽（也表示乘始发坐公汽等待3分钟)，等于2为地铁(也表示始发乘坐地铁等待分钟），总等待时间表示为：3)总步行时间：将相同车型换乘、不同车型换乘的步行时间,一同视为分钟不同车型换乘多步行的4分钟（虚线表示地铁，空心圆表示地铁站） 表示为:地铁转地铁是不同车型换乘的特例,且只可能在D1与D18转乘，出现这种情况在 基础上减少步行时间4

28、分钟(虚线表示地铁，空心圆表示地铁站）表示为:在地铁直达时，需要另外加上4分钟出站步行时间:若始发乘坐地铁转公交到达终点,需要增加步行时间2分钟:若始发乘坐公交转地铁到达终点,也需要增加步行时间分钟：总步行时间表示为：行程总时间最短表示为（总等待时间+总步行时间+乘车时间）:。2。23目标三：行程总费用最少设qij 表示 j的车辆属性设Sij表示j所过站数，那么i j直达费用权p=（pu)nxn表示为:行程总费用最少可表示为（正常票价 地铁换乘免费)： 3.2。4目标四：转乘车辆始发最多为考虑所选路线中转乘站点是否为所需转乘车始发站，我们引入01变量fij表示第i个站点是否为 的始发站,即始发

29、权W（fj）)nxn：从第i个站点到第j个站点的路线中转乘点为所转乘车的始发点最多的路线可表示为：25目标五：站点负载压力最小首先假设终点站是奥运场馆，乘坐公车的人大多数都到达终点站，因此转车站点离始发站的站点数越少越好(人少):负载压力 = 转乘站点离始发站的站点数 转乘站点离终点站的站点数注：若终点站不是奥运场馆则可以通过对负载取绝对值表示离始发或终点越近转车越方便.如图所示,站点i的负载压力 2 -,显然负载越小越好。2。3约束分析3231换乘次数约束基于对目标一的分析，可得在有向赋权图中换乘次数表达式,以 表示乘客所能接受的最大换乘次数，则换乘次数约束可表示为:其中,参数c为人为设定值

30、，分以下三种情况：1 当设定c = 0时,为严格约束不能换乘； 2当设定c = 时，为无乘车次数约束，即可无限次换乘； 当设定c 为不为0的常数C 时，为约束换乘次数在次以内的情况; 注：参数c可根据不同的计算需求进行自由选取。仅从数学模型角度考虑，为使模型更具通用性，c的选取可到。从实际出发,查询系统中的 值可由查询用户自己设定,当最小换乘次数小于 时，输出无解。3.23。2最短路起讫点约束由于G为有向图，则其中顶点分为“起点、“中间点”、“讫点”三类，对于起点只有出的边而无入的边，对于中间点既有入的也有出的边，对于讫点只有入的无出的边。对有向图而言，若求顶点se的最短路径，以u表示进入第j

31、个顶点的边，以xji表示出第j个顶点的边,则se中的三类点约束可表示为:对有向图而言，若求顶点 e 的最短路径，以j 表示进入第j 个顶点的边,以i x 表示出第j 个顶点的边，则s 中的三类点约束可表示为： (10） 3)地铁间换乘约束 站点 j k 间是否地铁换乘地铁，使用ijk 表示，那么Yijk与走的路径Yik需要满足：地铁转地铁情况只可能在12与8转乘,故换乘总次数不能够大于2： 3。 最少换乘次数的确定采用与2.2.1相同的建模思路及方法，统计 中各元素长度,可得任意两站点的直达线路数.由此可构造表示两两站点间直达路线数目的直达线路数矩阵,可确定换乘线路数矩阵：其中，元素 为通过

32、次换乘从站点 的线路数.其换乘站点可通过运算参数记录得到.进而确定最少换乘次数矩阵： 其中,矩阵 中元素 表示从站点必要的最少换乘次数。基于最少换乘次数矩阵,每对起始站终到站的最少换乘次数如下：最少换乘次数表线路编号 1 3 4 起始站 S359 157 S01 0008 S18 0087终到站 1828 S048 S0485 S0073 S048S376最少换乘1 2 1 0 。3 模型建立基于223.2分析,以 (2。4）（2）为目标,以(2）、(。1）为约束，建立多目标图论模型01规划表达式如下（ 为起点, 为终点）: 模型说明: (2.）换乘次数约束, 表示转乘次数应在乘客所能接受的最

33、多转乘次数。(。1） 最短路规划中的起讫点约束，其中为起点，为讫点.模型说明：换乘次数约束, 表示转乘次数应在乘客所能接受的最多转乘次数。 最短路规划中的起讫点约束，其中s为起点，e为终点。 xj 弧(i, j）是否在该路径上； tij 站点 ij的总乘车时间;fj- 第i个站点是否为i的始发站； 站点i的负载压力;i- 站点ij的乘车总费用； c 人为设定参数，表示乘客可接受的最多换乘次数,详见约束分析. =3表示ij最短直达为公汽（也表示乘始发坐公汽等待3分钟)，等于2为地铁（也表示始发乘坐地铁等待分钟）。 .模型求解 基于数据库Q与Dijkstra算法的“邻接算法”求解在计算初始化后具体

34、算法同模型“邻接算法”，在计算乘坐不同车型费用与换乘等待、步行时间时可以通过增加简易的判断语句实现，求解结果见表2.12。6。方法二、使用Lingo软件求解无转乘次数限制的方案（针对不同目标分别求解)上述最优化模型规模较大，但是通过模型分析章节抽象，模型所有约束与目标都已经线性化,所以采用no软件严格按照1模型求解，可求得条线路全局最优解,具体方案分别见表。1到2，其中第一字段为Lngo.求解软件环境是i10并使用了A段编程功能，能够一次求解6个模型,故调试时不能使用低版本调试。3。4。1 用户终端报表呈现系统:多目标分层序列排序 采用多目标分层序列法排序（排序方法见5。3.），输出按照用户需

35、求的报表样式,具体方案见下面表格。（默认排序顺序是转乘次数、总时间、总费用、始发站点数、负载，可以根据不同用户需求而改变）方案报表说明：每行代表一种方案,表中 加黑字格表示该方案该项指标最优； 表中总时间已包括起始点公汽、地铁等车3、分钟。 本表已按多目标分层序列法的目标排序（分别是表中转乘次数、总时间、转车站点是否始发、转车站点总负载量、总费用五个字段）,一般用户只需要从上到下选取即可,但如果用户希望在转站时乘坐始发车（有座位）那么可以挑选是否始发字段为1、2的方案，若希望转站时人较少的地方则可以考虑选择站点负载较小的方案;另外，如果线路比较长而且换乘站点负载非常大时用户可以考虑乘坐地铁线路

36、.本模型求解的方案集使用于所有用户,具有很强的实用价值.3模型的应用本文模型在数据库查询系统中的实际评价与应用 基于模型建立的思想，可将模型直接应用在查询系统的建立中，具体应用如下: 直达快表Q建立的实际应用:在实际应用中块表应用的主要目的为缩减系统搜寻样本空间,以减少搜寻时间及系统搜寻负担.具体搜寻方案为：将模型求解出的直达队列表储存在查询系统的第一层数据库中。查询时，乘客输入起讫点后，系统首先在直达列表中搜寻,若有结果，则优先输出直达路线以及相关信息；若无，则系统自动将数据导入下一层进行处理.邻接算法建立的实际应用：当第一层搜寻无结果时系统自动将数据转入本层邻接算法模型中.本层在处理时将数

37、据带入本模型，确定出任意两站点之间的最少转乘次数，同时记录对应的多条转乘方案,当转乘次数小于等于2时,数据在本层进一步处理。即将得到的不同方案导入分层序列排序模型中,针对不同需求对各方案进行优劣排序,最终将最优方案输出到用户终端。但当转乘次数大于时，由于算法时间限制，为提高查询效率,系统自动将数据导入下一层数据库进行处. 01规划模型建立的实际应用:当转乘次数大于2次时,数据进入本层处理.首先，系统将提示用户输入可接受的最大转乘次数,系统将其值带入本模型中的参数中，利用本模型规划求解出在该转乘次数约束下的最佳路线；若在该约束下无可行解，则系统提示无公交可乘，必须步行适当距离才可能乘坐到车。第四

38、章 已知站点间步行时间的线路选择模型本章主要讨论假设在知道所有站点之间的步行时间的基础上,建立任意两站点之间线路选择问题的数学模型，及其算法实现. 前两章为不考虑站点间步行时间问题，事实上在实际中会出现这样一种情况：人们步行一小段距离再转车，选择这种方式通常可以减少出行总时间.因此,研究此种情况下的出行方案对节省出行时间具有重要的实际意义。根据前面的分析公众出行时除了出行时间最短外，需要考虑的因素仍然包括转乘次数尽量少,行程费用最少，转乘点始发站最多,站点负载压力最小行.在只靠虑同一站点转乘时，针对公交和地铁网络节点图，可以建立最短路规划模型。假设在只考虑步行的情况下，同样，根据任意两点间的步

39、行时间可以个建立关于两点之间步行时间最短的最短路规划模型.根据上面的情况,对于同一有向赋权图，当对于任意两个点之间对应两个时间权值时，因此,对于步行和乘车的情况，我们建立最短的换乘模型。模型设计基于前两章问题的分析,本模型主要以出行总时间最省为主要目标，同时考虑转乘次数尽量少，行程费用最少，转乘点始发站最多,站点负载压力最小行。根据目标从前到后,的重要程度，根据分层序列法，建立最短路问题的01整数规划模型。建立本模型首先要创建邻接点矩阵 ，需要考虑的两个赋权值为乘车时间和步行时间,即赋权图中任意两点之间的权值有两个,即乘车时间 和步行时间 ，且都为已知量.令乘车时间对应的决策变量为 （1变量)

40、，步行时间对应的决策变量为 （0-变量）。 4.1。1目标分析 41。1。1目标一：行程总时间最短 公众出行是否会选择第 到第 个节点之间的路，有决策变量和共同决定.根据6.2。2分析,可以得出其出行总时间最少的目标函数为: (.)411。2目标二：行程总费用最少 当满足前面所有目标后，再求解所有可行方案中费用最小的路线，在这本层目标分析时，将图中的权值赋为途中所需的费用。基于模型6.2中关于任两站点费用的计算方法，这里可直接得到任一弧的所代表的行程的费用，所以总费用的计算为在将弧的权值赋为费用后,线路上代表该线路的各弧长之和。以 表示站点 到 的行程费用，则行程总费用最小可表示为： (3。)

41、41.3目标三:转乘点始发站最多 当满足第一层目标后，再考虑所选路线中转乘站点是否为所需转乘车始发站,引入0-1变量 表示第 个站点是否为 的始发站，即: 则从第 到 个站点的路线中转乘点为所转乘车的始发点最多的路线可表示为:（33） 4。1.。4目标四：站点负载压力最小 在满足以上三目标的前提下,从更为人性化的角度及城市交通规划角度考虑，应使乘客尽量到负载压力小的站点转乘。在本层目标分析时，将图中的权值赋为各弧起点处的站点负载压力。基于模型中关于任一站点负载压力的定义及计算方法，这里可得到任一弧起点处负载压力，以 表示起点处负载压力,则线路负载压力最小可表示为： (3。4） 12 约束分析

42、4。21最短路约束 由于行走路线中任意两点间只会选择一种出行方式，故:同时，决策变变量还要满足最短路问题中的主要限制条件，如下所示：。122换乘次数约束 公众在考虑出行时间尽量短的同时,也会考虑到换乘次数给出行带来的不便.表示乘客所能接受的最大换乘次数,根据乘车次数确定换乘次数约束可表示为:4.1。2.3地铁间换乘约束站点i j k 间是否地铁换乘地铁，使用ijk Y 表示,那么ij 与走的路径ij 需要满足：地铁转地铁情况只可能在1与D18转乘，故换乘总次数不能够大于2： 42模型建立根据问题分析中的目标分析和主要约束分析可建立多目标最短路模型，01规划表达式（为起点，j为终点）： 符号说明

43、: xi 弧（i, j)是否在该路径上； ti 站点 ij的总乘车时间；fij 第个站点是否为j的始发站; ri- 站点i的负载压力；j站点ij的乘车总费用； c人为设定参数,表示乘客可接受的最多换乘次数，详见约束分析.等于3表示ij最短直达为公汽(也表示乘始发坐公汽等待3分钟)，等于2为地铁（也表示始发乘坐地铁等待2分钟)。3模型求解 在公交和地铁交通网络系统对应的最短路权值确定的情况下，本模型线性可以考虑运用软件编程求解，针对不同目标分别求解可能比较容易.另外,针对本模型我们给出一种近似求解的算法。在所有站点之间的步行时间确定的情况下，公众出行时可以考虑步行小段距离再换乘车次比较符合实际。

44、基于这种思想，可以考虑将位置比较接近的站点抽象为一个点.根据人的心理分析，一般人对步行时间有一个心理承受值，令该值为，此时可以根据问题二站点的抽象方法,将这种点抽象为一个点处理。为方便描述，将公交和地铁整个系统描述为公交，算法思想如下：第五章北京地铁换乘方案研究与设计1号线（一线)北京地铁1号线北京地铁1号线，又称一线,全长30。44千米。 设53站、52站、苹果园站、古城站、八角游乐园站、八宝山站、玉泉路站、五棵松站、万寿路站、公主坟站、军事博物馆站、木樨地站、南礼士路站、复兴门站【换乘2号线】、西单站、天安门西站、天安门东站、王府井站、东单站【换乘5号线】、建国门站【换乘号线】、永安里站、

45、国贸站【换乘10号线】、大望路站、四惠站【换乘八通线】、四惠东站【换乘八通线】共5座车站。(52、 53#站不运营，供战备用。52站位于福寿岭北京地铁技术学校内，5站位于黑石头(高井）的北京军区院内）.地铁号线及八通线标志颜色为红色.2号线(环线）北京地铁号线，又称环线，全长3。千米。地铁2号线的标志颜色为蓝色。2号线设西直门站【换乘13号线】、车公庄站、阜成门站、复兴门站【换乘1号线】、长椿街站、宣武门站、和平门站、前门站、崇文门站【换乘号线】、北京站、建国门站【换乘1号线】、朝阳门站、东四十条站、东直门站【换乘13号线】、雍和宫站【换乘号线】、安定门站、鼓楼大街站、积水潭站共18座车站.1

46、号线北京城铁13号线，全长0.千米，设西直门站【换乘2号线】、大钟寺站、知春路站【换乘0号线】、五道口站、上地站、西二旗站、龙泽站、回龙观站、霍营站、立水桥站【换乘5号线】、北苑站、望京西站、芍药居站）、光熙门站、柳芳站、东直门站【换乘号线】共1座车站。全线除西二旗到龙泽、柳芳到东直门部分区间（约3千米）为地下段外,均为地面或高架铁路。3号线的标志颜色是橙黄色。八通线北京城铁八通线是北京地铁1号线的东段延长线，全长1。964千米，设四惠站【换乘1号线】、四惠东站【换乘1号线】、高碑店站、传媒大学站、双桥站、管庄站、八里桥站、通州北苑站、果园站、九棵树站、梨园站、临河里站、土桥站共13座车站。全

47、线均为地面或高架线路.八通线及地铁1号线标志颜色为红色.4号线（建设中）地铁号线线路全长21公里，共设有24座车站，正线全部为地下线,预计于209年9月建成通车.地铁4号线南起南四环路北侧马家楼,向北沿马家堡西路、菜市口大街、宣武门外大街、宣武门内大街、西四南大街、西四北大街、新街口南大街至新街口,由新街口向西，沿西直门内大街、西直门外大街至首都体育馆后转向北，然后沿中关村大街至清华西门,之后再次折向西，经圆明园、颐和园，终点至龙背村。5号线北京地铁5号线雍和宫车站地铁5号线自北向南依次设有:天通苑北站、天通苑站、天通苑南站、立水桥站【换乘1号线】、立水桥南站、北苑路北站、大屯路东站、惠新西街

48、北口站、惠新西街南口站【换乘0号线】、和平西桥站、和平里北街站、雍和宫站【换乘2号线】、北新桥站、张自忠路站、东四站、灯市口站、东单站【换乘1号线】、崇文门站【换乘2号线】、磁器口站、天坛东门站、蒲黄榆站、刘家窑站、宋家庄站。在太平庄设车一座车辆段,在宋家庄设一座停车场。5号线的代表颜色为紫色。在规划中，地铁5号线将向南延长:沿宋庄路穿南四环,经大兴庑殿村、旧宫镇、通州区马驹桥镇、最后穿六环抵达亦庄开发区的影视城主题公园。10号线巴沟站、苏州街站、海淀黄庄站【4号线，09年】、知春里站【换乘3号线】、知春路站、西土城站、牡丹园站、建德门站、北土城站【换乘8号线，即奥运支线】、安贞门站、惠新西街

49、南口站【换乘号线】、芍药居站【换乘13号线】、太阳宫站、三元桥站【换乘L1线,即机场线】、亮马桥站、农业展览馆站、团结湖站、呼家楼站、金台夕照站、国贸站【换乘1号线】、双井站、劲松站共22座车站。二期宋家庄站可与5号线换乘,火器营站和宋家庄站可与规划地铁11号线换乘.0号线的代表颜色为紫色.8号线（奥运支线)从南向北分别为北土城站【换乘10号线】、奥体中心站、奥林匹克公园站和森林公园南门站。8号线规划向南经中轴路绕行故宫东侧至永定门.8号线的代表颜色为绿色.010年12月月底,北京轨道交通将添“新丁”,拉近顺义、大兴等新城与市区之间的距离。据了解,新线与既有线路导乘通道越来越平坦，换乘时爬上爬

50、下、在室内外频繁交替的情况越来越少。 宋家庄站：亚洲最大“换乘平台”换乘时间:1至3分钟从号线列车上下来,不足10步外的站台墙壁被木板遮挡得严严实实。在工作人员的带领下，穿过一道暗门，眼前豁然开朗,向前步行不足1分钟，就可抵达亦庄线的候车站台中部。“00年12月月底开通时，这扇木墙将全部拆除，亚洲最大的地铁站将首次亮相.”亦庄线站台的设置类似13号线西直门站,中间站台两侧均可搭乘去往亦庄方向的列车。如果从亦庄进城，则从两侧站台下车后，爬级台阶抵达站厅层再进入号线站台层。整个过程都有扶梯搭乘，耗时约3分钟. 工作人员介绍,地铁亦庄线沿途已有不少成熟社区,以旧宫站为例，现有常住人口7.2万人,流动

51、人口万余人，相当于5号线北部的天通苑站周边客流总量。这些居民今后如果选择轨道交通,将搭乘亦庄线到宋家庄站，进行换乘后进入城中心。“届时,现在5号线站厅层中部的导流栏杆将全部拆除，2万余平方米的站厅、站台层全部打通，为大客流提供足够的流动空间.望京西站:换乘天桥伸入地下 换乘时间：5至1分钟 1号线望京西站矗立在京承高速路中间，通过一座天桥与高速路东侧的公交车站相连.如今,站在天桥上可以看到,十余米外另一座平行的新天桥已初具规模，桥体横穿高速路后，向北拐了个弯，蜿蜒至地下。15号线首开段开通后，乘客就将沿着这座新空中走廊实现双向换乘。如今走廊中间已安装好了半人高的防护栏,避免客流交叉发生危险。

52、从换乘通道穿出,正好位于5号线望京西站中部。整个“空中”换乘过程类似于1号线在东单站换乘号线,大约需要5至10分钟，途经百余级台阶,全程都已安装扶梯，但尚未安装自动步行道。虽然只是隔路相望，15号线望京西站站台还有不少细节改变.比如原本悬挂在站台天花板上的电视屏镶嵌进了屏蔽门上方，乘客抬眼就可以看到，不用像以往一样扭头。站台内还出现了类似号线的招援按钮。 新宫站：出城换乘只需15步 换乘时间：30秒大兴线开通后将与号线贯通运营,乘客只有在出城搭乘了小交路区间车时，才需要换乘.届时，4号线目前的南端末站公益西桥站，从起始站变为中途站,而在大兴线的首站新宫站设立折返线.如果搭乘区间车抵达新宫站后，

53、从3号站台下车，向前步行约15步就可抵达1号站台继续候车.“两侧屏蔽门上都有提示,号站台上写着终点站,1号站台上写着开往天宫院方向。”工作人员介绍，今后还将通过广播的方式引导乘客换乘。第六章 总结论公交换乘系统是城市公交系统的一个重要组成部分,建立高质量的公交换乘系统是提高城市的交通效率,减少出行时空消耗,确定公共交通主导地位的有效途径，它的研究越来越受到国内外专家的重视,本论文在分析了公交换乘系统国内外研究先装个的基础上，对公交换乘系统进行研究设计，设计了公汽站点之间线路选择模型、同时考虑公汽与地铁最佳线路选择模型和已知站点间步行时间的线路选择模型。该三个模型从实际情况出发，通过计算求解,可

54、以得出各种情况下的用户需要的最优公交换乘选择。但是该设计还存在一些不足，今后的研究可以从以下四个方面进行改进。 、考虑通过站点周围建筑物进行查询 查询用户一般为对城市道路交通情况不熟悉的外地乘客,所以在查询时可能并不知道具体的站台名称，而只知道站台所在的大概位置，如对于观看奥运会比赛的用户可能仅知道奥运场馆的名称而非其邻近站点的名称，因而在抽象公交网络时要考虑站台周围的建筑、大的单位及景点。根据实际情况可以把这些相关因素与其周围最近的站台名联系在一起,从而抽象成一个节点。如可以以站台为圆点，可以接受的步行距离为半径所画的圆形区,抽象为一个站点进行记录，用户在查询时可仅输入所要到达的地点标志,系

55、统会自动提示最近站点及最佳乘车方案。 、考虑提示观光路线 对于许多乘客而言,更希望乘车路线沿途可观赏到北京的特色景观及建筑,所以从宣扬首都文化角度考虑，应在系统内部将沿途有特色景观（如奥运场馆、名胜古迹等）的路径段进行特别标注或分区存放数据,在用户查询时，系统应在给出常规最佳路线的同时，提示一条观光路线供乘客自由选择. 、考虑步行对公众感受的影响程度由于题中未给出步行时间及乘车时间对公众感受的影响程度，所以本模型在建立时采取保守做法，即认为其影响程度相等。事实上存在这样一种情况，即乘客宁愿多坐0分钟的车，也不愿走3分钟的路,这样在计算总时间时应将走路时间设的系数设置的更大才更符合乘客出行心理.

56、 4、考虑乘客特殊乘车嗜好当同时考虑公汽及地铁时,本模型并为考虑公众出行的特殊嗜好,比如有的乘客不喜欢坐地铁或公汽.则查询系统内部应分三区,分别存放仅公汽、仅地铁、两者混合三区，用户查询时可根据系统提示自主进行选择。参考文献1 谢金星，薛毅优化建模与LINDO/INGO软件北京：清华大学出版社,2005年月2 Dune Hansemn, Bruc Littlfied。朱仁峰译.atlM.北京:清华大学出版社，2006，5 王莉,李文权.公共交通系统最佳路径算法.东南大学学报，0，4（2):262674 徐多勇，李志蜀,梅林.基于SM短信息的公交查询系统的最优化转乘方案研究与设计 J.计算机应用， 007，2（)文中如有不足，请您见谅！41 / 41