基于双向广度优先搜索的公交线路优化模型 论文.pdf

华中科技大学 2007CUMCM 获奖论文 基于双向广度优先搜索的公交线路优化模型 摘 要 对于公交线路的优化模型，要求从实际情况出发，根据查询者的不同需求，给出相 应的最优模型。在建模时，首先应考虑到乘客转乘车的次数问题，同时也是关于时间、 费用的多目标动态规划问题。由于在考虑因素的多少上是逐渐增加的，所以我们用三个 模型来回答题目中所提到的三个问题。 对于问题一，利用图论的方法，建立了多目标优化模型，利用双向广度优先搜索的 算法，通过 C语言编程，求出题目要求六组起始站与终到站的最佳线路，其中，花费的 时间与费用如下表： 组号  1  2  3  4  5  6  时间  63  106  128  106  83  106  65  46  费用  3  3  2  3  2  3  2  3  对于问题二，在问题一的基础上，增加了地铁因素，其模型与模型一类似，同样利 用图论方法，与问题一中的区别只是将与地铁相连的站点当作一个新的大站点，在原来 的算法上稍做修改，得到经过地铁的六组起始站与终到站的最佳线路，其中，花费的时 间与费用如下表： 组号  1  2  3  4  5  6  时间  63  106  128  106  96  83  65.5  106  87.5  65  25  费用  3  3  2  3  5  2  5  3  5  2  3  对于问题三， 在模型二的基础上，增加了乘客步行的因素。考虑到步行的目的是为 了减少换乘车的次数，同样有时间、费用两个目标，建立了如下的数学模型：  F = min{f(P)}  1 i  i  .  F = min{t(P)} 2 i  i  关键词：双向广度优先搜索 最佳路径 多目标动态规划 最优化模型 刘建平 廖慧 潘恩伦，指导教师：韩志斌  1  华中科技大学 2007CUMCM 获奖论文 1  问题分析 1.1 目标分析 本题中，有公交线路 520余条，地铁线路 2 条，总共有 522条线路。对于任意两个 站点，如何合理的选择线路，使得乘客能够根据自己的需求或偏好达到自身的效用最大 化。在本题中，将现实情况合理的简化，忽略掉一些突发的意外事件 （比如堵车、道路 维修的问题），采用与乘客联系最紧密的量（如费用、耗时等）来衡量乘客的效用。 1.2 与乘客的效用相关的三个量  1  费用 一般而言,费用是与乘客的效用联系相当紧密的。但公交是一个相当经济、大众化 的交通工具,每次乘公交车，所花费的费用也并不是很多。  2  耗时 “时间就是金钱,时间就是效率” 。在当今社会，时间越来越被看重，时间的价值也 在不断升值。因此，若能够多花费少许公交费用而节约相对更多的时间，一般而言,人们 都是愿意的。  3  换车次数