公交线路模型

1、承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名

2、）：参赛队员（打印并签名）：1.指导教师或指导教师组负责人（打印并签名）：数模指导组日期：2011 年8月26日编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：公交查询系统的研究与设计摘要本文旨在设计一个解决公交线路选择问题的自主查询计算机系统。问题一，鉴于实际生活中公交路线复杂多样，我们将不同公交线路抽象化。把公汽 换乘和直达综合考虑，模型比较复杂，所以我们首先建立公汽直达数据库Q，用户查询 时，系统首先查询Q，得到所有直达车方案。在需要转乘时，针对不同用户需求，分别 以转乘次数最少、总耗时最

3、短、总费用最少为目标，量化不同目标为有向赋权图的不同 权矩阵，始、终点连通为约束建立0-1整数线性规划模型来设计最佳路线。为了能提供多种公交线路备选方案，我们首先使用基于Dijkstra的邻接算法求解， 得到不同目标下的多种优化方案；对于邻接算法不易求解的多次转乘最优方案，我们采 用Lingo软件直接求得全局最优解。综合方案集（见5.1.6模型表1.1-1.6），其中6条 线路时间最短目标分别为67、102、106、62、105、49（分钟）。问题二，同时考虑公汽和地铁系统，首先把各地铁站点和周围邻近的公汽站点集抽 象为同一新站点，同时将两条地铁线路抽象化，计算公汽地铁直达数据库:】二，再结合

4、 地铁的费用与地汽换乘等待时间把地铁线与公汽线结合，建立多目标0-1整数线性规划 模型（见5.2.7模型）；对于转乘次数以2次为分界分别使用邻接算法和Lingo软件求解得 出6条线路的全局最优解。综合方案集（见5.2.9模型表2.1-2.6），其中6条线路时间最短 目标分别为65、102、98、56.5、89.5、30（分钟）。问题三，将步行考虑在内，将此系统抽象为最短路问题下的有向赋权图，并在此基 础上以换乘次数最少为主要约束，以总行程时间最短、费用最低为目标，建立多目标0-1 整数线性规划模型，并给出求解的一般步骤与算法。关键词：邻接算法；有向赋权图；直达队列表；分层序列法；叠加有向赋权图

5、问题的重述为了迎接2008年奥运会，北京公交做了充分的准备，公交线路已达800条以上， 使得公众的出行更加通畅、便利，但同时也面临了多条线路的选择问题。为方便公众查 询公交线路，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。这个系统的核心是线路选择的模型与算法，另外还应该从实际情况出发考虑，满足 查询者的各种不同需求。需要解决的问题有：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。 并根据数据，利用模型算法，求出以下6对起始站到终到站最佳路线。（1）S3359一S1828（2）S1557一S0481（3）S0971一S0485（4）S0008一S00

6、73（5）S0148一S0485（6）S0087一S3676同时考虑公汽与地铁线路，解决以上问题。又知道了所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。问题的分析本题主要在三种不同情况下，研究任意两站点之间的线路选择问题。问题一，在仅考虑公汽线路的情况下，首先要根据题目给出的公交线路信息数据对 每条线路进行抽象化处理。然后由于乘坐公交有直达和转乘两种情况，为了方便用户查 询，我们先要运用MATLAB内建元胞结构来建立公汽直达数据库;】，之后再结合有向赋 权图建立最短路模型来设计需要转乘时的路线。问题二，由于地铁与邻近站点可换乘，可将每个地铁站点及其周边邻近的所有公交 站点抽

7、象成一个点处理。对于两条地铁线路可按照与问题一相同的抽象方法处理。在此 基础上按照问题一的思路确定任意两站点间的最佳方案。问题三，综合考虑公交和地铁站点的实际分布情况，人们有时会选择步行小段距离 之后再转车来节省时间或减少转车次数，本问研究此种情况下的出行方案。模型的假设相邻公汽站平均行驶时间（包括停站时间）：3分钟。相邻地铁站平均行驶时间（包括停站时间）：2.5分钟。公汽换乘公汽平均耗时：5分钟（其中步行时间2分钟）。地铁换乘地铁平均耗时：4分钟（其中步行时间2分钟）。地铁换乘公汽平均耗时：7分钟（其中步行时间4分钟）。公汽换乘地铁平均耗时：6分钟（其中步行时间4分钟）。公汽票价：分为单一票

