乘公交 看奥运 数学建模

北京市公交查询系统 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 摘 要 本文要解决的问题是以即将举行的 08年 8 月北京奥运会为背景而提出的，人们为 了能现场观看奥运会，必然会面对出行方式与路线选择的问题。因此如何快速、高效地 从众多可行路线中选出满足各类需求的最优路线成为了解决此问题的关键。 显然，本文属于分层优化问题（即LSP问题）。需要解决的是在遍历所有可行路线的 情况下寻找出能满足不同查询者需求的路线，为此我们建立了宽容完全分层序列模型和 蚁群算法模型，采用了高效的广度优先算法和局部搜索枚举法对数据进行搜索，其基本 思想是从经过起（始）点的路线出发，搜寻出转乘次数不超过两次的可行路线，然后在 可行解中搜索出对应不同目标的最优解。为满足不同查询者要求，我们对三个问题都分 别建立了以转乘次数最少、时间最短、费用最低目标的优化模型。 对于问题一，在数据处理阶段将所有车次的路线都处理成上下行线路的形式，然后 针对实际生活中换乘次数不会超过两次建立了直达库，一次中转库和两次中转库，每当 输入出发站和目的站时便依次在数据库中进行局部搜索寻求各种最佳路线，在此基础上 有依据的以换乘次数为主要约束，以时间最短，花费最低为目标，建立宽容完全分层序 列模型，并给出求解方法和结果。 对于问题二，考虑公汽和地铁混排的方案，首先，我们将个地铁站点和其周围相邻 近的公汽站点虚拟为一个新的站点。把已知公汽到达都映射到新站点，计算新的直达库， 一次中转库和两次中转库，再结合地铁费用与与地汽换乘等待时间就可以把地铁与公汽 线结合，利用和问题一一样的模型和解法，建立宽容完全分层序列模型，并给出求解方 法和结果。 对于问题三，题目中说明假设已知所有站点之间的步行时间，也就是步行者不一定 必须按照公汽或地铁的路线行走，我们根据实际情况，做出一次步行不超过十分钟的假 设，综合考虑所有站点间步行与乘车等情况，发现如果还是利用问题一、二的局部搜索 的模型将会给求解带来很大的局限性，而利用蚁群算法进行遍历搜索可以很大程度上减 少运算时间，提高结果的准确性，于是我们在已有数据库的基础上，构造邻接矩阵，采 用蚁群算法求解遍历下的较优解问题，并给出详细算法流程和求解结果。 本文的最后，我们对模型进行了 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 ，并根据实际情况给出了改进方案。 关键字： 宽容完全分层序列 广度优先算法 局部搜索枚举法 蚁群算法 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. 模型的假设与符号说明 2.1 模型的假设 1：假设各线路上公交车发车的频率相同； 2：假设不出现交通阻塞，公交运行顺畅； 3：假设不出现车辆故障及道路交通事故； 4：假设不考虑红绿灯时间，公交车准时出发和到达； 5：假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁 费). 2.2 符号说明 j xn 第 j号汽车的第 n站 1 j A 第 j号汽车上行线的所有站数集合 2 j A 第 j号汽车下行线的所有站数集合 1 j P 属于分段计费的第 j 号汽车 2 j P 属于单一计费的第 j 号汽车 3. 问题分析 本文是解决在三种不同情况下任意两站点之间线路选择问题。根据查询者主要的考 虑因素包括换乘次数，时间长短，花费，乘坐压力以及起始站距离等，对查询者的不同 需求提供对应的最佳路线。为此，我们做了以下几个方面的分析。 3.1 乘客心理分析 通过对乘客的出行心理、行为的调查研究发现公交乘客选择路径主要受到以下几个 因素的作用：“换乘次数”、“时间长短”、“乘车费用”。换乘次数是指乘客从出发地到目 的地的过程中转车的次数；时间的长短包括乘车时间和换乘时间。 调查结果表明，一般情况下，优先考虑换乘次数的乘客占51.9%，优先考虑时间长 短的占35.5%，优先考虑费用多少的占9.8%，优先考虑其他因素的占2.8% 表3-1 优先考虑因素比例表 优先考虑因素 换乘次数 时间长短 费用多少 其他因素 比例（%） 51.9% 35.5% 9.8% 2.8% 优先考虑因素统计图 换乘次数 时间长短 费用多少 其他因素 图3-1公交出行转车情况统计图 由此可以将优先考率因素排序，分别为：换乘次数，时间长短，费用多少。 换乘枢纽是公交线网的核心。“换乘设计”指标影响到公交服务系统的形态及相互 连接性；影响到整个公共交通运输系统是否能够支持城市多中心发展模式，以及在各城 市分中心如何建立换乘中心，为各分中心之间提供具有竞争力的高品质公交服务；也影 响到是否能建立易于分辨的干线和支线服务网络，使乘客非常容易地理解公交服务系 统，降低提供信息的成本以及减少因寻找所需信息而产生的延误。 在公交服务设计导则中建议的换乘设计细则是： ① 前往和离开城市核心区95%的出行换乘不超过一次； ② 前往最近的城市次中心的所有出行中90％不需换乘； ③ 前往城市主要活动中心和主要口岸的所有出行中90%换乘不超过两次； ④ 任意两个相邻城市次中心之间的所有出行不需换乘。 根据公交系统的换乘设计，可以看出在城市内部，任意两点之间都可以在两次换乘 内到达。 调查结果表明，一般乘客出行都会选择换乘次数不超过两次的路线，调查结果如下 表： 表3-23公交出行者转车情况统计表 转车次数 不转车 一次 二次 二次以上 比例（%） 90.5% 8.5% 0.7% 0.3% 换乘次数统计图 不转车 一次 二次 二次以上 图 3-2 转乘次数统计图 根据上图可见，基本所有乘客都倾向在两次换乘内完成出行，因此下文不考虑三次 及三次以上的换乘路线是合理的。 3.2 北京公交网络分析 3.2.1 公交网络的连通性 在本题中，公交网络有 3种连通方式： �同路公交路段的连通； �不同公交线路路段在同一点通过换乘实现连通； �不同公交线路路段在不同点的连通，此种情况需要换乘多次车，增加了时间的消 耗。 3.2.2 结点性质 在公交网络中，结点可以按到一定原则抽象成网络图上的相关结点， 从而可以有效的模拟出公路之间的情况。 �不同公交线路在行程上是有部分重叠的，但各自的站点不可能完全重叠； �在公交网络中，结点与属性之间为一对多的关系。道路网中空间位置和属性相同 的同名结点，在公交网路中因位于不同的公交线路而性质和权值可能不一样。 3.2.3 有向线性质 实际的公交线路是有方向的，起点和终点决定了公交线路的行驶路 径和方向，即使是同一路公交车，其上行下行停靠的站点也可能不完全重叠，所以公交 网络图应该是有向的，应导入有向线路集，而空间位置相同的结点和权值在不同线路上 是不同。 3.2.4 复杂性 北京作为我国的首都，历史悠久，具有月 4000 多个站点和 520 条公交线 路，构成了一个及其庞大且复杂的公交网络。 3.3 针对问题分析 针对问题一，仅考虑公汽线路的情况下，首先，需要根据题目给出的公交线路信息 数据，对每条线路进行抽象处理，将分上下行的线路、双向行驶的线路和环行线路抽象 为两条。然后，主要考虑公众最关心的乘车因素，即转乘次数。在最少转乘次数的基础 上考虑共众对其他因素的需求，按照先后顺序考虑时间长短、乘车费用、乘车压力以及 转乘车辆是否始发等因素，给出供公众选用的多种参考方案。 在考虑问题二的情况下，根据地铁与邻近站点可换乘的信息，可将每个地铁站点及 其对应的所有公交站点抽象成一个点处理。对于两条地铁线路可按照与问题一相同的抽 象方法处理。在此基础上按照相同的思路确定任意两站点间的最佳方案。 考虑公交及地铁站点的实际分布情况，有时会出现步行小段距离再转车的情况更能 节省时间或转车次数。因此，研究此种情况下的出行方案对节省出行时间具有重要的实 际意义。 3.4 算法分析 以下便是我们求解问题和编制程序的具体算法，下述该算法比上叙一般路径选择算 法复杂度小很多，且满足中转次数不超过 2次情况下到达目的地。根据乘客出行心理分 析，根据转乘次数展开查询，首先考虑直达，其次是转乘 1 次和 2 次，算法的基本思想 框图如下： 图 3-2 算法分析流程图 根据题意要求，考虑到查询系统对查询速度有较高要求；我们首先建立公交直达线 路数据库 L；然后在 L的基础上，先分别求出与出发站点和目的站点相关的车次的集合， 再求交集，交集里的元素即为可行解。如果交集为空，再衍生出与上述车次相关的站点 集合，并求交集。如此可以迭代下去，构建一次中转数据库和二次中转库； 根据乘客的要求在数据库中搜索出需要的答案。通过这种用空间换时间的做法，有 效减少查询的计算次数，提搞了搜索效率。 4. 数据分析及处理 根据题目中所给的相关信息，公交线路共 520 条，停靠点 3975 个，地铁线路两条， 共 39 个站点，可将所有的线路分为三种：上下行停靠点完全一致（双向行驶），上下行 停靠点不完全一致，上下行停靠点完全不一致（单向环形），对 3 种线路进行处理，使 所有线路都成为上下行形式，这样一条线路对应两条路线。 4.1 线路数据处理 �上下行停靠点完全一致（双向行驶） 以 L001 为例： S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820 -S3914-S0128-S0710 处理后变为： 上行： S0619→S1914→S0388→S0348→S0392→S0429→S0436→S3885→S3612→S0819→S 3524→S0820→S3914→S0128→S0710 下行： S0710→S0128→S3914→S0820→S3524→S0819→S3612→S3885→S0436→S0429→S 0392→S0348→S0388→S1914→S0619 �上下停靠点不完全一致 以 L002 为例，处理后变为： 上行： S3748→S2160→S1223→S1404→S2377→S1477→S2017→S2019→S1321→S1381→ S1383→S1691→S3766→S1729→S2654→S3231→S3917→S2303→S1327→S3068→S2833 →S1733→S2113→S2636→S0012→S1968→S0004 下行： S0004→S1968→S0012→S2636→S2113→S2112→S2833→S0618→S1327→S2303→ S3917→S3231→S2654→S1729→S3766→S1691→S1383→S1381→S1321→S2019→S2017 →S1477→S1404→S1223→S2160→S3748 �上下行停靠点完全不一致（环形行驶） 以 L017 为例： S3748-S2160-S0732-S3078-S2808-S2816-S3028-S1123-S3029-S2764-S2543-S2742 -S2533-S1839-S2751-S2755-S2937-S1929-S1007-S0940-S1907-S2085-S0609-S0483-S0 604-S2650-S3693-S1659-S2962-S0622-S0456-S0427-S0582-S0577-S1895-S3648-S0668 -S3081-S3078-S2082-S0683-S2160-S3748 处理后变为： 上行： S3748→S2160→S0732→S3078→S2808→S2816→S3028→S1123→S3029→S2764→S 2543→S2742→S2533→S1839→S2751→S2755→S2937→S1929→S1007→S0940→S1907 →S2085→S0609→S0483→S0604→S2650→S3693→S1659→S2962→S0622→S0456→S04 27→S0582→S0577→S1895→S3648→S0668→S3081→S3078→S2082→S0683→S2160→S 3748 下行： S2085→S0609→S0483→S0604→S2650→S3693→S1659→S2962→S0622→S0456→S 0427→S0582→S0577→S1895→S3648→S0668→S3081→S3078→S2082→S0683→S2160 →S3748→S2160→S0732→S3078→S2808→S2816→S3028→S1123→S3029→S2764→S25 43→S2742→S2533→S1839→S2751→S2755→S2937→S1929→S1007→S0940→S1907→S 2085 为了保证任意两点距离最近，我们将环形路线抽象为两条，方式如图所示： 上行 ABA ，下行 BAB 4.2 站点位置数据处理 由题目中已给的地铁换乘公汽的数据，可以看出，一个地铁站往往有一个或多个公 交车站靠近，为了处理的方便，我们将这这些靠近的站点抽象处理为一个站点（即用元 胞进行处理，一个元胞对应靠近的几个站台）。 4.3 数据库的建立过程 Step1: Step1: Step1: Step1:把公交线路了转换为集合表示: { }1 2, ...i nA x x x= Step Step Step Step2 2 2 2: : : : 构建自定义 length 函数 考虑到公交车站的方向性，单行线，双行线，环线；在进行运算时，首先把集合转换成 矩阵, ( )1 2, ...i nA x x x= 则函数定义为第 k列车站与第 i列车站间的站数： ( ), i k length x x k i= − Step Step Step Step3 3 3 3：采用遍历所搜已知任意起点 aj和终点 ak； j j x A∈起点 k k x A∈终点 求出包含 aj的集合 Aj和包含 ak 的集合 Ak； j j x A∈起点 k k x A∈终点 求出 Aj与 Ak的交集；（Aj=Ak or Ajk or 空集） j k x A A∈ ∩公共 x A∈公共 公共 分别对 Ajk 和空集情况进行考虑 构建直达数据库 若 = j k A A ，则判定为 j=k,即坐第 j号车直达，距离为 ( ),j jlength x x起点 终点 ，将所有可直 达路线记入直达库 构建一次换乘数据库 若 j k A A≠ ， j k A A φ∉∩ ，则求出 x A∈公共 公共，将出发站和目的站，乘坐车次，转 乘站台等信息都记入一次中转库。 构建两次换乘数据库 若 j k A A≠ ， j k A A φ∈∩ ，则求得 1sank j sanx A A∈ ∩ 2sank k sanx A A∈ ∩ { }1 2,sank sank sanx x A⊆ 将出发站和目的站，乘坐车次，转乘站台等信息都记入二次中转库。 判定为三次换乘 若不存在 j k A A≠ ， j k A A φ∈∩ ，{ }1 2,sank sank sanx x A⊆ 使得 1sank j sanx A A∈ ∩ 2sank k sanx A A∈ ∩ 则求得 1 2,sank san sank fourx A x A∈ ∈ ，使得 1sank j sanx A A∈ ∩ 2sank k fourx A A∈ ∩ four san four x A A∈ ∩ 距离为 ( ) ( ) ( ) ( )3 3 4 4min = , + , + , ,j j k k four four length x x length x x length x x length x x+sank1 sank1 sank2 sank2起点 终点 即判定为三次换乘内最短距离； 5． 问题一的解答 针对问题一，我们建立了模型一。 5.1 模型一的建立（宽容完全分层序列模型） 模型一的准备 多目标分层序列法是根据各个目标的重要程度顺序排列，以决定在多个目标中，各 个目标考虑的优先级，假设为： 表示 R1最优先考虑，F2次之、入最次。然后将第一个目标与约束并列，求解之， 得到最优解集 R1，再在 R1约束下，求 F2(x)的最优值，得 R2，依次类推，直到求出 Rm， 即为多目标问题的最优解集合。 但是分层序列法的缺陷是，由于求解员优化问题 1 max ( ) x K F x x R − ⎧ ⎨ ∈⎩ 其解集 R k 有可能缩小为一个有限集合甚至一点，从而大大限制了 F k + 1的优化范围， 因此经常采用其改进形式——有宽容度的冷层序列法。在求解后一个目标 F i 的最优值 时，不是局限在前一个目标的是优解集 R k − 1去寻找，而是在其最优解集 Rk − 1的一个有 宽容的集合中寻找，从而大大扩大了目标 R k 优化范围。 宽容度分层序列法表示如下： 1 1 1 1 1 2 2 2 ( ) ( ) ( ) ( ) ( ) ( ) m x G x R m m m x R F x MaxF x F x MaxF x F x MaxF x − ∈ ∈ ∈ = = = ⋮ 其中， 1 | ( ) ( ) 0 i i i i i T T R x R F x F x a a−= ∈ ≥ − > 为一容许的宽容限度。 该方法不但性能优越，而且每一步都有比较适当的实际含义和决策背景，便于建模 人员与实际决策者之间的对话，是一种有效的分析方法。 针对问题一，仅考虑公汽线路，先找出经过任意两个公汽站点最多转乘两次公汽的 路线并建立数据库，然后再根据不同查询者的需求采用有宽容度的冷层序列模型在数据 库中搜寻出最优路线。 5.1.1 确定目标函数 目标一：换乘次数最少 根据绝大多数乘客的心理，换乘次数对乘客的选择起决定性的作用，在算法分析中， 我们可以通过搜索直达库，一次中转库，二次中转库来找出所有可行方案，在所有可行 方案中选出换乘次数最少的方案。 根据数据库中的集合表示方式，Ak 表示为第 k辆公交车的路线,有数据库路线可知， 换乘次数为： 其中为 size 为矩阵中的元素数， G 为换乘次数的可行域。 目标二：时间最短 考虑到是在看奥运的前提下，乘客的时间观念应该较强，所以时间优化也是较为重 要的一点，根据题目假设，相邻公汽站平均行驶时间（包括停站时间）为 3分钟，公汽 换乘公汽平均耗时为 5分钟，行程时间等于乘车时间与转车时间之和。由此可以确定时 间最短的目标函数为： 1 2 2 2 2 ( ) ( , ) ( 1) ( ) ( ) k j x R F x length x x n F x Min F x λ β ∈ = × + − × = 其中， 1 | ( ) ( ) 0 i i i i i T T R x R F x F x a a−= ∈ ≥ − > 为一容许的宽容限度。 length是取两个站点之间相邻公汽站数目， xk —— 表示出发站；λ— 表示相邻公汽站间花费时间：3 分钟； xj —— 表示目的站；β— 表示公交换乘公交花费时间：5 分钟； 目标三：乘车费用 附录一中指出公汽票价分为单一票价与分段计价两种，其中分段计价的票价为： 0～20 站：1元；21～40 站：2元；40 站以上：3元。 由此可以确定目标函数为： 1 2 2 3 3 3 3 ( )= ( ) ( )= ( ) k i P m n k m E x A x R F x P f x F x MinF x ∈ ∈ ∈ +∑ ∑ 其中票价为分段函数： 1 1 0 ( ) 20 2 21 ( ) 40( ) 3 ( ) 41 k p k k k length x length x f x length x ≤ ≤⎧ ⎪ ≤ ≤= ⎨ ⎪ ≥⎩ 　 　　 P 1 —— 分段计价的公交车； P2 —— 单一票价的公交车； 2 m P∑ —— 乘坐了m次单一票价车的费用和，每次费用为 1 元； 1 ( )P n k f x∑ —— 乘坐了 n次分段计费车的费用和； 5.1.2 确定约束条件 ( ) 1 1 1 1 1 2 ( ) ( ) ( ) , ,...., x G k F x MinF x F x size A A A ∈ = = 约束条件的确定 由所给数据易确定换乘次数的约束条件为： . . 0 n n x p s t n ∈⎧ ⎨ ≥⎩ 然后将第一个目标与约束并列，求解之，得到最优解集 R1，再在 R1约束下，求 F2(x) 的最优值，得 R2，依次类推，直到求出 R3，即为多目标问题的最优解集合。 5.1.3 由此可以确定问题一的模型： 在问题分析中，根据调查可知乘客对五种目标的需求程度优先顺序为： > > > >换乘次数 时间 花费 车载压力 乘车压力 综上所述，采用宽容完全分层序列模型建立最优路线选取模型如下： 2 1 1 1 1 3 3 3 2 2 2 ( ) ( ) ( ) ) ( = ( ( ) ) x x G x R R F x MinF x F x F x MinF nF x Mi x ∈ ∈ ∈ = = . . 0 n n x p st n ∈⎧ ⎨ ≥⎩ 其中， G 为换乘次数的可行域， 1 | ( ) ( ) 0 i i i i i T T R x R F x F x a a−= ∈ ≥ − > 为一容 许的宽容限度 模型说明： xk —— 表示出发站；λ— 表示相邻公汽站间花费时间：3 分钟； xj —— 表示目的站；β— 表示公交换乘公交花费时间：5 分钟； 2 m P∑ —— 乘坐了m次单一票价车的费用和，每次费用为 1 元； 1 ( )P n k f x∑ —— 乘坐了 n次分段计费车的费用和； 5.2 模型一的求解（程序详解附录一） 5.2.1 求解过程 基于数据库的查询搜索算法 步骤一： 输入出发站名 SXXXi 和目的站名 SXXXj 查询所有经过出发站名 SXXXi 和目的站名 SXXXj 的车次 得到结果： 库 LS1：LAi（储存经过 SXXXi 的所有车次） 库 LE1：LBi（储存经过 SXXXj 的所有车次） 步骤二： 比较库 LS1 与库 LE1 中是否有相同车次？ 若存在相同车次，则记入库（直达库） 步骤三： 查询（1）：库 LAi 中所有车次的各站名 SAi 查询（2）：库 LBi 中所有车次的各站名 SBj 得到结果： 库 SS1：SAi 库 SE1：SBj 步骤四： 比较库 SS1 和库 SE1 中是否有相同站名。 若存在相同站名，则记入库（一次中转库）：SAi=SBj，及相应的始乘车次和转乘车 次 步骤五： 查询（3）： 经过 SAi 的所有车次 查询（4）： 经过 SBj 的所有车次 得到结果： 库 LS2：LAm 经过 SAi 的所有车次 库 LE2：LBn 经过 SBj 的所有车次 步骤六： 比较库 LS2 和库 LE2 中相同的元素。 若存在相同的车次，则记入库（二次中转库）：LAm=LBn，及相应的两个中转站名和 从出发站点、目的站点到中转站的车次 至此，完成了对所有可行路线的搜索，并保证不去计算超过两次中转以上的方案。 算法结束 。 查询得出结果 对上述存储的经过两个站点（出发站和目的站）的不同路线，根据不同模型进行最 优路线进行搜索，得出查询者满意的最优路线。 5.2.2 编程实现求解 依据确定的模型的目标函数及其约束条件，借助 MATLAB 编程（具体程序见附录）求 解得到如下结果： 表 5-1 S3359→S1828的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 435 166 1241 32 101 2 时间最少 435 166 1241 32 101 2 费用最少 435 166 1241 32 101 2 表 5-2 S1557→S0481的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 83 416 515 1919 2424 37 118 4 时间最少 362 416 253 1919 2424 37 118 3 费用最少 362 416 253 1919 2424 37 118 3 表 5-3 S0971→S0485的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 12 376 1215 32 101 3 时间最少 12 376 1215 32 101 3 费用最少 12 376 1215 32 101 3 表 5-4 S0008→S0073的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 354 281 2263 26 83 4 时间最少 354 281 1064 26 83 2 费用最少 462 344 2833 26 83 2 表 5-5S0148→S0485 的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 307 155 416 36 3351 35 112 3 时间最少 307 155 416 36 3351 35 112 3 费用最少 307 155 416 36 3351 35 112 3 表 5-6 S0087→S3676的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 453 208 1893 2 65 12 8 20 时间最少 453 208 1893 2 65 12 8 20 费用最少 453 208 1893 2 65 12 8 20 5.3 模型一的结果分析 从结果可以看出:几乎所有换乘 2次的线路都可以以较短时间、较低的费用到达目的 站点，说明选择三次作为换乘次数的上限是可行的。 考虑查询系统的时效性，给出MATLAB程序运行时间。由运行时间：查询换乘次数小 于1次含1次的线路，程序运行时间远小于1秒；查询换乘2次程序耗时不超过5秒；查询 换乘3次程序所需时间200秒左右。在实际情况中，乘客在乘车点等车时进行路线查询， 以上查询时间是可以被乘客接受的。以上所述程序运行时间说明在本文描述的数据存储 结构下，改进的邻接算法的可行性与较低的时间复杂度。 综述，模型I求解的线路方案集使用于不同需求下的所有用户，具有较强的实用价值， 很大程度上满足了乘客乘车线路多样化的需求。 6. 问题二的解答 6.1 问题二的分析和求解 问题二与问题一相比，增加了地铁部分，根据附录中相关信息可知，地铁的每一个 站点都有多个公交站点与之对应，两条地铁线路也在两站相交。并且同一地铁站对应的 任意两个公汽站之间可以通过地铁换乘，无需支付地铁费，这样，我们就可以将相邻近 的多个站点（包括地铁站点和公交站点）虚拟成为相同的一个站点，这样就可以将新增 加的两条地铁线等同为增加了两条公共汽车线。然后再次利用模型一对问题进行求解。 注意： �由于无论地铁线路间是否换乘，地铁票价始终为 3元，所以在计算费用时，应特 别注意要单独计算。从进地铁站到出地铁站只需付一次费。 �在计算时间时，由于是将公交车站和地铁站揉和在一起，所以在计算时间时要分 清哪些是乘坐地铁，哪些是乘坐公交，再分别进行计算。 6.2 模型二的建立 对于新站点，可等同看作问题一中的公汽站点，当用户输入起点和终点后，优先显 示直达线路，否则自动搜寻转乘线路，同时，系统向查询者推荐不同目标下的最佳路线 及转乘方案。 考虑乘客可以乘坐地铁，依据问题一中的模型，调整如下： 6.2.1 确定目标函数 目标一：换乘次数最少 根据绝大多数乘客的心理，换乘次数对乘客的选择起决定性的作用，在算法分析中， 我们可以通过搜索直达库，一次中转库，二次中转库来找出所有可行方案，在所有可行 方案中选出换乘次数最少的方案。 根据数据库中的集合表示方式，Ak 表示为第 k辆公交车的路线,有数据库路线可知， 换乘次数为： , k j A A 为地铁站等价的两条新公交路线； G 为换乘次数的可行域。 目标二：时间最短 考虑到是在看奥运的前提下，乘客的时间观念应该较强，所以时间优化也是较为重 要的一点，根据题目假设，相邻地铁站平均行驶时间（包括停站时间）为 2.5 分钟，地 铁换乘地铁平均耗时为 4分钟，地铁换乘公汽平均耗时为 7分钟；公汽换乘地铁平均耗 时为 6分钟；行程时间等于乘车时间与转车时间之和。由此可以确定时间最短的目标函 数为： ( ) ( ), 1α β= × + − ×k j B T length x x n 乘地铁的消耗时间： ( , ) 2.5 7 6 4k j S S B B S S S T length D D S S S− − −= × + × + × + × 1 2 2 2 2 ( ) ( ) ( ) B S x R F x F x MinF T T x ∈ = = + 其中， 1 | ( ) ( ) 0 i i i i i T T R x R F x F x a a−= ∈ ≥ − > 为一容许的宽容限度。 ( )1 1 2 1 1 1 ( ) , ,...., , ( ) ( ) k j x G F x size A A A A F x MinF x ∈ = = length是取两个站点之间相邻公汽站数目， xk —— 表示出发站；λ— 表示相邻公汽站间花费时间：3 分钟； xj —— 表示目的站；β— 表示公交换乘公交花费时间：5 分钟； 目标三：乘车费用 附录一中指出公汽票价分为单一票价与分段计价两种，其中分段计价的票价为： 0～20 站：1元；21～40 站：2元；40 站以上：3元。 由此可以确定目标函数为： 1 2 2 3 3 3 3 ( )= ( ) 3 ( )= ( ) k i P m n k S m E x A x R F x P f x P F x MinF x ∈ ∈ ∈ + + ×∑ ∑ 其中票价为分段函数： 1 1 0 ( ) 20 2 21 ( ) 40( ) 3 ( ) 41 k p k k k length x length x f x length x ≤ ≤⎧ ⎪ ≤ ≤= ⎨ ⎪ ≥⎩ 　 　　 P 1 —— 分段计价的公交车； P 2 —— 单一票价的公交车； P S ——乘坐的地铁次数 2 m P∑ —— 乘坐了m次单一票价车的费用和，每次费用为 1 元； 1 ( )P n k f x∑ —— 乘坐了 n次分段计费车的费用和； 6.2.3 由此可以确定问题二的模型： 综上所述，采用宽容完全分层序列模型建立最优路线选取模型如下： 2 1 1 1 1 3 3 3 2 2 2 ( ) ( ) ( ) ) ( = ( ( ) ) x x G x R R F x MinF x F x F x MinF nF x Mi x ∈ ∈ ∈ = = . . 0 n n x p st n ∈⎧ ⎨ ≥⎩ 其中， G 为换乘次数的可行域， 1 | ( ) ( ) 0 i i i i i T T R x R F x F x a a−= ∈ ≥ − > 为一容 许的宽容限度 模型说明： xk —— 表示出发站；λ— 表示相邻公汽站间花费时间：3 分钟； xj —— 表示目的站；β— 表示公交换乘公交花费时间：5 分钟； 2 m P∑ —— 乘坐了m次单一票价车的费用和，每次费用为 1 元； 1 ( )P n k f x∑ —— 乘坐了 n次分段计费车的费用和； 6.3 问题二的求解 在分析清楚上述问题后，问题二的求解基本和问题一完全一致。通过利用 MATLAB 编程求解可以得到结果如下： 表 5-1 S3359→S1828的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 435 166 1241 32 101 2 时间最少 435 166 1241 32 101 2 费用最少 435 166 1241 32 101 2 表 5-2 S1557→S0481的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 362 416 446 1000020 2424 36 11 5 时间最少 362 416 446 1000020 2424 36 11 5 费用最少 362 416 446 1000020 2424 36 11 5 表 5-3 S0971→S0485的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 12 376 1215 32 86 3 时间最少 12 376 1215 32 86 3 费用最少 12 376 1215 32 86 4 表 5-4 S0008→S0073的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 354 281 1064 26 83 2 时间最少 354 281 1064 26 83 2 费用最少 354 281 1064 26 83 2 表 5-5S0148→S0485 的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 307 155 416 36 3351 35 11 5 时间最少 307 155 416 36 3351 35 11 5 费用最少 307 155 416 36 3351 35 11 5 表 5-6 S0087→S3676的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 D27 直达 10 25 3 时间最少 D28 直达 10 25 3 费用最少 D29 直达 10 25 3 问题二的结果分析： 加入地铁后，乘客有了更多的公交路线选择，可以在换乘两次之内到达任意目的站 点，减少了换乘次数，优化了交通网络。 7. 问题三的解答 7.1 步行时间的分析 问题三是问题二的基础上增加了步行选择，选择步行的主要原因是为了减少换乘次 数和节约费用，但是步行距离会受到一定的限制。 如果出发站点和目的站点足够近，人们一般都会直接步行前往；如果需要乘车，人 们可以走过几个站再搭乘直达车，或者为了减小换乘次数乘车到某站下车后再走到目的 站，也可以先乘车到某站，再走到另一站去转乘直达目的站点的车。但是，人们徒步行 走得时间不可能太长，尤其是在北京 8 月的烈日下。据有关医学调查，人在烈日下平均 连续步行 10 分钟就已经大量出汗，感到不适，所以在此我们设定每次步行时间不得超 过 10分钟。 经过在网上的查寻可以得到，北京市公汽的平均时速为 17 公里，地铁时速为 35 公里，人步行的平均速度为 5.4 公里/小时。按照相邻公汽站平均行驶时间 3 分钟，相 邻地铁站平均行驶 2.5 分钟，一次步行时间不超过 10分钟来计算,得到： 公汽站间距约为 850 米，地铁间距约为 1460 米，一次步行的距离不超过 900 米， 则一次步行只能行走相当于公交车站约一站的距离。 7.2 步行决策的分析 考虑到实际情况，选择步行的原因有两个： 原因一：在顺行方向减少换乘时间； S0 0 2 S0 0 1S0 0 3 图 3-1 红色为出发站，黄色为换乘站 根据 7.1 步行时间的分析，如图所示，存在只坐一站就要换乘的情况；现实生活中 考虑到乘车的花费与等车的时间，这种做法是不合理的；对应在模型中添加决策变量一： ( )( )02 ( , ) 2 10ntime sign length x x= + − × 对应的约束条件为： 00 ( , ) 2nlength x x≤ ≤ 即在只坐一站路的情况下，花费时间改用为步行一站路的时间； 原因二：通过逆行减少换乘时间； S0 0 2 S0 0 1S0 0 3 图 3-2 红色为出发站，黄色为换乘站 考虑到实际情况下存在换行站在出发站的逆行方向，即如果在出发站坐车，单行线 不可能到达换行站，环线线要浪费过多时间；根据 7.1，考虑到实际情况，若换行站离 出发站较近，乘客一般选择通过步行逆行至换行站；对应在模型中添加决策变量二： ( )( )02 ( , ) 10ntime sign length x x= + × 对应的约束条件为： 02 ( , ) 0nlength x x− ≤ ≤ 即在逆行一站路的情况下，若可以找到换乘站，花费时间改用为步行一站路的时间； 7.2 考虑步行决策下的目标函数 目标一：换乘次数最少 根据绝大多数乘客的心理，换乘次数对乘客的选择起决定性的作用，在算法分析中， 我们可以通过搜索直达库，一次中转库，二次中转库来找出所有可行方案，在所有可行 方案中选出换乘次数最少的方案。 根据数据库中的集合表示方式，Ak 表示为第 k辆公交车的路线,有数据库路线可知， 换乘次数为： 考虑到步行情况下可以减少换行次数： 0 0 2 ( , )0 1 2 ( , ) 2i n n length x x length x A x − ≤ ≤ > ⎧ = ⎨ ⎩ 其中 i A 为换乘车辆中 00 ( , ) 2nlength x x≤ ≤ 的车辆；G为换乘次数的可行域。 size 为矩阵中的元素数。 目标二：时间最短 考虑到是在看奥运的前提下，乘客的时间观念应该较强，所以时间优化也是较为重 要的一点，根据题目假设，相邻公汽站平均行驶时间（包括停站时间）为 3分钟，公汽 换乘公汽平均耗时为 5分钟，行程时间等于乘车时间与转车时间之和。同时考虑到步行 的因素，确定时间最短的目标函数为： ( )1 1 2 1 1 1 ( ) , ,...., ( ) ( ) k x G F x size A A A F x MinF x ∈ = = 1 2 2 2 2 ( ) ( ) ( ) S R n x B TF x F x MinF x T T ∈ = = + + 其中 length是取两个站点之间相邻公汽站数目： 1 | ( ) ( ) 0 i i i i i T T R x R F x F x a a−= ∈ ≥ − > 为一容许的宽容限度 xk —— 表示出发站；λ— 表示相邻公汽站间花费时间：3 分钟； xj —— 表示目的站；β— 表示公交换乘公交花费时间：5 分钟； Tn —— 表示对应的第 n次的步行时间：10 分钟/站； 目标三：乘车费用 附录一中指出公汽票价分为单一票价与分段计价两种，其中分段计价的票价为： 0～20 站：1元；21～40 站：2元；40 站以上：3元。 考虑到步行可以减少换乘次数，以此减少车费； 由此可以确定目标函数为： 1 2 2 3 3 3 3 ( )= ( ) 3 ( )= ( ) k i P m n k S m E x A x R F x P f x P F x MinF x ∈ ∈ ∈ + + ×∑ ∑ 其中票价为分段函数： 1 1 0 ( ) 20 2 21 ( ) 40( ) 3 ( ) 41 k p k k k length x length x f x length x ≤ ≤⎧ ⎪ ≤ ≤= ⎨ ⎪ ≥⎩ 　 　　 其中判定是否步行的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ： 0 0 2 ( , )0 1 2 ( , ) 2i n n length x x length x A x − ≤ ≤ > ⎧ = ⎨ ⎩ P 1 —— 分段计价的公交车； P2 —— 单一票价的公交车； 2 m P∑ —— 乘坐了m次单一票价车的费用和，每次费用为 1 元； 1 ( )P n k f x∑ —— 乘坐了 n次分段计费车的费用和； ； 7.1.3 由此可以确定问题三的模型： 在问题分析中，根据调查可知乘客对五种目标的需求程度优先顺序为： > > > >换乘次数 时间 花费 车载压力 乘车压力 综上所述，采用多目标分层整数规划法建立最优路线选取模型： 2 1 1 1 1 3 3 3 2 2 2 ( ) ( ) ( ) ) ( = ( ( ) ) x x G x R R F x MinF x F x F x MinF nF x Mi x ∈ ∈ ∈ = = . . 0 n n x p st n ∈⎧ ⎨ ≥⎩ 其中， G 为换乘次数的可行域， 1 | ( ) ( ) 0 i i i i i T T R x R F x F x a a−= ∈ ≥ − > 为一容 许的宽容限度 模型说明： xk —— 表示出发站；λ— 表示相邻公汽站间花费时间：3 分钟； xj —— 表示目的站；β— 表示公交换乘公交花费时间：5 分钟； 2 m P∑ —— 乘坐了m次单一票价车的费用和，每次费用为 1 元； 1 ( )P n k f x∑ —— 乘坐了 n次分段计费车的费用和； 7.2 模型三的求解（程序详解附录三） 7.2.1 求解过程 蚁群算法背景介绍 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻 找优化路径的机率型算法。它由 Marco Dorigo 于 1992 年在他的博士论文中提出，其灵 感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法 ,初步 的研究表明该算法具有许多优良的性质.针对PID控制器 参数 转速和进给参数表a氧化沟运行参数高温蒸汽处理医疗废物pid参数自整定算法口腔医院集中消毒供应 优化设计问题,将蚁群算法 设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种 新的模拟进化优化方法的有效性和应用价值。 其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种 群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递， 搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间 的相似性。得到了具有 NP 难度的旅行商问题的最优解答。同时，该算法还被用于 求解 Job-Shop 调度问题、二次指派问题以及多维背包问题等，显示了其适用于组 合优化类问题求解的优越特征。。 基于数据库的蚁群算法 采用蚁群算法进行遍历搜索可以很大程度上减少运算时间，我们再已有数据库的基 础上，构造邻接矩阵，采用蚁群算法求解遍历下的较优解问题。 算法流程图： 7.2.2 编程实现求解 依据确定的模型的目标函数及其约束条件，借助 MATLAB 编程（具体程序见附录）求 解得到如下结果： 表 5-1 S3359→S1828的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 435 步行 1241 31 108 1 时间最少 435 步行 1241 31 108 1 费用最少 435 步行 1241 31 108 1 表 5-2 S1557→S0481的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 362 416 446 1000020 2424 36 11 5 时间最少 362 416 446 1000020 2424 36 11 5 费用最少 362 416 446 1000020 2424 36 11 5 表 5-3 S0971→S0485的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 12 步行 1215 31 90.5 3 时间最少 12 步行 1215 31 90.5 3 费用最少 12 步行 1215 31 90.5 3 表 5-4 S0008→S0073的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 156 步行 3053 26 90.5 4 时间最少 462 169 2083 28 89 2 费用最少 462 169 2083 28 89 2 表 5-5S0148→S0485 的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 307 155 416 36 3351 35 11 5 时间最少 307 155 416 36 3351 35 11 5 费用最少 307 155 416 36 3351 35 11 5 表 5-6 S0087→S3676的路线选择 起始线路 转乘线路一 转乘线路 二 转站点 1 转站点 2 总站数 时间 费用 站数最少 D27 直达 10 25 3 时间最少 D28 直达 10 25 3 费用最少 D29 直达 10 25 3 8. 模型的评价、改进及推广 8.1 模型评价 优点： ①通过对问题的充分分析，把同一车次行驶方向独立成上下行路线，有效的解决了 公交车的往返路线不同的问题，并且极大地提高了整体查询的准确性。 ②分析公交线路信息建立可行路线算法的时候，巧妙的借鉴了“求交集”的思想， 创造出一种高效快速的可行路线查询方法。 ③对多目标规划问题，采用宽容完全分层序列算法，避开了时间和价格的权数比不 明确的问题。得出的结果更具有合理性。 ④在解决问题三时采用了蚁群算法，蚁群算法作为一种高级算法，在处理遍历问题 上具有很大的优势。 缺点： ①用“宽容分层序列法”求解最短路线时，缺乏确切的乘客查询路线时的选择数据， 不能具体给出三目标之间的权重系数。故模型的结果只是定性分析的结果，但是考虑到 一般乘客心理因