2007国赛B题特等奖论文.docVIP

公交查询系统的最佳乘车方案研究与设计 【摘要】 本文将站点实体间的线路选择抽象为图论最短路模型采用 整数规划表述。建立直达数据库 作为数据基库，根据用户需求建立不同目标的 规划模型运用邻接算法与 分别求解，最终方案集通过多目标分层序列排序输出到用户终端。 第一问，在数据处理阶段将直行、环行线路分别抽象为 2、4 条路线(见 5.0)。建立查询系统时考虑服务器要同时响应多个请求，计算任务繁重，采用空间换取时间的策略，先建立站点至站点直达数据库来描述两两可直达站点的所有线路，用户查询时，系统首先查询，得到所有直达车方案。 在没有直达车情况下，针对不同用户需求，目标考虑：转乘次数、总耗时、总费用、转站车辆是否始发、转乘站点负载量；在 的基础上，量化不同目标为有向赋权图的不同权矩阵(见 5.2.0)，以所求顶点到顶点的路径是否包含 弧为决策变量，上述 5 项用户需求为目标，始、终点连通为约束建立 整数线性规划模型(见 5.2.3模型Ⅰ)。 为了能够为用户提供多种备选方案， 我们首先使用基于的邻接算法求解，得到不同目标下的多种优化方案；对于邻接算法不易求解的多次转乘最优方案，我们采用软件直接求得全局最优解； 两种方法求解步骤见(5.3.1)， 综合方案集见(5.3.2表 1.1~1.6)，其中 6 条线路时间最短目标分别为 67、102、106、62、105、49(分钟)；两种求解方法的优劣在 5.4 中给出了详细评价。 第二问考虑公汽与地铁混排方案，首先把各地铁站点和周围的公共汽车站点集抽象为同一新站点，把已知公汽线路到达都映射到，计算新直达数据库，再结合地铁的费用与地汽换乘等待时间就可以把地铁线与公汽线结合，建立多目标整数线性规划模型(见 6.2.3 模型Ⅱ)；对于转乘次数少于等于2次的方案任可以通过邻接算法求解；对于邻接算法不易求解的多次转乘优化方案，虽然模型规模较大但约束与目标线性程度较好，还可用软件求解得出6跳线路的全局最优解；综合方案集(见 6.3.2 表 2.1~2.6)，， 其中6 条线路时间最短目标分别为 65、102、98、56.5、89.5、30(分钟)；随后我们在6.4与6.5中给出了模型具体的评价与应用。 第三问综合考虑所有站点间步行与乘车情况，将其抽象为最短路问题下的叠加有向赋权图，在此基础上以换乘次数为主要约束，以总行程时间(包括步行)最短、转站车辆始发数最大、转乘站点负载量最小、费用最低为目标，建立多目标 整数线性规划模型(见 7.3 模型Ⅲ)，并给出了求解的一般步骤与算法。 最后本文还对实现查询系统的具体方案给出了建议，对各模型在实际中的应用价值进行了详细讨论，并提出了改进方案。 关键字： 邻接算法 有向赋权图 直达队列表 分层序列法 叠加有向赋权图 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 问题分析 本题主要在三种不同情况下，研究任意两站点之间的线路选择问题。联系实际，公众乘坐公交车主要考虑的因素包括转乘次数、行程时间、车站始发情况、车站的车次负载量及乘车费用等因素。为满足一般公众的乘车需求，主要按照公众对不同乘车信息的重视程度，确定出最佳的乘车路线。 仅考虑公汽线路的情况下，首先，需要根据题目给出的公交线路信息数据，对每条线路进行抽象处理，将分上下行的线路、双向行驶的线路和环行线路抽象为两条。然后，主要考虑公众最关心的乘车因素，即转乘次数。在最少转乘次数的基础上考虑共众对其他因素的需求，按照先后顺序考虑行程时间、车站始发情况、车站的车次负载量及乘车费用，给出供公众选用的多种参考