8、价与分段计价两种；单一票价：1元其中分段计价的票价为：020站：1元2140站：2元40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）。假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁 费。假设各公交车都运行正常，不会发生堵车现象。假设公交、列车均到站停车。假设始发终点出入地铁需要步行4分钟；符号说明二.：孤:.是否在该有向赋权图上；:,:站点i一的总乘车时间；三：站点i一的乘车费用；Si :站点；A.:站点*一的直达路线数；上=:直达线路数矩阵；二=；： 最少换乘次数矩阵；/ j :0-1决策变量；/ j :弧（i, j）是否在该路径上；、:站点i一一 土间是否

9、地铁换乘地铁；二.:站点i 一 的乘车时间；三:站点i 一 的乘车总费用；:人为设定参数，表示乘客可接受的最多换乘次数；二T2 :总等待时间，总步行时间；Z,=3 :i - 最短直达为公汽（表示乘始发坐公汽等待3分钟），等于2为地铁。模型的建立与求解5.1问题一的模型建立与求解5.1.1图论抽象化处理模型实际生活中，公交线路复杂多样，不利于问题的求解，于是我们将三种公汽线路进 行抽象化处理，方法如下：（1）上、下行线原路返回线路这种线路有两个端点站，在两个端点之间双向行车，并且两个方向上的行车路线相 同，经过同样的站点序列。由于线路的方向不同，将上行线和下行线抽象为两条线路处 理。如图所示：S

10、1 S2 S3 S41111（2）线路为环行线实际情况中环形路线一般是双环，即将环形路线抽象为顺时针和逆时针两条线路。如图所示：（3）下行线与上行线经过站点不同由于下行线与上行线经过站点不同，该种线路显然可以被抽象为两条不同线路。如下图所示:S1 S2 S3 S4 S5 S6 S9S7S85.1.2公汽直达数据库Q的建立在现实生活中，乘客在进行公交路线选择时，通常会优先选择直达车，那么在查询 系统内部应设有任意两站点的直达线路表，以方便查询时快速查询是否有直达车，若有， 则直接输出所有直达车辆；若无，再搜索换乘路线。在建立公汽直达数据库Q的时候，由于本题站点较多，若采用通常方式，占的内存 较大

