公交线路模型

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的 , 如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员（打印并签名）：1.2.3.指导教师或指导教师组负责人（打印并签名）：数模指导组日期：2011 年8月26日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公交查询系统的研究与设计 摘要 本文旨在设计一个解决公交线路选择问题的自主查询计算机系统。 问题一，鉴于实际生活中公交路线复杂多样，我们将不同公交线路抽象化。把公汽 换乘和直达综合考虑，模型比较复杂，所以我们首先建立公汽直达数据库Q,用户查询 时，系统首先查询Q,得到所有直达车方案。在需要转乘时，针对不同用户需求，分别 以转乘次数最少、总耗时最短、总费用最少为目标，量化不同目标为有向赋权图的不同 权矩阵，始、终点连通为约束建立 0-1 整数线性规划模型来设计最佳路线。为了能提供多种公交线路备选方案，我们首先使用基于 Dijkstra 的邻接算法求解， 得到不同目标下的多种优化方案；对于邻接算法不易求解的多次转乘最优方案，我们采 用 Lingo 软件直接求得全局最优解。综合方案集（见 5.1.6 模型表1.1-1.6），其中6 条 线路时间最短目标分别为 67、102、106、62、105、49（分钟）。问题二，同时考虑公汽和地铁系统，首先把各地铁站点和周围邻近的公汽站点集抽 象为同一新站点，同时将两条地铁线路抽象化，计算公汽地铁直达数据库:门，再结合 地铁的费用与地汽换乘等待时间把地铁线与公汽线结合，建立多目标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 整数线性规划模型，并给出求解的一般步骤与算法。关键词：邻接算法；有向赋权图；直达队列表；分层序列法；叠加有向赋权图一. 问题的重述为了迎接 2008 年奥运会，北京公交做了充分的准备，公交线路已达 800条以上， 使得公众的出行更加通畅、便利，但同时也面临了多条线路的选择问题。为方便公众查 询公交线路，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。这个系统的核心是线路选择的模型与算法，另外还应该从实际情况出发考虑，满足 查询者的各种不同需求。需要解决的问题有：1. 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。 并根据数据，利用模型算法，求出以下 6 对起始站到终到站最佳路线。（1）S3359-S1828（2）S1557-S0481（3）S0971-S0485（4）S0008-S0073（5）S0148-S0485（6）S0087-S36762. 同时考虑公汽与地铁线路，解决以上问题。3. 又知道了所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。二. 问题的分析本题主要在三种不同情况下，研究任意两站点之间的线路选择问题。 问题一，在仅考虑公汽线路的情况下，首先要根据题目给出的公交线路信息数据对 每条线路进行抽象化处理。然后由于乘坐公交有直达和转乘两种情况，为了方便用户查 询，我们先要运用MATLAB内建元胞结构来建立公汽直达数据库Q ,之后再结合有向赋 权图建立最短路模型来设计需要转乘时的路线。问题二，由于地铁与邻近站点可换乘，可将每个地铁站点及其周边邻近的所有公交 站点抽象成一个点处理。对于两条地铁线路可按照与问题一相同的抽象方法处理。在此 基础上按照问题一的思路确定任意两站点间的最佳方案。问题三，综合考虑公交和地铁站点的实际分布情况，人们有时会选择步行小段距离 之后再转车来节省时间或减少转车次数，本问研究此种情况下的出行方案。三. 模型的假设1. 相邻公汽站平均行驶时间（包括停站时间）： 3分钟。2. 相邻地铁站平均行驶时间（包括停站时间）： 2.5分钟。3. 公汽换乘公汽平均耗时：5分钟（其中步行时间2分钟）。4. 地铁换乘地铁平均耗时：4分钟（其中步行时间2分钟）。5. 地铁换乘公汽平均耗时：7分钟（其中步行时间4分钟）。6. 公汽换乘地铁平均耗时：6分钟（其中步行时间4分钟）。7. 公汽票价：分为单一票价与分段计价两种； 单一票价：1 元其中分段计价的票价为：020站：1元2140站：2元40 站以上： 3 元8. 地铁票价： 3 元（无论地铁线路间是否换乘）。9. 假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁 费。10. 假设各公交车都运行正常，不会发生堵车现象。11. 假设公交、列车均到站停车。12. 假设始发终点出入地铁需要步行4分钟；四. 符号说明鞘：5 :% ：Si ：Akj:弧ij）是否在该有向赋权图上； 站点ij的总乘车时间； 站点1 fj的乘车费用；站点；站点kfj的直达路线数；A =(话如 c = (CJ :Yij :Yij : 知: 珀:直达线路数矩阵；最少换乘次数矩阵；0-1 决策变量；弧（i, j）是否在该路径上；站点if jf k间是否地铁换乘地铁；站点1 f j的乘车时间；R；：C :站点if j的乘车总费用；人为设定参数，表示乘客可接受的最多换乘次数;二：总等待时间，总步行时间;z： =3 :i - 最短直达为公汽（表示乘始发坐公汽等待3分钟），等于2为地铁。五. 模型的建立与求解5.1 问题一的模型建立与求解5.1.1 图论抽象化处理模型 实际生活中，公交线路复杂多样，不利于问题的求解，于是我们将三种公汽线路进行抽象化处理，方法如下：（1）上、下行线原路返回线路 这种线路有两个端点站，在两个端点之间双向行车，并且两个方向上的行车路线相 同，经过同样的站点序列。由于线路的方向不同，将上行线和下行线抽象为两条线路处 理。如图所示：S1 S2 S3 S4V1AYAV1（2）线路为环行线 实际情况中环形路线一般是双环，即将环形路线抽象为顺时针和逆时针两条线路 如图所示：3）下行线与上行线经过站点不同由于下行线与上行线经过站点不同，该种线路显然可以被抽象为两条不同线路。如下图所示：5.1.2 公汽直达数据库 Q 的建立 在现实生活中，乘客在进行公交路线选择时，通常会优先选择直达车，那么在查询 系统内部应设有任意两站点的直达线路表，以方便查询时快速查询是否有直达车，若有， 则直接输出所有直达车辆；若无，再搜索换乘路线。在建立公汽直达数据库Q的时候，由于本题站点较多，若采用通常方式，占的内存 较大，所以本文采用MATLAB内建元胞结构，当元胞内队列不存在时不占用空间。具体元胞结构设计如下：CellfljCellgCell13 Cell14008 CelI2TlCell如CeU23 0611(24000 Cell27TlCeU273 CellfalOOS 车号耗时（分钟）费用（元）L053391 上图中Cell27,1008代表公汽直达数据库Q中第27行第1008个元胞（即从站 点 S0027 到站点 S1008 的直达公交线路信息），元胞中队列的每一行代表一辆直达车 信息。5.1.3 基于不同目标的有向赋权图定义_ 由图论相关知识可将题中所提供的公汽网络抽象成一个有向赋权图 迂中的每个顶点为每个不同的站点，如果从三中的顶点到有直达路线，那么这两点之间就用有向边相连，记做，方向为从i指向，表示可从i直达，相应的有一个数称为该有向边的权，这样公汽网络就抽象为一个有向赋权图。在 本模型中，赋权图中的权定义如下：时间费用其分量为二=$m码）站点到站点m的直达时间 i +8无直达线路小=：._，其分量为氾=典出閑）站点K到站点Y的直达费用 （+8无直达线路5.1.4 最小换乘次数的确定如果用户查询的站点间无直达车辆，则查询系统需给出换乘方案，此时，我们需要 得知查询的站点间公交的最小换乘次数。由公汽直达数据库;?我们可得任意两站点的直达线路数，由此可构造表示两两站点 间直达路线数目的直达线路数矩阵 ，通过矩阵运算可得到任两站点间换乘线 路数矩阵，进而得到任两站点间的最少换乘次数矩阵 ，从而可得任两站间所 需的最少换乘次数。 5.1.4.1直达线路数矩阵的建立引入直达线路数矩阵，N表示所有公汽所经过的的站点总数。矩阵元素汀表示第i个站点到第个站点直达线路数匚，其中，当i=，时为无效路径，设定值为0,即：_ fa i# j)% lo 0 = j)5.1.4.2最少换乘线路数矩阵的建立以尸表示方阵上的匚次幕，込.为站点久亠的直达路线数，贝I：A?i =A?k1-Akjk=l其中，元素兰 为通过次换乘从站点i的线路数。如三=二表示从站点2到站点3有1条2次换乘路线，其换乘站点可通过运算参数记录得到。匚e 1严),即：引入矩阵三=:：-.；，其矩阵元素.为使得兰=二的匚的最小值,则表示从站点i必要的最少换乘次数，以矩阵:=(7:.表示最少换乘次数矩阵，贝U：C = E 1其中，元素J表示从站点i必要的最少换乘次数。基于最少换乘次数矩阵二，每对起始站f终到站的最少换乘次数如下: 表 2.0 最小换乘次数表：线路编号123456起始站S3359S1557S0971S0008S0148S0087终到站S1828S0481S0485S0073S0485S3676最少换乘1211215.1.5 最短路模型5.1.5.1 目标函数的建立(1)换乘次数最少 基于5.1.3建立的有向赋权图，引入0T决策变量二.表示弧J J是否在起点与终 点的路径上，则=$ 弧(i, 0在站点叫到站点M的路径上X J = I 0其他情祝若 与可通过转乘到达，则由站点到站点之间换乘次数为经过的总弧数减1，即换乘次数最小可表示为：2)行程总时间最短基于5.1.3建立的有向赋权图，行程总时间最短表示为：3)行程总费用最少 设肃表示车辆票价属性，则表示单一票制1元 ：2分段计价设二.表示所过站数，那么直达费用权十f表示为:%= 1Pii =Mij =占旳 E MOQij = 2,ss) E 21,40Qii = 2 円j E 41,-Foo行程总费用最少可表示为：5.1.5.2 约束条件的建立(1) 换乘次数约束基于对换乘次数最少这一目标的分析，可得在有向赋权图中换乘次数表达式，以匚表示乘客所能接受的最大换乘次数，则换乘次数约束可表示为：xij - 1 cc 0, +眄,且为整数在实际应用中，查询系统中的:值可由查询用户自己设定。(2)最短路起止点约束(i = e) (i 圭 s, e)由于三为有向图，则其中顶点分为“起点” “中间点” “终点”三类，对于起点只 有出的边而无入的边，对于中间点既有入的边也有出的边，对于终点只有入的边无出的 边。若求顶点三一m的最短路径，以;表示进入第个顶点的边，以二:表示出第个顶点的 边，贝临中的三类点约束可表示为：乙鞘乙咛j=ij=i(Lj)eE(ij)EE5.1.5.3模型的建立基于以上部分，建立多目标最短路模型0-1规划表达式如下(s为起点，e为终点):鞘-gCifDEE鞘 E 04（M） E E5.1.6最短路模型的求解5.1.6.1 模型的算法及评价方法一基于数据库Q与Dijkstra算法的“邻接算法”求解 步骤1：输入乘车始点i终点,（注：为最少换乘次数矩阵）若ch = 0则有直达线路，输出公汽直达数据库Q中所有直达信息，结束程序， 若】则有转乘1次线路，转步骤2,若=2则有转乘2次线路，转步骤4,若则存在转乘-次线路，但全局计算时间复杂度较高，终止邻接算法，采用Ling o求解。步骤2：求线路心的直达站点，及线路口:的直达站点m。步骤3：若存在，线路屮）、可能为一次转车的线路，保存队列L二，转步骤6。步骤4：求经过三:啲线路壬：以及求线路壬：的站点。步骤5：若存在，线路匚、二二、让小可能为两次转车的线路，保存队列U2,转步骤6。步骤6：修改队列匸、口中的成员，按其属性（路过的站点数，乘坐的车辆）根据不同目 标计算总行程时间、费用等。评价说明：这种算法的优点是把较优方案都记录在匚八LV中，方案丰富，这对用户多需求是 吻合的。缺点是对于转乘次数大于2次时，本方法无法在有限时间内求解。方法二 使用Lingo软件求解无转乘次数限制的方案 本方法运用 Lingo 软件，通过稀疏矩阵实现编程实现。评价说明： 这种算法可以弥补邻接算法的缺陷，在需要转乘次数大于2时，只要开始迭代计算 后，由于目标与约束线性， Lingo 只需要几秒即可求解出全局最优解。5.1.6.2 模型的结果表1.1 一线S3359-S1828部分出行方案列表：求解方 法转乘总时间转站点1转站点2车辆1车辆2车辆3总费用Lingo/ 邻接1104S1784一L436L167一3邻接1104S1784一L436L217一3邻接1140S2364一L469L217一3邻接1143S0519一L469L167一4Lingo/ 邻接267S3697S1784L484L485L1673邻接267S3697S1784L484L485L2173邻接267S2027S1784L324L485L1673邻接267S2027S1784L324L485L2173邻接267S2903S1784L015L485L1673邻接267S2903S1784L015L485L2173表1.2二线S1557-S0481部分出行方案列表:求解 方法转乘总时间转站点1转站点2车辆1车辆2车辆3总费 用Lingo3102S1919,S3186,S0903L084,L189,L091,L2394Lingo /邻接2109S1919S3186L084L189L4603邻接2109S1919S3186L363L189L4603邻接2115S1919S2424L084L417L2543邻接2115S1919S2424L084L417L3123邻接2118S1919S0992L084L417L4603邻接2118S1919S0992L363L417L4603邻接2130S1919S0417L084L497L4604邻接2130S1919S0417L363L497L4604邻接2133S3389S1427L084L454L4474表1.3三线S0971-S0485部分出行方案列表:求解方 法转乘总时间转站点1转站点2车辆1车辆2车辆3总 费 用邻接1131S2184一L013L417一3邻接1146S2119一L013L395一3邻接1152S1739一L119L417一3Lingo/ 邻接2106S2517S2159L013L290L4693邻接2109S1609S2654L013L140L4693邻接2109S1609S2654L024L140L4693邻接2124S2324S2482L013L132L4174邻接2124S2324S2482L013L242L4174邻接2124S2324S2480L013L132L4174邻接2124S1520S2265L119L008L4693表1.4四线S0008-S0073部分出行方案列表:求解 方法转乘总时 间转站点1转站点2车辆1车辆2车辆3总费 用Lingo462S3766,S2085,S0483,S0525L19 &L476,L17,L32 &L1035邻接186S2263一L355L345一2邻接189S2302一L355L057一2邻接1113S3415一L463L118一2邻接1131S3915一L463L118一2Lingo /邻接270S1691S2184L198L290L3453邻接270S1383S2184L043L290L3453邻接279S0630S1659L159L231L4593邻接279S0630S1659L159L381L4593邻接279S0854S1659L159L231L4593表1.5五线S0148-S0485部分出行方案列表:求解 方法转乘总时 间转站点1转站点2车辆1车辆2车辆3总费 用Lingo3105S3604,S2361,S2210L30 &L81,L156,L4174Lingo/邻接2109S0036S2210L308L156L4173邻接2112S0036S2482L308L157L4173邻接2118S3604S1381L308L129L4693邻接2118S3604S2026L308L123L4693邻接2118S3604S1383L308L129L4693邻接2121S3604S2840L308L454L4173邻接2121S0302S2027L308L427L4693邻接2121S3604S1321L308L129L4693邻接2124S3604S2079L308L206L4173表1.6六线S0087-S3676部分出行方案列表:求解 方法转乘总时 间转站点1转站点2车辆1车辆2车辆3总费 用Lingo/邻接168S3496一L454L209一2Lingo/邻接249S0088S0427L021L231L0973邻接249S0088S0427L206L231L0973邻接249S0088S0427L454L231L0973邻接252S0630S0427L021L381L0973邻接252S0854S0427L293L231L0973邻接252S1427S0427L021L381L0973邻接255S0541S2336L454L120L4623邻接261S3874S0280L021L068L4623邻接273S3874S0274L021L068L46235.2 问题二的模型建立与求解5.2.1 抽象化处理模型（1）可互换站点抽象化 因为地铁与公汽互换的时间较短而且比较容易换乘，故将这些站点看作紧邻站点， 将这些可互换的紧邻站点在整个交通网络中抽象为一个站点，使问题得到简化。（2）地铁线路抽象化基于5.1.1的抽象方法对两地铁线路Tl、T2进行抽象处理如下：T1：为双向线路，根据方向不同将其抽象为两条单向行驶线路。T2：为环行线路，环形路线一般是对开，故抽象成两条线处理。5.2.2公汽地铁直达数据库8的建立将紧邻站点抽象为一个新站点，此时建立的公汽地铁直达数据库二二实质上是新站 点与新站点间的直达路线集。当用户使用查询系统时，系统首先查找这两点所属的新站 点，然后查找新站点间可直达的线路，给出系统设计的多种路线方案，供用户按照自己 的目标选择。采用与5.1.2相同的思路及方法，把已知公汽线路到达久：都映射到汽，得出新直达数据库:&，再结合地铁的费用与地汽换乘等待时间就可以把地铁线与公汽线结合。 具体元胞结构设计图如下：CeUl,2 Celllf1008 Cell血 1Cell2,2Cell2,3 Cell24008 Cell2AlGeU27,2CeU27,3 Cell274003 车号耗时 （分钟）费用 （元）L053391 上图中Cell27,1008代表公汽直达数据库Q中第27行第1008个元胞（即从站 点 S0027 到站点 S1008 的直达公交线路信息），元胞中队列的每一行代表一辆直达车 信息。5.2.3 公汽地铁混合网络图的赋权根据5.1的简化，结合图论相关知识，将第二问公汽、地铁混合网络抽象成一个 有向赋权图 ，乏中的每个顶点为每个不同的站点，如果从壬中的顶点 厂到有直达路线，那么这两点之间就用有向边相连，记做 ，赋权图中的权可 根据不同的目标进行定义：时间：费用：V肥“其分量为斗j =其分量为pjj=3站点vi至可的直达时间 ,+8无直达线路pfvi环 站点vi至VJ的直达费用 、+8无直达线路5.2.4 最少换乘次数的确定采用与5.1.4相同的思路及方法，由公汽地铁直达数据库：；二可得任意两站点的直达线路数。由此可构造直达线路数矩阵二，确定换乘线路数矩阵：Aikn 1 x Akjk=l其中，元素丄为通过（n-1）次换乘从站点i f j的线路数。其换乘站点可通过运算参数记录得到。进而确定最少换乘次数矩阵：minn禺110,n E 1, cCf = Br - 1其中，矩阵中元素匚.表示从站点i - j必要的最少换乘次数。基于最少换乘次数矩阵c ，每对起始站一终点站的最少换乘次数如下: 表 2.0 最小换乘次数表：线路编号123456起始站S3359S1557S0971S0008S0148S0087终到站S1828S0481S0485S0073S0485S3676最少换乘1211205.2.5 最短路模型5.2.5.1 目标函数的建立引入0-1决策变量表示弧:j J是否在该路径上: 弧（i,j）位于顶点到*的路径上其他（1）换乘次数最少基于对混合网络的抽象,0若 与可通过转乘到达，则由站点到站点之间换乘次数为经过的总弧数减1，即换乘次数最小可表示为：2）行程总时间最短 乘车时间：其中，二为各站点最快直达时间，基于，包括地铁在内。 总等待时间：设表示ij最短直达为公汽（也表示乘始发坐公汽等待2分钟），则总等待时间可表示为：Tl=YijZij 总步行时间：将相同车型换乘、不同车型换乘的步行时间，均视为2 分钟：不同车型换乘多步行的4分钟：Tb =工 4*y，iCi,j）EEfZi=2地铁转地铁是不同车型换乘的特例，且只可能在D12与D18转乘，出现这种情况在，基础上减少步行时间4分钟:t产工沪y馭ziiuZjk-2PD12.D1B在地铁直达时，需要另外加上4 分钟出站步行时间:T日=知s %启）=2若始发乘坐地铁转公交到达终点，需要增加步行时间2分钟：L = BjB；Zjj = Z若始发乘坐公交转地铁到达终点，也需要增加步行时间2分钟:Tf= 2YiiLij=e;Zt=2总步行时间表示为:二=二一乙二二-二-二Min T1-FT2-FCtDeEf行程总时间最短表示为（总等待时间+总步行时间+乘车时间）：3）行程总费用最少设S表示i的车辆票价属性，贝I：（1表示单一票制一元碣=2表示分段计价（3表不地铁线路设二.表示i所过站数，那么if 直达费用权皿=：.齐；,，.表示为行程总费用最少可表示为（正常票价-地铁换乘免费）：4-qk=I1 = 1312135.2.5.2约束条件的建立（ 1）换乘次数约束 基于对换乘次数最少这一目标的分析，可得在有向赋权图中换乘次数的表达式，以 表示乘客所能接受的最大换乘次数，贝换乘次数约束可表示为：ce 0严)且为整数从实际出发，查询系统中的c值可由查询用户自己设定，当最小换乘次数小于二时， 输出无解。(2) 最短路起止点约束由于壬为有向图，则其中顶点分为“起点”、“中间点”、“终点”三类。对有向 图而言，若求顶点的最短路径，以二表示进入第个顶点的边，以二:表示出第个顶点的边，贝U中的三类点约束可表示为：I丹厂X y = H二j=ij=i(0(1 H s7 ej(3) 地铁间换乘约束站点i 一 一间是否地铁换乘地铁，使用:心表示，那么与走的路径-需要满 足：Yij + Yjk 三 2Yijk (ik) EE； Zi?Z|k = 2地铁转地铁情况只可能在D12与D18转乘，故换乘总次数不能够大于2：L Y哽兰 2 ZiPZik=2Cifjk)GEf5.2.5.3 0-1规划模型的建立由 5.2.5.1和5.2.5.2可得该模型的表达式：Min 乙 -1Min T1-FT2-FAA(10 = s)/ Yij- / Yji = -1(i= e) j=ij=i(0(i#気可(LjeE(Lj)eEr(iJ,k)eErziizjk = 2zijzjk = 2也j)tiJ.kJeE1zjk = 2y，i YijkYjk 三 YikYijk 2 ySj e 04模型说明： 换乘次数约束, 表示转乘次数应在乘客所能接受的最多转乘次数。 最短路规划中的起点，终点约束，其中三为起点，三为终点。5.2.6 最短路模型的求解5.2.6.1 模型的评价方法一、基于数据库;？与Dijkstra算法的“邻接算法”求解此模型能够求解出转乘次数不超过两次的所有可行方案，设计方案的速度较快，人 们可依据自己的不同需求选择出行方案，故模型实用性较强；但本模型还存在一定的局 限性，一般不用于转乘次数超过两次的情况。方法二、使用Lingo软件求解无转乘次数限制的方案（针对不同目标分别求解） 上述最优化模型规模较大，但是通过模型分析章节抽象，模型所有约束与目标都已 经线性化，所以可采用Lingo软件严格按照0-1模型求解。此方法在不限制最小转乘数 时可以求得全局最优解。5.2.6.2 模型的结果表2.1 一线S3359-S1828部分出行方案列表：求解 方法转乘总时 间转站点1转站点2车辆1车辆2车辆3总 费 用Lingo/邻接1104S1784L436L1673邻接1104S1784L436L2173邻接1110S1241L436L1673邻接1140S2364L469L2173Lingo465S2903,D12,D37,L15,L201,T02,7S1671L428, L41邻接267S3697S1784L484L485L1673邻接267S3697S1784L484L485L2173邻接267S2027S1784L324L485L1673邻接273D06S1784L484L485L1673邻接279S1842S1671L123L475L0413表2.2二线S1557-S0481部分出行方案列表:求解 方法转乘总时间转站点1转站点2车辆1车辆2车辆3总 费 用Lingo31021919,3186,903L84,L189,L91,L2394邻接2109D20S3186L084L189L4603邻接2109D20S3186L363L189L4603邻接2112D20S3186L084L189L4603邻接2112D20S3186L363L189L4603邻接2112D20S2424L084L417L2543邻接2112D20S2424L084L417L3123邻接2112D20S2424L084L417L4473邻接2121D20S1402L084L030L4603邻接2121D20S1402L363L030L4603表2.3三线S0971-S0485部分出行方案列表:求解 方法转 乘总时 间转站点1转站点2车辆1车辆2车辆3总 费 用邻接1131S2184一L013L417一3邻接1146S2119一L013L395一3Lingo398D01,D15,3351L094,T001,L156,L4176Lingo /邻接299D01D21L094T001L0515邻接299D01D21L094T001L1045邻接299D01D21L094T001L3955邻接299D01D21L094T001L4505邻接2124S2324S2482L013L132L4174邻接2124S2324S2482L013L242L4174邻接2127S3405S2515L013L079L4174表2.4四线S0008-S0073部分出行方案列表:求解 方法转乘时间转站点1转站点2车辆1车辆2车辆3总 费 用Lingo356.5D15,D12,D25L200,T001,T002,L1035邻接183D13L159L4742邻接186S3614L159L0582邻接186S2083L463L0572邻接186S3315L159L0583邻接186S2303L355L3452邻接258D30D25L150T002L1035邻接258D30D25L159T002L1035邻接263.5D30D24L150T002L1035邻接263.5D30D24L259T002L1035表2.5五线S0148-S0485部分出行方案列表:求解 方法转乘总时间转站点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邻接2124S0036S2082L308L156L0453表2.6六线S0087-S3676部分出行方案列表:求解 方法转乘总时间转站点1转站点2车辆1车辆2车辆3总费用Lingo030一一T002一一3邻接033一一L231一一1邻接042一一L381一一15.3 问题三的模型建立与求解 基于前面的分析公众出行时除了出行时间最短外，需要考虑的因素还包括转乘次数和行程费用。再依据分层序列法，建立最短路问题的0-1整数规划模型。建立本模型首 先要创建邻接点矩阵E,需要考虑的两个赋权值为乘车时间和步行时间，即赋权图中任 意两点之间的权值有两个，即乘车时间和步行时间：，且都为已知量。令乘车时间 对应的决策变量为二.（0-1变量），步行时间对应的决策变量为匚（0-1变量）。5.3.1目标函数的建立：（1）行程总时间最短Min（2）行程总费用最少MinA昭j+工叫(诩詐=01210(ijJchE5.3.2 约束条件的建立(1)最短路约束由于行走路线中任意两点间只会选择一种出行方式，因此：xij + Yi, k)cBr5.3.3 模型的建立 根据问题分析中的目标分析和主要约束分析可建立多目标最短路模型， 0-1规划表达式( s 为起点， e 为终点)：nn （呵+ %）-（号+均）=j=iCijltE*爼ij兰Yijkj=i1-10s.tjk 三 Yijk（iJ.keEzijzjk = 2L04k）EBrSij +羯兰1xLj e 04Yijk E 0,12jk = 2Oj）占j）占（iJ,k）eEr耳”现=25.3.4 模型的求解 在公交和地铁交通网络系统对应的最短路权值确定的情况下，本模型线性可以考虑 运用Lingo软件编程求解，针对不同目标分别求解可能比较容易。另外，针对本模型我 们给出一种近似求解的算法。在所有站点之间的步行时间确定的情况下，公众出行时可以考虑步行小段距离再换 乘车次比较符合实际。基于这种思想，可以考虑将位置比较接近的站点抽象为一个点。 此时可以根据问题二站点的抽象方法，将这种点抽象为一个点处理。为方便描述，将公 交和地铁整个系统描述为公交，算法思想如下：步骤1：输入起始站点A和目的站点B；根据输入的站点进行优化，映射入紧邻站点集A = D： =E = 二 .c ：o步骤2：查询直达队列表是否有A到B的乘车方案，若有则直接输出结果；若无，继续。步骤3：在公交站点数据库中查出过站点上及紧邻站点的站点，及经过站点B及紧邻站点上U的公交线路；步骤4：判断是否有，若有一条线路满足要求，则该公交线路即为最优线路输出结果；若没有，继续。步骤5：从公交线路数据库中查出经过站点上的公交线路的站点，以及经过站点三的公交线路逼J的站点。步骤6：判断是否有E(i,g) = F(g,h)。若有一个站点满足要求，该站点即为一次换乘站 点。从A站点出发，在该站点换乘即可以到达站点。可能有一对或多对公交线路 满足要求，从中选择一条距离最短的公交线路即为最优线路，输出结果。若有 几个站点满足要求，则先分别求出每一个站点的距离最短的换乘方案，然后选 择所有方案中距离最短的换乘方案为最优线路，输出结果；若没有，继续。步骤7：从公交站点数据库中查得经过的公交线路，从公交线路数据库中查得线路T(k)的站点G(k,w)(k = 1,2,3,-.mjw = 1,2,3, . ,n)o步骤8：判断是否有。若有某个站点E满足要求。则站点E为第二个换乘站点。从起始站点A经过一次换乘（假设换乘点为站点二），可以到达站点三，从 站点三可以换乘公交车直达目的站点。按照步骤4-6的方法求出从起始站点A到 站点E的一次换乘的最优线路,在按照2-3的方法求出从站点E到目的站点的最优 线路。两个换乘站点和两段最优线路即组成了从起始站点上到目的站点的最优 线路。若有多个站点满足，则分别求出各站点的最优换乘方案，比较各方案的线路距离，选择一种距离最短的换乘方案作为最后的结果，输出 结果。六. 模型的评价 邻接算法模型基于直达数据库，采用空间换取时间思想，适合查询系统设计标准且 能够适应工程应用；0-1规划模型在限制最小转乘数时可以得到与邻接算法同样的方案， 说明此模型的通用性较强，但无法像邻接算法一样求解多种方案；但在不限制最小转乘 数时可以求得全局最优解，这是其他所有算法无法达到的；从计算时间来分析，真正计 算耗时很短，如果将所需数据存放入内存不变，其求解速度将高于邻接算法。参考文献1 姜启源，谢金星，数学建模M第三版，北京：高等教育出版社，20032 王莉，李文权，公共交通系统最佳路径算法，东南大学学报，第34卷：第3期， 2004 年 3 月3 谢金星，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2005年7月 第一版4 孙惠泉，图论及其应用M，北京：20045 百度文库 附录5.1.2计算公汽直达数据库；?：filename二B2007da ta/1.1 公汽线路信息.txt; lines=1040;%最多1040行数据fid=fopen(filename,r);line_i=0; while(feof(fid) & line_ilines ) dataline=fgetl(fid);line_i=line_i+1; dataline_i=transpose(sscanf(dataline,%f);endfclose(fid);% a=data;x1=input(please input starting station:); y1=input(please input the terminal:);u=0;A=;w=size(data);for i=1:w(2)if any(datai=x1)& any(datai=y1) u=u+1;i1,j1=find(datai=x1);i2,j2=find(datai=y1);A(u,:)=floor(i/2)+1,j1,j2;endendA例如：please input starting station:0027 please input the terminal:1008 A =53 1 13注： 0027 站到 1008 站在第 53条线路上，分别为第 1 站和第 13 站。21