[基础科学]2007数模竞赛B题_城市公交线路选择优化模型论文.doc

城市公交线路优化模型 摘　要 本文针对城市公交线路选择问题建立了两个模型，一个是基于集合寻线算法模型，另一个是图论模型。 基于集合寻线算法模型中，首先固定换乘次数，通过集合论的相关知识把确定换乘点的具体位置, 转化成确定一些集合间的交集，从而建立集合寻线算法，再根据集合相关公式，得到所有可行线路；进一步考虑时间和费用等因素，对可行线路进行处理比较，得出最佳线路。 图论模型中，通过图论的知识将整个北京市交通线路构建出一个有向图，每个站点与有向图的顶点一一对应，同一线路上的相邻站点对应为有向边，通过不同目标（时间、费用）给有向图进行不同的赋权，分别将不同目标转化为赋权有向图寻找最短有向路，根据最短路径算法，得到最佳线路。最后综合评价了两个模型的优缺点。 关键词：集合寻线算法；最短路算法；换乘点；赋权有向图 1 问题提出 北京将于2008年举行奥运会，届时会有从四面八方而来观看奥运比赛观众，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。随着现代化的步伐加快，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。在现实生活中，公交线路以及其相应经过的站点非常多且密，乘客往往难以知道如何选择公交线路，所以针对市场需求以及公交线路选择上的问题，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。 该系统的核心在于线路选择的模型与算法，应该从实际情况出发，满足查询者的各种不同需求。根据附录1、附录2，解决如下问题： 1.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用建立的模型与算法，求出以下6对起始站→终到站之间的最佳线路。 (1) S3359→S1828 (2) S1557→S0481 (3) S0971→S0485 (4) S0008→S0073 (5) S0148→S0485 (6) S0087→S3676 2.同时考虑公汽与地铁线路，解决以上问题。 3.假设知道所有站点之间步行时间，给出任意两站点之间线路选择的数学模型。 2 问题分析 为了研制开发一个解决公交线路最佳选择（即乘客在多条公交线路中根据自己的需求获得最适合自己的线路）问题的自主查询计算机系统，只要乘客给出起点站和终点站两个站点，系统就给出最佳交通线路，使得公众出行更加通畅、便利。而问题核心是如何在多条线路选择中获得最佳线路。 乘客往往不能只乘一辆公交便直达终点，而是要通过换乘一辆或多辆公交才能到达终点站，但若多次换乘公交，可能导致乘客所花时间及其费用的增加，更会给乘客造成不便。在奥运将在北京举行的背景下，我们知道乘客前往观看奥运比赛时，主要注重的是能否及时到达，所以在为乘客选择线路时，力求乘坐花费的时间尽可能少以及路程尽可能短的线路，同时考虑换乘车辆以及乘车费用尽量少的最佳线路，而现实是很难同时满足上面三个目标的。为了使问题简单化， 我们分别以乘车时间、乘车费用以及换乘次数为目标函数，得到各自的较优线路，再通过对比，有效地处理这些线路，最终得出查询系统给出的结果。 3 模型准备 3.1 模型假设 1.假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘（无需支付地铁费）； 2.假设所有交通线路都不出现停运或者线路变动； 3.假设公汽的环行行驶线路是单向的。 3.2 符号约定 ：相邻公汽站平均行驶时间（包括停站时间），； ：相邻地铁站平均行驶时间（包括停站时间），； ：公汽换乘公汽平均耗时，（其中步行时间2）； ：地铁换乘地铁平均耗时，（其中步行时间2）； ：地铁换乘公汽平均耗时，（其中步行时间4）； ：公汽换乘地铁平均耗时，（其中步行时间4）； ：交通工具与交通工具换乘所需时间； ：地铁票价，元； ：换乘次数； ：乘客在可选择的从起始站到终点站线路中第条线路的换乘点（包括始点和终点），，为起点，为终点； ：乘客从第换乘点上车到第换乘点的下车所付的票价，； ：公交车从第换乘点到第换乘点经过的站点数（含第换乘点）； ：公交车在第线路上从第换乘点到第换乘点线路； ：公交车在第线路上从第换乘点到第换乘点经过每站所需时间； ：只换乘次乘客从起始站到终点站选择第条线路所需要的总时间； ：只换乘次乘客从起始站到终点站选择第条线路所需要的总费用。 4 基于集合寻线算法的模型 4.1 集合寻线算法的建立 现实乘客换乘的次数很小，公司在设计一个城市公交线路时，为了使线路更合理，一般不会使乘客要通过多次换乘（超过3次）才到达终点站。则不妨假设换乘次数，。 我们可以看到问题中关键要解决的是找出换乘点的具体位置，显然换乘点是公交线路的交叉点，或者说站点至少要有两条公交线路经过。由于公交线路不是一条直线段或者