11、，所以本文采用MATLAB内建元胞结构，当元胞内队列不存在时不占用空间。具体元胞结构设计如下:CellfljCell14008CelI2TlCell2T2CeU230611(24000Cellfa?,!CeU27T2Cell27TSCell27T1003车号耗时（分钟）费用（元）L053391上图中Cell27,1008代表公汽直达数据库Q中第27行第1008个元胞（即从站 点S0027到站点S1008的直达公交线路信息），元胞中队列的每一行代表一辆直达车 信息。5.1.3基于不同目标的有向赋权图定义_ 由图论相关知识可将题中所提供的公汽网络抽象成一个有向赋权图 号=:三二,号中的每个顶点为每

12、个不同的站点，如果从号中的顶点到有直达路线，那么这两点之间就用有向边相连，记做三，方向为从i指向，表示可从值达，相 应的有一个数称为该有向边的权，这样公汽网络就抽象为一个有向赋权图。在 本模型中，赋权图中的权定义如下：时间:、_、,其分量为.站点-到站点直达时间无直达线路费用:w = :._,其分量为 ：=（PMvj）站点到站点Y的直达费用+oo无直达线路5.1.4最小换乘次数的确定如果用户查询的站点间无直达车辆，则查询系统需给出换乘方案，此时，我们需要 得知查询的站点间公交的最小换乘次数。由公汽直达数据库R我们可得任意两站点的直达线路数，由此可构造表示两两站点 间直达路线数目的直达线路数矩阵

13、上=；如：_，通过矩阵运算可得到任两站点间换乘线 路数矩阵，进而得到任两站点间的最少换乘次数矩阵二=1二.：.，.，从而可得任两站间所 需的最少换乘次数。 直达线路数矩阵的建立引入直达线路数矩阵如：_/，N表示所有公汽所经过的的站点总数。矩阵元素己.表示第i个站点到第个站点直达线路数n,其中，当时为无效路径，设定值为0, 即：_ fa (i# j)% lO (i = j)最少换乘线路数矩阵的建立以与表示方阵上的-次幕，为站点K的直达路线数，则：A?i =A?k1-Akjk=l其中，元素苴.为通过-r.- 1;次换乘从站点一的线路数。如上=】表示从站点2 到站点3有1条2次换乘路线，其换乘站点可

14、通过运算参数记录得到。引入矩阵三=:：-.；，其矩阵元素二: .为使得一顼=。的n的最小值，一日1,8)，即:贝叮矽-二：表示从站点i 一 必要的最少换乘次数，以矩阵。=表示最少换乘次数 矩阵，则：C = B 1其中，元素匚.表示从站点i 一必要的最少换乘次数。基于最少换乘次数矩阵二，每对起始站一终到站的最少换乘次数如下: 表2.0最小换乘次数表：线路编号123456起始站S3359S1557S0971S0008S0148S0087终到站S1828S0481S0485S0073S0485S3676最少换乘1211215.1.5最短路模型目标函数的建立(1)换乘次数最少基于5.1.3建立的有向赋

15、权图，引入0-1决策变量二.表示孤:)是否在起点与终 点的路径上，则=p 弧(i, j)在站点片到站点M的路径上气=。其他情徂若站点了.与站点可通过转乘到达，则由站点到站点匚之间换乘次数为经过的总孤 数减1，即换乘次数最小可表示为：(2)行程总时间最短基于5.1.3建立的有向赋权图，行程总时间最短表示为:(3)行程总费用最少设表示i 一 车辆票价属性，则=(1表示单一票制1元% =(2分段计价设s：.表示i一，所过站数，那么1一，直达费用权* f _表示为:_ 1% = 2司 E 1,20Plj = 1 2 qSj = 27sbE 21,400 鬼=可 E 4L H行程总费用最少可表示为：Mi

16、n PijXLj(li)EE约束条件的建立换乘次数约束基于对换乘次数最少这一目标的分析，可得在有向赋权图中换乘次数表达式，以c表 示乘客所能接受的最大换乘次数，则换乘次数约束可表示为：CMkEc 0, +oo),且为整数在实际应用中，查询系统中的:值可由查询用户自己设定。(2)最短路起止点约束由于号为有向图，则其中顶点分为“起点”、“中间点”、“终点”三类，对于起点只C（i=，）G = e）i # s,司有出的边而无入的边，对于中间点既有入的边也有出的边，对于终点只有入的边无出的 边。若求顶点s-e的最短路径，以二.表示进入第个顶点的边，以二.:表示出第个顶点的 边，则SB中的三类点约束可表示

17、为：j=lj=l(Lj)eE(ij)EE模型的建立基于以上部分，建立多目标最短路模型0-1规划表达式如下(s为起点，e为终点):Zssi -1 -c(tjl) EEAA( 1(i=s)乩Xjj - y XL = J% = 3行程总费用最少可表示为（正常票价-地铁换乘免费）：的。耳跖一 3衣亦现缸上=*1 = 131213约束条件的建立（1）换乘次数约束基于对换乘次数最少这一目标的分析，可得在有向赋权图中换乘次数的表达式，以 表示乘客所能接受的最大换乘次数，则换乘次数约束可表示为：X-1 -c)EEce 0,8)且为整数从实际出发，查询系统中的c值可由查询用户自己设定，当最小换乘次数小于二.时，

