公交查询系统特等奖

1 公交查询系统的最佳乘车 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 研究与 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 【摘要】 本文将站点实体间的线路选择抽象为图论最短路模型采用 0-1 整数规划表述。建 立直达数据库 Q 作为数据基库，根据用户需求建立不同目标的 0-1 规划模型运用邻接 算法与 Lingo 分别求解，最终方案集通过多目标分层序列排序输出到用户终端。 第一问，在数据处理阶段将直行、环行线路分别抽象为 2、4 条路线(见 5.0)。建 立查询系统时考虑服务器要同时响应多个请求，计算任务繁重，采用空间换取时间的 策略，先建立站点至站点直达数据库 Q 来描述两两可直达站点的所有线路，用户查询 时，系统首先查询 Q，得到所有直达车方案。 在没有直达车情况下，针对不同用户需求，目标考虑：转乘次数、总耗时、总费 用、转站车辆是否始发、转乘站点负载量；在 Q 的基础上，量化不同目标为有向赋权 图的不同权矩阵(见 5.2.0)，以所求顶点u 到顶点 v的路径是否包含 xij 弧为决策变量， 上述 5 项用户需求为目标，始、终点连通为约束建立 0-1 整数线性规划模型(见 5.2.3 模型Ⅰ)。 为了能够为用户提供多种备选方案，我们首先使用基于 Dijkstra 的邻接算法求解， 得到不同目标下的多种优化方案；对于邻接算法不易求解的多次转乘最优方案，我们 采用 Lingo 软件直接求得全局最优解；两种方法求解步骤见(5.3.1)，综合方案集见(5.3.2 表 1.1~1.6)，其中 6 条线路时间最短目标分别为 67、102、106、62、105、49(分钟)； 两种求解方法的优劣在 5.4 中给出了详细 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 。 第二问考虑公汽与地铁混排方案，首先把各地铁站点 iD 和周围的公汽站点集 ( )iR s 抽象为同一新站点 kS ，把已知公汽线路到达 ( )iR s 都映射到 kS ，计算新直达数据 库 DQ ，再结合地铁的费用与地汽换乘等待时间就可以把地铁线与公汽线结合，建立 多目标 0-1 整数线性规划模型(见 6.2.3 模型Ⅱ)；对于转乘次数少于等于 2 次的方案仍 可通过邻接算法求解；对于邻接算法不易求解的多次转乘最优方案，虽然模型规模较 大但约束与目标线性程度较好，还可用 Lingo 软件求解得出 6 条线路的全局最优解； 综合方案集(见 6.3.2 表 2.1~2.6)，其中 6 条线路时间最短目标分别为 65、102、98、56.5、 89.5、30(分钟)；随后我们在 6.4 与 6.5 中给出了模型具体的评价与应用。 第三问综合考虑所有站点间步行与乘车情况，将其抽象为最短路问题下的叠加有 向赋权图，在此基础上以换乘次数为主要约束，以总行程时间(包括步行)最短、转站 车辆始发数最大、转乘站点负载量最小、费用最低为目标，建立多目标 0-1 整数线性 规划模型(见 7.3 模型Ⅲ)，并给出了求解的一般步骤与算法。 最后本文还对实现查询系统的具体方案给出了建议，对各模型在实际中的应用价 值进行了详细讨论，并提出了改进方案。 关键字： 邻接算法 有向赋权图 直达队列表 分层序列法 叠加有向赋权图 2 1 问题重述 我国人民翘首企盼的第 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、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题 的数学模型。 2 问题分析 本题主要在三种不同情况下，研究任意两站点之间的线路选择问题。联系实际，公 众乘坐公交车主要考虑的因素包括转乘次数、行程时间、车站始发情况、车站的车次负 载量及乘车费用等因素。为满足一般公众的乘车需求，主要按照公众对不同乘车信息的 重视程度，确定出最佳的乘车路线。 仅考虑公汽线路的情况下，首先，需要根据题目给出的公交线路信息数据，对每条 线路进行抽象处理，将分上下行的线路、双向行驶的线路和环行线路抽象为两条。然后， 主要考虑公众最关心的乘车因素，即转乘次数。在最少转乘次数的基础上考虑共众对其 他因素的需求，按照先后顺序考虑行程时间、车站始发情况、车站的车次负载量及乘车 费用，给出供公众选用的多种参考方案。并考虑以时间为主要目标的情况下，建立最优 化模型确定任意两站点行程时间最短的方案。 在考虑问题二的情况下，根据地铁与邻近站点可换乘的信息，可将每个地铁站点及 其对应的所有公交站点抽象成一个点处理。对于两条地铁线路可按照与问题一相同的抽 象方法处理。在此基础上按照相同的思路确定任意两站点间的最佳方案。 考虑公交及地铁站点的实际分布情况，有时会出现步行小段距离再转车的情况更能 节省时间或转车次数。因此，研究此种情况下的出行方案对节省出行时间具有重要的实 际意义。 3 模型假设 [1] 假设车站不重名； [2] 假设各路经上公交车发车频度相同； [3] 假设相邻站点间平均行驶时间一定； [4] 假设不出现交通阻塞，公交运行顺畅； [5] 假设不出现车辆故障及道路交通事故； [6] 假设始发终点出入地铁需要步行4分钟； [7] 假设公交准点到达，不考虑红绿灯等待时间。 3 4 符号系统 ijx —— 弧 ( , )i j 是否在该有向赋权图上； ijt —— 站点 i→ j 的总乘车时间； ijf —— 第 i个站点是否为 i→ j 的始发站； ijP —— 站点 i→ j 的乘车费用。 5 公汽站点之间线路选择模型（问题一） 本节主要研究任意两公汽站点间线路选择的数学模型与算法。分别在不同行程需求 下推荐最佳路线，给出更为人性化的站点负载压力及转乘点是否为始发站的提示。 z 通畅、便利目标：换乘次数最少； z 不同的行程需求：行程耗时最少； 行程费用最少； z 人性化查询设计：转乘站点是否为始发站提示； 站点负载压力提示。 基于此，本部分共分如下四小节： 5.0：数据处理，将三种公汽线路进行了图论抽象处理； 5.1：建立了可查询两站之间直达线路的“公汽直达数据库 Q”； 5.2：建立基于有向赋权图与最短路理论的 0-1 规划模型； 5.3：针对模型分别使用不同方法求解，得到多种适合不同用户的方案集。 5.0 数据处理——三种公汽线路抽象处理 根据题中信息，公汽线路分三种，下面将这三种线路进行数据处理： (1) 下行线、上行线原路返回 这种线路有两个端点站，在两个端点之间双向行车，而且两个方向上的行车路线相 同，经过同样的站点序列。由于线路的方向不同，因此，下行线和上行线可以抽象成两 条线路处理。 1S 5S4S3S2S 8S7S6S (2) 线路为环行线 实际中环形路线一般是双环，但在对这两条线路进行抽象时，为保证任意两站点距 离最近，把每条线路再抽象成 2条（如图所示）： A B 'A 'B q q ABA BAB q q ' ' ' ' ' ' A B A B A B (3) 下行线与上行线经过站点不同 由于下行线与上行线经过站点不同，显然，该种线路需要抽象成两条线路处理。 1S 5S4S3S2S 8S7S6S 10S 11S 12S 5.1 “公汽直达数据库Q”的建立 从实际出发，结合公众出行心理，公汽线路选择应优先考虑两站点之间是否有直达 4 车，那么在查询系统内部应设有任两站点的直达线路表，以方便查询时优先快速查询是 否有直达车，若有，则直接输出所有直达车辆；若无，再搜索换乘路线。 在建立 Q 的时候，数据结构的选择非常重要，本题共有 3957 个站点,若 Q 内每个队 列的每个数据都使用双精度实型储存，实际在 MATLAB 等软件内内存占用大约为 2GB，这 显然超越现阶段个人电脑极限，所以根据实际情况可以采用不同数据结构，本文采用 MATLAB 内建元胞结构，当元胞内队列不存在时不占用空间，具体元胞结构设计如下： Cell{1,1} Cell{1,2} 车号 费用 耗时 L001 2 27 L076 3 18 Cell{1,3} Cell{2,1} Cell{2,2} Cell{2,3} 图 1.1 元胞结构示意图 上图中 Cell{1,2}代表 Q 中第 1 行第 2个元胞（即从站点 S0001 到站点 S0002 的直 达公交线路信息），元胞中队列的每一行代表一辆直达车信息。 5.2 模型Ⅰ分析与建立 从查询系统设计角度考虑，当输入起讫点后，系统内部通过 Q 查询无结果时，系统 内部应自动搜寻换乘次数最少的路线，若换乘次数相同时有多种转乘方案，则系统应显 示所有转乘路线方案（包括转乘次数、行程总时间、途径总站点数、转乘站点及路线、 是否始发、行程总费用、转承站点负载压力）以供查询者自主选择。 同时，系统应向查询者推荐“时间最短”，“费用最省”，“转乘站始发站最多”，“负 载压力最小”的不同目标下的最佳路线。 5.2.0 基于不同目标的有向赋权图定义 引用图论相关知识，将题中所提供的公汽网络抽象成一个有向赋权图 ( , , )G V E W=JG ,GJG中的每个顶点为每个不同的站点, 如果从GJG中的顶点 iV 到 jV 有直达路 线，那么这两点之间就用有向边相连, 记做 ( , )i j E∈ ，方向为从 i指向 j ，表示可从 i直 达 j ，相应的有一个数 ( , )i jw v v 称为该有向边的权，这样公汽网络就抽象为一个有向赋 权图。赋权图中的权可根据不同的目标进行定义，本模型在确定不同目标时，将其分别 定义为（具体分析见 5.2.2） 时间： ( )t ij n nW t ×= 其分量为 ( , )i jv v i jij t v vt ⎧⎪= ⎨+∞⎪⎩ 站点 至站点 的直达时间 无直达线路 费用： ( )P ij n nW P ×= 其分量为 ( , )i jv v i jij P v vP ⎧⎪= ⎨+∞⎪⎩ 站点 至站点 的直达费用 无直达线路 始发： ( )f ij n nW f ×= 其分量为 ( , )i jv v i jij f v vf ⎧⎪= ⎨+∞⎪⎩ 站点 至站点 的直达线路是否始发 无直达线路 负载： ( ) 1r i nW r ×= 其分量为 ( )iv ii r vr ⎧⎪= ⎨+∞⎪⎩ 站点 的负载量 无直达线路 5 5.2.1 最少换乘次数的确定 在用户输入起点与终点后，系统需要立即给出至少要转乘几次才能够到达目的地， 这样就需要建立以下矩阵。 统计 Q 中各元素长度，可得任意两站点的直达线路数。由此可构造表示两两站点间 直达路线数目的直达线路数矩阵 ( )ij n nA a ×= ，通过矩阵运算可得到任两站点间换乘线路 数矩阵，进而得到任两站点间的最少换乘次数矩阵 ( )ij n nC c ×= ，从而可得任两站间所需 的最少换乘次数。 1）直达线路数矩阵的建立 引入直达线路数矩阵 ( )ijA a= ，其矩阵元素 ija 表示第 i个站点到第 j 个站点直达线路 数n ，其中，当 i = j 时为无效路径，设定值为 0，即： ( ) 0 ( )ij n i j a i j ≠⎧= ⎨ =⎩ (1.1) 以 N 表示所有公汽所经过的的站点总数，则直达线路数矩阵可表示为： 11 12 1 21 22 2 1 2 N N N N ij N N NN a a a a a a A a a a a × ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ """ """ # # # # # # # # # """ 2）换乘线路数矩阵的建立 直达矩阵 A为 N N× 阶方阵，矩阵 A的 2 次幂中元素表示任两站点间通过 1 次转乘 的路线数，即： 2A A A= ⋅ 其中， 2ijA 表示第 i个站点到第 j 个站点通过 1 次转乘的路线数，下面以 2A 第 1 行第 2 个元素 212a 为例对 2A 中元素意义进行举例说明： 《例》： 212 11 12 12 22 13 32 1 2N Na a a a a a a a a= ⋅ + ⋅ + ⋅ + + ⋅"" 假设上式中等号右边仅 13 1a = 、 32 1a = ，其余为 0，说明仅第 1 个站点可直达到第 3 个站点，第 3 个站点可直达到第 2 个站点，那么 212 1a = ，即第 1 站点可通过一次换乘 到达 2 站点，换乘点为站点 3。 以 nA 表示方阵 A的n 次幂， kjA 为站点 k → j 的直达路线数，则： 1 1 N n n ij ik kj k A A A− = = ⋅∑ (1.2) 其中，元素 nijA 为通过 ( 1)n − 次换乘从站点 i→ j 的线路数。如 34,3 1A = 表示从站点 4 到站点 3 有 1 条两次换乘路线，其换乘站点可通过运算参数 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 得到。 6 3）最少换乘次数矩阵的建立 引入矩阵 ( )ijB b= ，其矩阵元素 ijb 为使得 0nijA ≠ 的n 的最小值， [1, )n ∈ ∞ ，即： { }min | 0, [1, ) ( ) 0 ( ) n ij ij n A n i j b i j ⎧ ≠ ∈ ∞ ≠⎪= ⎨ =⎪⎩ (1.3) 则 ijb -1 表示从站点 i→ j 必要的最少换乘次数，以矩阵 ( )ijC c= 表示最少换乘次数 矩阵，则： 1C B= − (1.4) 其中，元素 ijc 表示从站点 i→ j 必要的最少换乘次数。 基于最少换乘次数矩阵 C，每对起始站→终到站的最少换乘次数如下： 表 1.0 最少换乘次数表 线路编号 1 2 3 4 5 6 起始站 S3359 S1557 S0971 S0008 S0148 S0087 终到站 S1828 S0481 S0485 S0073 S0485 S3676 最少换乘 1 2 1 1 2 1 5.2.2 基于最短路理论的模型分析 我们结合实际，主要考虑用户如下几个需求因素： 目标一：换乘次数最少； 目标二：行程时间最短； 目标三：行程费用最少； 目标四：转乘车辆始发最多； 目标五：站点负载压力最小。 目标分析 目标一：换乘次数最少 基于 5.2.0 建立的有向赋权图，引入 0-1 决策变量 ijx 表示弧 ( , )i j 是否在起点与终 点的路上，则： 1 ( , ) 0 i j ij i j v v x ELSE ⎧⎪= ⎨⎪⎩ 弧 位于顶点 至顶点 的路上 若 iv 与 jv 之间无直接相连的弧，但可通过中间节点转跳，表明由站点 i 到 j 之间不 可直达，但可通过转乘到达，则由 iv 到 jv 之间换乘次数为经过的总弧数减 1，即换乘次 数最小可表示为： ( ), 1ij i j E Min x ∈ −∑ (1.5) 目标二：行程总时间最短 时间权值 ( )t ij n nW t ×= ，则乘车总时间为: ( ), ij iji j E t x ∈ ∑ 7 公汽换公汽时间固定是 5分钟，则换乘时间为： ( ), 5 1ij i j E x ∈ ⎛ ⎞−⎜ ⎟⎜ ⎟⎝ ⎠∑ 行程总时间包括起始站点等待的 3分钟，行程总时间最短表示为： ( ) ( ), , 5 1 3ij ij ij i j E i j E Min t x x ∈ ∈ ⎛ ⎞+ − +⎜ ⎟⎜ ⎟⎝ ⎠∑ ∑ (1.6) 目标三：行程总费用最少 设 ijq 表示 i→ j 车辆属性 1 2ij q ⎧= ⎨⎩ 表示单一票制1元 分段计价 设 ijs 表示 i→ j 所过站数，那么 i→ j 直达费用权 ( )P ij n nW P ×= 表示为： 1 1 1 2, [1, 20] 2 2, [21, 40] 3 2, [41, ] ij ij ij ij ij ij ij ij q q s P q s q s =⎧⎪ = ∈⎪= ⎨ = ∈⎪⎪ = ∈ +∞⎩ 行程总费用最少可表示为： ( ), ij iji j E Min P x ∈ ∑ (1.7) 目标四：转乘车辆始发最多 为考虑所选路线中转乘站点是否为所需转乘车始发站，我们引入 0-1 变量 ijf 表示第 i个站点是否为 i→ j 的始发站，即始发权 ( )f ij n nW f ×= ： 1 ( , ) 0ij i i j f ELSE ⎧= ⎨⎩ 第 个站点是弧 线路的始发站 从 i→ j 个站点的路线中转乘点为所转乘车的始发点最多的路线可表示为： ( ), ij iji j E Max f x ∈ ∑ (1.8) 目标五：站点负载压力最小 首先假设终点站是奥运场馆，乘坐公车的人大多数都到达终点站，因此转车站点离 始发站的站点数越少越好(人少)： 负载压力 = 转乘站点离始发站的站点数 － 转乘站点离终点站的站点数 注：若终点站不是奥运场馆则可以通过对负载取绝对值表示离始发或终点越近转车 越方便。 8 i 001L 始发 终点 如图所示，站点 i 的负载压力 = 2-3 = -1，显然负载越小越好。根据式 1.1, jia 表 示进入第 i个站点的径数， ija 表示从第 i个站点出站的径数矩阵，以 ir 表示第 i个站点的 负载压力权 ( ) 1r i nW r ×= ： 1 ( ) N i ij ji j r a a = = −∑ 线路负载压力最小可表示为： ( ), i iji j E Min r x ∈ ∑ (1.9) 约束分析 1) 换乘次数约束 基于对目标一的分析，可得在有向赋权图中换乘次数表达式，以 c表示乘客所能接 受的最大换乘次数，则换乘次数约束可表示为： ( ), 1ij i j E x c ∈ − ≤∑ (1.10) [0, )c ∈ ∞ 且为整数 其中，参数 c 为人为设定值，分以下三种情况： [1] 当设定 0c = 时，为严格约束不能换乘； [2] 当设定c = ∞ 时，为无乘车次数约束，即可无限次换乘； [3] 当设定 c为不为 0的常数C 时，为约束换乘次数在C 次以内的情况； 《注》：参数 c可根据不同的计算需求进行自由选取。仅从数学模型角度考虑，为使 模型更具通用性，c的选取可到∞。 从实际角度出发，查询系统中的 c值可由查询用户自己设定，当最小换乘次数小于 ijb 时，输出无解。 2）最短路起讫点约束 由于G JG 为有向图，则其中顶点分为“起点”、“中间点”、“讫点”三类，对于起点只 有出的边而无入的边，对于中间点既有入的也有出的边，对于讫点只有入的无出的边。 对有向图而言，若求顶点 s → e的最短路径，以 ijx 表示进入第 j 个顶点的边，以 jix 表 示出第 j 个顶点的边，则 s → e中的三类点约束可表示为： ( ) ( ) 1 1 , , 1 ( ) 1 ( ) 0 ( , ) n n ij ji j j i j E i j E i s x x i e i s e= =∈ ∈ =⎧⎪− = − =⎨⎪ ≠⎩ ∑ ∑ (1.11) 9 5.2.3 模型Ⅰ建立 基于 5.2.2 分析，以 (1.5)～(1.9)为目标，以(1.10)、(1.11)为约束，建立多目标 最短路模型 0-1 规划表达式如下（ s 为起点， e为终点）： ( ), 1ij i j E Min x ∈ −∑ ( ) ( ), , 5 1 3ij ij ij i j E i j E Min t x x ∈ ∈ ⎛ ⎞+ − +⎜ ⎟⎜ ⎟⎝ ⎠∑ ∑ ( ), ij iji j E Min P x ∈ ∑ ( ), ij iji j E Max f x ∈ ∑ ( ), i iji j E Min r x ∈ ∑ ( ) ( ) ( ) , 1 1 , , 1 (1.10) 1 ( ) 1 ( ) (1.11) . . 0 ( , ) {0,1} ( , ) ij i j E n n ij ji j j i j E i j E ij x c i s x x i e S T i s e x i j E ∈ = = ∈ ∈ ⎧ − ≤⎪⎪⎪ =⎧⎪ ⎪− = − =⎪ ⎨⎨ ⎪ ≠⎩⎪⎪⎪ ∈⎪⎪ ∈⎩ ∑ ∑ ∑ 模型说明： (1.10) 换乘次数约束, 表示转乘次数应在乘客所能接受的最多转乘次数。 (1.11) 最短路规划中的起讫点约束，其中 s 为起点， e为讫点。 ijx —— 弧 ( , )i j 是否在该路径上； ijt —— 站点 i→ j 的总乘车时间； ijf —— 第 i个站点是否为 i→ j 的始发站； ir —— 站点 i的负载压力； ijP —— 站点 i→ j 的乘车总费用； c —— 人为设定参数，表示乘客可接受的最多换乘次数，详见 5.2.2 约束分析。 5.3 模型Ⅰ的求解（程序见附件 1.1～ 1.7） 5.3.1 模型求解的 2种方法 方法一、基于数据库 Q 与 Dijkstra 算法的“邻接算法”求解 Step 1：输入乘车始点 i终点 j ，（注： ( )ij n nC c × 为最少换乘次数矩阵，） 若 0ijc = 则有直达线路，输出Q中所有直达信息，结束程序， 若 1ijc = 则有转乘1次线路，转 Step 2， 若 2ijc = 则有转乘2次线路，转 Step 4， 若 2ijc > 则存在转乘 ijc 次线路，但全局计算时间复杂度较高，终止邻接算法， 采用Lingo求解； 10 Step 2：求线路s(i)的直达站点E(i,U),及线路t(j)的直达站点F(j,V)； Step 3：若存在 E(i,U)=F(j,V)，线路 s(i)、t(i)可能不止一种，即为一次转车的线路,保存 队列 U1，转 Step6； Step 4：求经过E(i,U)的线路r(K)求线路r(K)的站点G(K,W)； Step 5：若存在 G(K,W)=F(j,V)，线路 s(i)、t(j)、r(K)可能不止一种，即为两次转车的线 路，保存队列 U2，转 Step6; Step 6：修改队列 U1、U2 中的成员，按其属性(路过的站点数，乘坐的车辆)根据不同目 标计算总行程时间、费用等； 在邻接算法内不考虑转乘 2次以上主要原因是我们实际上并不是简单计算最短路 径，而是把较优方案都记录在 U1、U2 中，这对用户多需求是吻合的，但这样对复杂度 为 2( )O n 的算法来说还是不可行的，但我们权衡了二者的重要性决定用方案的丰富性取 代计算的准确性，而且从实际出发用户也不一定非常关心转乘次数大于 2次的方案。虽 然在本算法内我们不考虑转乘次数大于 2次的方案，但最后我们从规划角度使用 lingo 软件求解了全局最优值，等同于弥补了邻接算法的缺陷。 在计算机空间使用方面，我们通过对一些整形数组使用 16 位无符号整形，定义稀 疏元胞数组缩小空间占用，最终求解成功。 方法二、使用 Lingo 软件求解无转乘次数限制的方案（针对不同目标分别求解） 邻接算法可以求出多种方案，但对于转乘次数大于2的情况无法在有限时间内求解。 作为一个全面的查询系统必须非常全面，我们认为还是有一些用户会转乘多次且需要时 间最短是他们的最重要目的（前提是在代价低于使用专车费用），而且从理论角度考虑 仍需要找到求解转乘n 次时的可行方法。 在求解上述规划模型时，通过基表Q建立的数量非常庞大，采用传统求解方法时不 可行，但其中有大量 0 元素可以在 Lingo 软件内通过稀疏矩阵实现，但求解时间仍然需 要 20 分钟左右，主要为数据导入时间（19.9 分钟），只要开始迭代计算后由于目标与约 束线性，Lingo 只需要 6 秒左右即可求解出全局最优解（具体程序见附录 1.6）。 5.3.2 用户终端报表呈现系统：多目标分层序列排序 由于可行方案集 U1、U2 中的数据出现顺序不一定是用户所期望的，所以有必要根 据不同的用户需求对其排序，本文采用多目标分层序列法对方案集排序，实质上就是按 关键字顺序依次排序，即对于一个 M个字段的表按照给定的 N个字段排序（在数据库软 件里可以通过 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 SQL 语句直接操作），下面给出算法的文字描述： 1）按第一关键字（即一层目标）对列表排序； 2）按第二关键字对列表每个第一关键字相同的组进行排序; 3) 按第三关键字对列表每个第二关键字相同的组进行排序; 4）按第 N关键字对列表每个第 N-1 关键字相同的组进行排序。 采用多目标分层序列法排序，输出按照用户需求的报表样式，具体方案见下面表格。 （默认排序顺序是转乘次数、总时间、总费用、始发站点数、负载，可以根据不同用户 需求而改变） 方案报表说明：每行代表一种方案，表中加黑字格表示该方案该项指标全局最优； 表中总时间已包括起始点等车 3分钟。 11 表 1.1 一线 S3359→S1828 部分出行方案列表 求解方法 转乘 总时间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 转站点始发数 总负载 总费用 Lingo/邻接 1 104 1784 - 436 167 - 0 -20 3 邻接 1 104 1784 - 436 217 - 0 -20 3 邻接 1 140 2364 - 469 217 - 1 -1 3 邻接 1 143 519 - 469 167 - 0 -9 4 Lingo/邻接 2 67 3697 1784 484 485 167 0 -24 3 邻接 2 67 3697 1784 484 485 217 0 -24 3 邻接 2 67 2027 1784 324 485 167 0 -16 3 邻接 2 67 2027 1784 324 485 217 0 -16 3 邻接 2 67 2903 1784 15 485 167 0 -9 3 邻接 2 67 2903 1784 15 485 217 0 -9 3 表 1.2 二线 S1557→S0481 部分出行方案列表 求解方法 转乘 总时间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 转站点始发数 总负载 总费用 Lingo 3 102 1919,3186,903 L84,L189,L91,L239 - - 4 Lingo/邻接 2 109 1919 3186 84 189 460 0 -113 3 邻接 2 109 1919 3186 363 189 460 0 -113 3 邻接 2 115 1919 2424 84 417 254 0 -112 3 邻接 2 115 1919 2424 84 417 312 0 -112 3 邻接 2 118 1919 992 84 417 460 0 -126 3 邻接 2 118 1919 992 363 417 460 0 -126 3 邻接 2 130 1919 417 84 497 460 1 -90 4 邻接 2 130 1919 417 363 497 460 1 -90 4 邻接 2 133 3389 1427 84 454 447 1 77 4 表 1.3 三线 S0971→S0485 部分出行方案列表 求解方法 转乘 总时间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 转站点始发数 总负载 总费用 邻接 1 131 2184 - 13 417 - 0 6 3 邻接 1 146 2119 - 13 395 - 0 11 3 邻接 1 152 1739 - 119 417 - 0 -1 3 Lingo/邻接 2 106 2517 2159 13 290 469 0 -2 3 邻接 2 109 1609 2654 13 140 469 0 -33 3 邻接 2 109 1609 2654 24 140 469 0 -33 3 邻接 2 124 2324 2482 13 132 417 1 17 4 邻接 2 124 2324 2482 13 242 417 1 17 4 邻接 2 124 2324 2480 13 132 417 1 24 4 邻接 2 124 1520 2265 119 8 469 0 -52 3 表 1.4 四线 S0008→S0073 部分出行方案列表 求解方法 转乘 时间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 始发数 负载 总费用 Lingo 4 62 3766,2085,483,525 L198,L476,L17,L328,L103 - - 5 邻接 1 86 2263 - 355 345 - 0 48 2 邻接 1 89 2302 - 355 57 - 0 -16 2 邻接 1 113 3415 - 463 118 - 0 -46 2 邻接 1 131 3915 - 463 118 - 1 9 2 Lingo/邻接 2 70 1691 2184 198 290 345 0 0 3 邻接 2 70 1383 2184 43 290 345 0 37 3 邻接 2 79 630 1659 159 231 459 1 -83 3 邻接 2 79 630 1659 159 381 459 1 -83 3 邻接 2 79 854 1659 159 231 459 1 -60 3 表 1.5 五线 S0148→S0485 部分出行方案列表 求解方法 转乘 总时间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 转站点始发数 总负载 总费用 Lingo 3 105 3604,2361,2210 L308,L81,L156,L417 - - 4 Lingo/邻接 2 109 36 2210 308 156 417 1 -29 3 邻接 2 112 36 2482 308 157 417 1 -47 3 邻接 2 118 3604 1381 308 129 469 0 -21 3 邻接 2 118 3604 2026 308 123 469 0 -14 3 邻接 2 118 3604 1383 308 129 469 0 24 3 邻接 2 121 3604 2840 308 454 417 0 -22 3 邻接 2 121 302 2027 308 427 469 0 -13 3 邻接 2 121 3604 1321 308 129 469 0 3 3 邻接 2 124 3604 2079 308 206 417 0 -73 3 12 表 1.6 六线 S0087→S3676 部分出行方案列表 求解方法 转乘 总时间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 转站点始发数 总负载 总费用 Lingo/邻接 1 68 3496 - 454 209 - 0 -36 2 Lingo/邻接 2 49 88 427 21 231 97 0 -52 3 邻接 2 49 88 427 206 231 97 0 -52 3 邻接 2 49 88 427 454 231 97 0 -52 3 邻接 2 52 630 427 21 381 97 0 -44 3 邻接 2 52 854 427 293 231 97 0 -21 3 邻接 2 52 1427 427 21 381 97 0 -12 3 邻接 2 55 541 2336 454 120 462 0 -68 3 邻接 2 61 3874 280 21 68 462 1 -13 3 邻接 2 73 3874 274 21 68 462 1 -12 3 用户选线指南： 上面表中已按多目标分层序列法的默认目标排序（分别是表中转乘次数、总时间、 转车站点是否始发、转车站点总负载量、总费用五个字段），一般用户只需要从上到下 选取即可，但如果用户希望在转站时乘坐始发车（有座位）那么可以挑选始发字段为 1、 2 的方案，若希望转站时人较少的地方则可以考虑选则站点负载较小的方案。综述，本 模型 I求解的方案集使用于所有用户，具有很强的实用价值。 5.4 模型Ⅰ的评价 5.4.1 邻接算法评价 1) 建立在图论基础下能够求解出转乘次数不超过两次时的所有可行方案，并可根 据公众的不同需求，给出最佳需要方案，从此角度考虑，模型实用性较强； 2) 模型求解基于直达队列 Q，采用空间换取时间思想，适合查询系统设计标准能够 较强的适应工程应用； 3) 在转乘次数超过两次的情况下，运用本模型求解计算过程复杂，计算量过大； 故本模型存在一定的局限性。 5.4.2 0-1 规划 Lingo 求解方案评价 1) 在不限制最小转乘数时可以求得全局最优解，这是其他所有算法无法达到的， 例如在第 2、4、5 条线路上其转车次数为 3、4、3，但是耗时相对转 2 次的要节省许多； 2)在限制最小转乘数时可以求得与邻接算法同样的方案，表明模型的通用性较强， 但无法像邻接算法一样求解多种方案是用户所不能接受的； 3) 从理论角度分析，最优化模型规划角度可解具有很强的实际意义，例如从全国 范围考虑求解，那么转车 3~4 次也是可以接受的，只要耗时足够短； 4) 从计算时间来分析，尽管需要 20 分钟，但大部分时间为数据导入，只有 1%的 时间是真正计算耗时，如果将所需数据存放入内存不变，其求解速度将超越邻接算法； 5) 但 Lingo 不能求解出多种方案，实用性不如邻接算法。 6 同时考虑公汽与地铁最佳线路选择模型（问题二） 本问为综合考虑公汽与地铁线路的情况，解决查询系统中混合最佳路径选择问题的 模型与算法。 6.0 数据处理——公交网简化模型 1）将可互换站点抽象处理为一个站点 题中给出了地铁换乘公汽的数据文件，由地铁与公汽互换的时间来看，可互换的两 站间地理位置应非常接近且容易换乘，定义这些站点为紧邻站点，可将这些可互换的紧 邻站点抽象为一个站点，使问题得到简化。 13 <例>：信息数据第一行为“ 01D ： 0567S , 0042S , 0025S ”,则可认为这四个站点实际距离 非常近，为紧邻站点，所以可看做一个点处理，示意图如下： 抽象为一个站点 图 2.1 可互换站点抽象为一个站点示意图 基于这种思想，根据题目中给出关于地铁换乘公交的信息数据，可以将各地铁站点 及其紧邻站点在整个交通网络中抽象为一个点处理。 2）两种地铁线路抽象处理 基于 5.1.0 对三种公汽线路的抽象方法，以相同的方法对两地铁线路 1T 、 2T 进行 抽象处理如下： 1T ：为双向线路，故可以根据不同的方向将其抽象为两条单向行驶线路。 2T ：为环行线路，实际中环形路线一般是对开，故该种线路可以抽象成两条线路处理。 6.1 “公汽、地铁直达数据库 DQ ”的建立 将紧邻站点处理为一个新站点，则当综合考虑公汽与地铁时，建立的 DQ 实质上是 新站点与新站点间的直达路线集。认为在新站点所代表的站点集中的任意站点可通过步 行到达，且时间忽略。则当用户输入起、讫点后，系统内部首先自动查找这两点所属的 新站点，再查找新站点间可直达的线路，并给出起点及其附近站点可直达讫点及其附近 站点的路线。 采用与 5.1 相同的思路及方法，把已知公汽线路到达 ( )iR s 都映射到 kS ，计算新直达 数据库 DQ ，再结合地铁的费用与地汽换乘等待时间就可以把地铁线与公汽线结合。 具体元胞结构设计图如下： Cell{1,1} Cell{1,2} 车号 费用 耗时 L001 2 30 T001 3 22.5 Cell{1,3} Cell{2,1} Cell{2,2} Cell{2,3} 图 2.2 元胞结构示意图 上图中 Cell{1,2}代表直达队列表中第 1 行第 2 个元胞（即从站点 S0001 到站点 S0002 的直达混合线路信息），元胞中队列的每一行代表一辆直达车信息。 6.2 模型Ⅱ的分析与建立 经过数据处理后，紧邻站点被处理为一个新站点，该站点可等同看作问题一中的公 汽站点，当用户输入起、讫点后，系统内部通过直达线路队列表查询无结果时，则搜寻 转乘路线方案。同时，系统向查询者推荐不同目标下的最佳路线及转乘方案。 14 6.2.1 最少换乘次数的确定 采用与 5.2.1 相同的建模思路及方法，统计 DQ 中各元素长度，可得任意两站点的 直达线路数。由此可构造表示两两站点间直达路线数目的直达线路数矩阵 A′，可确定换 乘线路数矩阵： 1 1 N n n ij ik kj k A A A ′ − = ′ ′ ′= ⋅∑ (2.1) 其中，元素 nijA′ 为通过 ( 1)n − 次换乘从站点 i→ j 的线路数。其换乘站点可通过运算 参数记录得到。 进而确定最少换乘次数矩阵： { }min | 0, [1, ) ( ) 0 ( ) n ij ij n A n i j b i j ⎧ ′ ≠ ∈ ∞ ≠⎪′ = ⎨ =⎪⎩ (2.2) 1C B′ ′= − (2.3) 其中，矩阵C ′中元素 ijc′ 表示从站点 i→ j 必要的最少换乘次数。 基于最少换乘次数矩阵 'C ，每对起始站→终到站的最少换乘次数如下： 表 2.0 最少换乘次数表 线路编号 1 2 3 4 5 6 起始站 S3359 S1557 S0971 S0008 S0148 S0087 终到站 S1828 S0481 S0485 S0073 S0485 S3676 最少换乘 1 2 1 1 2 0 6.2.2 模型分析 采用与5.2.2相同的建模思路及方法，这里在考虑地铁后仍按目标的重要程度将“换 乘次数最少”、“行程时间最短”、“行程费用最少”、“转乘车辆始发最多”、“站点负载压 力最小”分设为第一到五层目标，基于 5.2.2 对各目标的分析与建立，这里不再复述分 析，仅在模型建立时给出具体表达式，这里由于对站点的定义与第一问不同，所以对时 间及费用的计算与第一问有所不同。 我们结合实际主要考虑用户如下几个因素： 目标一：换乘次数最少； 目标二：行程时间最短； 目标三：行程费用最少； 目标四：转乘车辆始发最多； 目标五：站点负载压力最小。 公汽地铁混合网络图的赋权 通过 6.0 的简化，结合图论相关知识，将第二问公汽、地铁混合网络抽象成一个有 向赋权图 ' ( ', ', ')G V E W=JJG , 'GJJG中的每个顶点为每个不同的站点, 如果从 'GJJG中的顶点 'iV 到 ' jV 有直达路线，那么这两点之间就用有向边相连, 记做 ( , ) 'i j E∈ ，赋权图中的权可 根据不同的目标进行定义 15 时间： ( )' 't ij n nW t ×= 其分量为 ( , )'' i jv v i jij t v vt ⎧⎪= ⎨+∞⎪⎩ 站点 至站点 的直达时间 无直达线路 费用： ( )' 'P ij n nW P ×= 其分量为 ( , )'' i jv v i jij P v vP ⎧⎪= ⎨+∞⎪⎩ 站点 至站点 的直达费用 无直达线路 始发： ( )' 'f ij n nW f ×= 其分量为 ( , )'' i jv v i jij f v vf ⎧⎪= ⎨+∞⎪⎩ 站点 至站点 的线路是否始发 无直达线路 负载： ( )' 1'r i nW r ×= 其分量为 ( )'' iv ii r vr ⎧⎪= ⎨+∞⎪⎩ 站点 的负载量 无直达线路 目标分析 目标一：换乘次数最少 基于对混合网络的抽象，引入 0-1 决策变量 ijy 表示弧 ( , )i j 是否在该路径上： 1 0 i j ij v v y ELSE ⎧⎪= ⎨⎪⎩ 弧(i,j)位于顶点 到 的路上 若 iv 与 jv 之间无直接相连的弧，但可通过中间节点转跳，表明由站点 i 到 j 之间不 可直达，但可通过转乘到达，则由 iv 到 jv 之间换乘次数为经过的总弧数减 1，即换乘次 数最小可表示为： ( ), ' 1ij i j E Min y ∈ −∑ (2.4) 目标二：行程总时间最短 1）乘车时间（ 'ijt 为各站点最快直达时间，基于 DQ ，包括地铁在内）： ( ), ' 'ij ij i j E t y ∈ ∑ 2）总等待时间： 设 ijZ =3 表示 i→j 最短直达为公汽（也表示乘始发坐公汽等待 3 分钟），等于 2 为地 铁（也表示始发乘坐地铁等待 2 分钟），总等待时间表示为： ( ), 1 ij ij i j E T Z y ′∈ = ∑ 3）总步行时间： 将相同车型换乘、不同车型换乘的步行时间，一同视为 2分钟 ( ), 2 1a ij i j E T y ′∈ ⎛ ⎞= −⎜ ⎟⎜ ⎟⎝ ⎠∑ 不同车型换乘多步行的 4分钟（虚线表示地铁，空心圆表示地铁站） 2 2 2 2 2 2 共多4分钟 表示为： ( ) 2 , 4 ij b ij Z i j E T y = ′∈ = ∑ 地铁转地铁是不同车型换乘的特例，且只可能在 D12 与 D18 转乘，出现这种情况在 bT 基础上减少步行时间 4分钟（虚线表示地铁，空心圆表示地铁站） 16 2 2 2 2 2,2 22 bT 表示为： ( ) 12, 18 , 2 , , 4 ij jk c ijk j D D Z Z i j k E T Y = = ′∈ = ∑ 在地铁直达时，需要另外加上 4分钟出站步行时间： ( , ) ( , )4 2d s e s eT y Z= = 若始发乘坐地铁转公交到达终点，需要增加步行时间 2分钟： ( ) , ; 2 , ' 2 ij e ij i s j e Z i j E T y = ≠ = ∈ = ∑ 若始发乘坐公交转地铁到达终点，也需要增加步行时间 2分钟： ( ) , ; 2 , ' 2 ij f ij i s j e Z i j E T y ≠ = = ∈ = ∑ 总步行时间表示为： 2 a b c d e fT T T T T T T= + − + + + 行程总时间最短表示为（总等待时间+总步行时间+乘车时间）： ( ), ' 1 2 'ij ij i j E Min T T t y ∈ + + ∑ (2.5) 目标三：行程总费用最少 设 'ijq 表示 i→ j 的车辆属性 1 ' 2 3 ijq ⎧⎪= ⎨⎪⎩ 表示单一票制1元 表示分段计价 表示地铁线路 设 'ijs 表示 i → j 所过站数，那么 i → j 直达费用权 ( )' 'P ij n nW P ×= 表示为： 1 ' 1 1 ' 2, ' [1, 20] ' 2 ' 2, ' [21,40] 3 ' 2, ' [41, ] 3 ' 3 ij ij ij ij ij ij ij ij ij q q s P q s q s q ⎧ =⎪ = ∈⎪⎪= = ∈⎨⎪ = ∈ +∞⎪⎪ =⎩ 行程总费用最少可表示为（正常票价 - 地铁换乘免费）： ( ) ( ) , ' 12, 18 ' , ' 3 , , ' ' 3 ij jk ij ij ijk i j E j D D q q i j k E Min P y Y ∈ = = ∈ −∑ ∑ (2.6) 目标四：转乘车辆始发最多（地铁不考虑） 为考虑所选路线中转乘站点是否为所需转乘车始发站，我们引入 0-1 变量 'ijf 表示 17 第 i个站点是否为 i→ j 的始发站，即始发权 ( )' 'f ij n nW f ×= ： 1 ( , ) ' 0ij i i j f ELSE ⎧= ⎨⎩ 第 个站点是弧 线路的始发站 从第 i个站点到第 j 个站点的路线中转乘点为所转乘车的始发点最多的路线可表示为： ( ), ' 'ij ij i j E Max f y ∈ ∑ (2.7) 目标五：站点负载压力最小 首先假设终点站是奥运场馆，乘坐公车的人大多数都到达终点站，因此转车站点离 始发站的站点数越少越好(人少)： 负载压力 = 转乘站点离始发站的站点数 － 转乘站点离终点站的站点数 注：若终点站不是奥运场馆则可以通过对负载取绝对值表示离始发或终点越近转车 越方便。 i 001L 始发 终点 如图所示，站点 i 的负载压力 = 2-3 = -1，显然负载越小越好。根据式 2.1, ' jia 表 示进入第 i个站点的径数， 'ija 表示从第 i个站点出站的径数矩阵，以 'ir 表示第 i 个站点 的负载压力权 ( )' 1'r i nW r ×= ： 1 ' ( ' ' ) N i ij ji j r a a = = −∑ 线路负载压力最小可表示为： ( ), ' 'i ij i j E Min r y ∈ ∑ (2.8)