1、毕业设计开题报告 计算机科学与技术 城市公交换乘指南系统设计 一、 选题的背景、意义 1.选题的背景 我国经济的持续发展必然加快城市化、机动化速度，更何况我国城市化水平本来就低于相应的经济发展水平。汽车进入家庭、城市扩张可能带来的郊区化趋势，与城市化一起成为21 世纪我国城市交通发展的大背景。我国私人汽车的迅速发展给城市交通系统带来了严重的影响。如何考虑私人小汽车和公共交通系统的竞争关系并建立一个有竞争力的公共交通系统；如何选择交通政策等，都影响这个城市的交通模式、城市建设。 城市的各种交通政策的选择和实施必须考虑 城市的特性和资源、代价和效果。因此有必要在可持续发展的目标下，借鉴国外城市的成
2、功经验和失败教训，重新检查城市交通系统的规划和建设，从而充分利用有限的交通资源，体现“无缝接驳”的人性化理念 1。目前乘客可以获得的公交信息很少，而且方式主要是常规手段。我国乘客一般获得公交信息的方式局限与电话，交通地图，向他人问询等常规方式。 2.选题的意义 关于共交线路中最优线路得查询算法有很多文献都作了讨论 ,如文献 2-4,还有专门讨论针对换乘次数最少的线路查找算法 5;以及文献 6等都对公交线路中最优线路的 查询算法。作研究 .城市交通的换乘方式主要有停车场换乘和乘车换乘两种。停车场换乘也叫存车换乘， 是指将自备车存放后， 改乘公共交通工具到达目的地的交通方式；乘车换乘是指从一种公共
3、交通工具或一条线路，转换到另一种公共交通工具或另一条线路上的换乘方式， 这是一种前后衔接的连续转乘方式 7。下面通过以下两点说明公交换乘系统的必要性和重要性： .以百万人口占地一百平方公里的城市为例，若每平方公里划分一个交通小区，其各点均直接联系需要 4 950条线路，显然，这既无可能也无必要，必须用换乘的方式来解决 8；如果采用不同 的交通工具，换乘更是大量存在。 公交以其覆盖面广、经济快捷的特点，目前仍然是绝大数出行者的首选方式。 我国实施城市的可持续发展之路，当然包括城市交通的可持续发展。所以大力倡导改善客运结构，大力发展公共交通乃当务之急 。 二、 研究的基本内容与拟解决的主要问题 1
4、. 研究的基本内容 本设计将研究实现公交查询系统换乘查询时，在知道每条公交线上的站点的基础上 ,首先以换乘次数最少作为最优标准 ,当换乘次数相同时再以站点数最少为最优标准 ,用集合的方法给出了任意两站点之间的最优公交线路的查询算法，并给出了选择换乘次数多 ,但站点数少的公交 线路的条件 4。 2. 要解决的主要问题 1)前期掌握理解该设计中用到的算法思想。 2)熟练掌握有关在设计总需要用到的开发环境和软件工具。 3)基于 Web 环境，为某一城市公交出行者提供换乘线路选择，设计出良好的人机查询交互界面。 4)优先基于换乘次数最少的公交换乘线路实现公交出行者换乘线路的优化，力求达到换乘次数最少和
5、乘车站点总数最少的双目标优化。 三、 研究的方法与技术路线、研究难点，预期达到的目标 1. 研究的方法与技术路线 算法思想 设要查询从 SA 站点到 SB 站点的最优线路 .设 SA 的后续线路有 m1 条 , 分别为La1,La2Lam.设 SB 前续线路有 m2 条 ,分别为 Lb1,Lb2,Lbn。 取 SA 的后续线路与 SB 前续线路分别作交得 Z，令 Z0 = 所有 Zij 的并 ;当 SA , SB 包含在 Z0 中时 ,说明 SA 到 SB 有直达的线路；当 SA , SB 不包含在 Z0 中且 Z0 非空时 ,则 SA 到SB 没有直达的线路 ,至少需换一次车 ,而 Z0 中
6、的元素为可换车的站点。 分别取这些站点连接 SA 和 SB , 得多条 SA 到 SB 需转一次车的线路 ,比较这些线路上的站点数可得最优线路。 当 Z0 为空时 ,用不经过 SA 和 SB 的各条公交线路 (记为 Lq， q=1,2,)与 SA 的所有后继线路作交 . 取 Lq 中与 SA 的后续线路交为非空的线路 Lp,(p=1,2,3),得 Lp 上的站点 St , St 的前续线路与 SA 的后续线路交集减去 St 为空 . 此时 ,取 St 在线路 Lp 上的后续线路 Ls 与 SB 的各前续线路取交 .。 若交集不空 (存在 S t 属于此交集 ) ,则知从 SA 到 SB 至少需
7、换两次车 ,且换车的两个站点先后分别为 St 和 S若各 St 在线路 Lp 上的后续线路 Ls 与 SB 的各前续线路交为空时 ,则取Lp ( p= 1, 2, )与 SB 的各前续线路交作交 ;其中与 SB 的前续线路交非空的线路记为 Lq, 得 Lq上的站点 Sr , Sr 的后续线路与 SB 的前继线路交集减 Sr 为空 . 取 Sr 在 Lp 上的前续线 Lq 与St 在线路 Lp 上的后续线路 Ls 取交 . 若交集非空 ,则得到多条从 SA 到 SB 至少需换三次车的线路和各条线路上的三个换车站点 , 将它们比较可的换车次数为三的最优线路 . 若交集为空 ,则表明 SA 到 SB
8、 至少需换四次车。 重复以上过程 ,可找出需换四次 ,五次及换更多次车的线路。以上是以换车次数最少为标准的最 优线路查询算法， 但在实际中会出现换车次数多的线路上的站点数比换车次数少的线路上的站点数少，这时乘客会考虑以换车次数的线路作为最优线路。 下面给出这种选择的条件。 设 k1、 k2 分别为从 SA 到 SB 最少需要的换车次数和从 SA 到 SB 可达线路上的换车次数 , 显然 k2 k1 ;若换车次数为 k1 时的各线路的站点集为 Lk11 , , Lk1v(包含 SA 和 SB ) , 记 nk1 = min |Lk11 | , , | Lk1v | ; 换车次数为 k2 的各线路
9、的站点集为 Lk21 , Lk2u ,记nk2=min |Lk21 | , , |Lk2v | ; 所以 ,当 ( nk1 - 1) T间 + k1 T转 ( nk2 - 1) T间 + k2 T转时乘客会以换车次数为 k2 的线路作为最优线路 ,即 nk1 - nk2 T转 /T间 ( k2 - k1 ) 当在第 2部分的算法中加进以上条件时 ,则可在换乘次数和节省时间 (站点数少 )的平衡上选取出最优线路。 2. 研究难点 已知公交网络的邻接矩阵或已有公交地图 ,来查询最优的线路。这种查询系统 ,首先得存储整个公交线路网络 ,然后 ,利用网络分析得算法 ,如 Dijkstra 算法 11、
10、 Floyd 算法 12等来实现 . 在网络规模较小的情形下 ,这是十分有效的 . 但是 ,当公交网络中的结点 (站点 )增多和网络变得复杂时 ,公交线路网络的存储和网络分析算法中计算量增大的问题就会变得突出。本文在仅知道每条公交线路上的站点和顺序的条件下 ,通过集合的方法来设计最优公交线路查询算法 ,为公交系统最优线路查询系统设计提供了新的思路和方法。 3. 预期达到的目标 本毕业设计将实现基于 Web 的城市公交换乘指南系统设计，具体实现以下功能：根据某一城市既有公交网络，为公交出行者提供换乘线路选择。公交换乘问 题是多目标优化问题，需要同时满足两个或者多个目标要求以达到高效换乘的目标。本
11、设计要求建立城市公交网络多目标优化模型，首先基于换乘次数最少的公交线路，在此基础上建立换乘次数最少和乘车站点总数最少的双目标优化模型。 四、论文详细工作进度和安排 计划进度： 第七学期第 10周至第 18周（ 2011年 01月 06日前）：文献检索和资料收集，完成毕业论文（设计）文献综述、开题报告和外文翻译； 第八学期 第 1周 至第 3周（ 2011年 03月 11日前）：撰写论文提纲，完成毕业论文（设计）初稿、需求分析和概要设计； 第八学期 第 4周 至第 12周（ 2011年 05月 13日前）：详细设计、系统调试、和毕业论文（设计）完成定稿； 第八学期第 13周（ 2011年 05月
12、 20日前）：完成应用软件系统的设计和毕业论文（设计）送指导老师和评阅老师评阅，准备答辩； 第八学期第 14 周：参加毕业论文（设计）答辩。 五、主要参考文献： 1 关志宏， 刘小明 . 停车场规划设计与管理 M. 北京： 人民交通出版社， 2003. 2李玉芝 ,方源敏 . 城市公交查询系统的设计与实现 J . 地矿测 绘 , 2006, 22 (1) : 3 - 5. 3王 朝晖 ,杨洁 . 公交线路中最优路线的查询算法设计 C . 2005 数字江苏论坛 电子政务与地理信息技术论文专辑 : 149 - 152. 4郭建东 . 公交网络线路查询算法的设计与实现 J . 福建电脑 , 200
13、6 (3) : 114 - 115. 5傅冬绵 . 交通系统中最少换乘算法及其实现 J . 华侨大学学报 (自然科学版 ) , 2001, 22 (4) : 348 - 350. 6周培德 . 交通道路网中任意两点之间最短路径的快速算法 J . 计算机工程与科学 , 2002, 24 (4) : 35 - 37. 7 陆化普 . 交通规划理论与方法 M. 北京 ： 清华大学出版社 ， 1998. 8 陆锡明 . 综合交通规划 M.上海 ： 同济大学出版社 ， 1999. 9 谢润，何昌莲，张森 .基于换乘次数最少的公交线路查询算法 J.宜宾学院学报， 2008，6（ 6）： 18-19 10
14、Yongjie Ma*, Ye Tian, and Wenjing Hou. Dynamic Path Optimization of Emergency Transport Based on Hierarchical Genetic AlgorithmJ.2008,7(10):18-20. 11 Yu-Hsin Liu. A genetic local search algorithm with a thresholdaccepting mechanism for solving the runway dependent aircraft landing problem. Comput. Oper. Res. 31, 2199 2213 (2004)