18、 输出无解。最短路起止点约束由于乏为有向图，则其中顶点分为“起点”、“中间点”、“终点”三类。对有向 图而言，若求顶点s - m的最短路径，以二.表示进入第，个顶点的边，以二.表示出第个 顶点的边，则s - m中的三类点约束可表示为：V V I耻X *=己与*j=ij=i(1 s, ej地铁间换乘约束站点i - *间是否地铁换乘地铁，使用丁七表示，那么丁七与走的路径上.需要满足：珏 + Yjk 三 2Yijk (Lj，k) EE； =2地铁转地铁情况只可能在D12与D18转乘，故换乘总次数不能够大于2：$ Yijk2 Zi?Zjk=2第 kkE 0-1规划模型的建立由和可得该模型的表达式：Mi

19、n yii - 1国Min T1 + T2+乌玲Min 岛外- 业 (LjJc)EE； q缸矣二31 j 二 DIM 18(i=s)-1 (i= e)% E 04ziizjk = 2zzjk = 2(Lj)*tiJ.kJeE1zij-zjk = 2模型说明：换乘次数约束，表示转乘次数应在乘客所能接受的最多转乘次数。最短路规划中的起点，终点约束，其中m为起点，日为终点。5.2.6最短路模型的求解模型的评价方法一、基于数据库您与Dijkstra算法的“邻接算法”求解此模型能够求解出转乘次数不超过两次的所有可行方案，设计方案的速度较快，人 们可依据自己的不同需求选择出行方案，故模型实用性较强；但本模

20、型还存在一定的局 限性，一般不用于转乘次数超过两次的情况。方法二、使用Lingo软件求解无转乘次数限制的方案（针对不同目标分别求解）上述最优化模型规模较大，但是通过模型分析章节抽象，模型所有约束与目标都已 经线性化，所以可采用Lingo软件严格按照0-1模型求解。此方法在不限制最小转乘数 时可以求得全局最优解。模型的结果表2.1 一线S3359S1828部分出行方案列表：求解方法转乘总时 间转站点1转站点2车辆1车辆2车辆3总费 用Lingo/邻接1104S1784-L436L167-3邻接1104S1784-L436L217-3邻接1110S1241-L436L167-3邻接1140S236

21、4-L469L217-3Lingo465S2903,D12,D37,S1671L15,L201,T02,L428,L417邻接267S3697S1784L484L485L1673邻接267S3697S1784L484L485L2173邻接267S2027S1784L324L485L1673邻接273D06S1784L484L485L1673邻B接279S1842S1671L123L475L0413表2.2二线S1557-S0481部分出行方案列表:求解方法转乘总时间转站点1转站点2车辆1车辆2车辆3总费 用Lingo31021919,3186,903L84,L189,L91,L2394邻接21

22、09D20S3186L084L189L4603邻接2109D20S3186L363L189L4603邻接2112D20S3186L084L189L4603邻接2112D20S3186L363L189L4603邻接2112D20S2424L084L417L2543邻接2112D20S2424L084L417L3123邻接2112D20S2424L084L417L4473邻接2121D20S1402L084L030L4603邻接2121D20S1402L363L030L4603表2.3三线S0971-S0485部分出行方案列表:求解方法转乘总时 间转站点1转站点2车辆1车辆2车辆3总费 用邻；接1

23、131S2184-L013L417-3邻接1146S2119-L013L395-3Lingo398D01,D15,3351L094,T001,L156,L4176Lingo/邻接299D01D21L094T001L0515邻接299D01D21L094T001L1045邻；接299D01D21L094T001L3955邻；接299D01D21L094T001L4505邻；接2124S2324S2482L013L132L4174邻；接2124S2324S2482L013L242L4174邻；接2127S3405S2515L013L079L4174表2.4四线S0008-S0073部分出行方案列表

24、:求解方法转乘时间转站点1转站点2车辆1车辆2车辆3总费 用Lingo356.5D15,D12,D25L200,T001,T002,L1035邻接183D13L159L4742邻接186S3614L159L0582邻接186S2083L463L0572邻接186S3315L159L0583邻接186S2303L355L3452邻接258D30D25L150T002L1035邻B接258D30D25L159T002L1035邻B接263.5D30D24L150T002L1035邻B接263.5D30D24L259T002L1035表2.5五线S0148S0485部分出行方案列表:求解方法转乘总时

25、间转站点1转站点2车辆1车辆2车辆3总费 用Lingo389.5D02,D15,3351L024,T001,L156,L4176Lingo/邻接290.5D02D21L024T001L0515邻接290.5D02D21L024T001L1045邻接290.5D02D21L024T001L3955邻接290.5D02D21L024T001L4505邻接290.5D02D21L024T001L4695邻接2109S0036S2210L308L156L4173邻接2112S0036D20L308L157L4173邻接2124S0036S1406L308L157L0453邻接2124S0036S208

26、2L308L156L0453表2.6六线S0087S3676部分出行方案列表:求解方法转乘总时间转站点1转站点2车辆1车辆2车辆3总费用Lingo030-T002-3邻接033-L231-1邻接042-L381-15.3问题三的模型建立与求解基于前面的分析公众出行时除了出行时间最短外，需要考虑的因素还包括转乘次数 和行程费用。再依据分层序列法，建立最短路问题的0-1整数规划模型。建立本模型首 先要创建邻接点矩阵E，需要考虑的两个赋权值为乘车时间和步行时间，即赋权图中任 意两点之间的权值有两个，即乘车时间W：.和步行时间/.，且都为已知量。令乘车时间 对应的决策变量为二.（0-1变量），步行时间

27、对应的决策变量为匚.（0-1变量）。5.3.1目标函数的建立：（1）行程总时间最短Min T1+T2+ 2 坛 0再（2）行程总费用最少Min P产 3%5.3.2约束条件的建立（1）最短路约束由于行走路线中任意两点间只会选择一种出行方式，因此： 1同时，决策变量还应满足最短路问题中的主要限制条件，如下：AAf 1（i = s）.（气 + 环）一）（理+*）= T。=司j=ij=i（o （i#s,e）（2）换乘次数约束公众在考虑出行时间尽量短的同时，也会考虑到换乘次数给出行带来的不便。以c表 示乘客所能接受的最大换乘次数，根据乘车次数确定换乘次数约束可表示为： % - M c（3）地铁间换乘约

28、束站点i 一 一 k间是否地铁换乘地铁，使用Y：-表示，那么丁七与走的路径孔 需要满 足：Xii + yjk 企 2Yijk （Lj,k）EE争辱=2地铁转地铁情况只可能在D12与D18转乘，故换乘总次数不能够大于2：L Vijk 2 ZirZjk = 2 65.3.3模型的建立根据问题分析中的目标分析和主要约束分析可建立多目标最短路模型，0-1规划表 达式（s为起点，e为终点）：MinMin12 耳声j+ 3Yjjk珂 M Yijke)=1=#:(Ljk)*%知=2zij 2jk = 2(Lj)击(LD*(Lj-kJ*zij2jk = 2Kjk 丑 YijkZ *后2气 + ViM 1 气

29、E 04% E (0,1)5.3.4模型的求解在公交和地铁交通网络系统对应的最短路权值确定的情况下，本模型线性可以考虑 运用Lingo软件编程求解，针对不同目标分别求解可能比较容易。另外，针对本模型我 们给出一种近似求解的算法。在所有站点之间的步行时间确定的情况下，公众出行时可以考虑步行小段距离再换 乘车次比较符合实际。基于这种思想，可以考虑将位置比较接近的站点抽象为一个点。 此时可以根据问题二站点的抽象方法，将这种点抽象为一个点处理。为方便描述，将公 交和地铁整个系统描述为公交，算法思想如下：步骤1：输入起始站点人和目的站点B；根据输入的站点进行优化，映射入紧邻站点集A =，、三:, B =

30、 D: ：?；。步骤2：查询直达队列表是否有4到8的乘车方案，若有则直接输出结果；若无，继续。步骤3：在公交站点数据库中查出过站点上及紧邻站点上=Am 的站点-】；，及经过站点8及紧邻站点二：.三的公交线路支： = 】， r-；步骤4：判断是否有L.i； = & ；，若有一条线路满足要求，则该公交线路即为最优线路 输出结果；若没有，继续。步骤5：从公交线路数据库中查出经过站点上的公交线路L)的站点三:.i E；：.i =1 ： 3 .】二，M =二 , ti：，以及经过站点三的公交线路:十：)的站点f =二 3 ，如 n =】1 3，p：o步骤6：判断是否有E(i,g) = F(g,h)。若有

31、一个站点满足要求，该站点即为一次换乘站 点。从入站点出发，在该站点换乘即可以到达站点。可能有一对或多对公交线路 满足要求，从中选择一条距离最短的公交线路即为最优线路，输出结果。若有 几个站点满足要求，则先分别求出每一个站点的距离最短的换乘方案，然后选 择所有方案中距离最短的换乘方案为最优线路，输出结果；若没有，继续。步骤7：从公交站点数据库中查得经过三:.i二的公交线路=二 . 从公交 线路数据库中查得线路T：.k；的站点 ；：/ = _ 2 5 . E；- - = 12 5 ,】；。步骤8：判断是否有二:.k注；=7： 1】；。若有某个站点E满足要求。则站点E为第二个换乘 站点。从起始站点A经过一次换乘（假设换乘点为站点C）,可以到达站点三，从 站点三可以换乘公交车直达目的站点。按照步骤4-6的方法求出从起始站点A到 站点E的一次换乘的最优线路，在按照2-3的方法求出从站点三到目的站点的最优 线路