基于android的成市道路交道最优路径方法研究开题报告

1. 研究目的与意义（文献综述）

当今21世纪，信息技术迅猛发展，并被不断地应用到了生活的方方面面中，带动了各行业技术的进步，给我们的生活方式，生活质量带来了日新月异的变化。

在城市中，道路交道错综复杂，要从城市的这一端到另一端需要七拐八拐，即使再熟悉道路的人也总有不知道走哪一条路的时候。如果走错了路，既浪费了时间，又增加了出行成本。而一个基于android的地图导航系统可以有效解决这个问题，只要用你的手机下载这样的一个app，你只需输入你的起始位置和目的地，就可以轻松地得到正确的路线。为了实现这样方便的功能，就需要找出一种合适的算法来计算出最优路径。然而传统的最优路径算法如dijkstra算法，floyd算法等都是在静态网络下求解最短路径的算法，其约束条件只是各顶点之间的距离。但城市交通网络是复杂的、时刻变化的，结点数目比较多而且结点之间包含的信息不再是单一的、确定的，并且无法提前预知。距离并不是唯一的约束条件，时间，红绿灯数，拥堵程度等都会对用户的选择造成影响。用户想要的是综合考虑多种交通信息后得到的最优路径。蚁群算法可以解决这个问题。蚁群算法是一种新兴的仿生模拟算法，它受蚁群觅食行为启发而产生。人工智能的先去minsky说过“我们应该从生物学而不是物理学得到启示。”蚁群在觅食过程中总能找到一条从蚁巢到食物源的最短路径。受其启发，意大利学者m.dorigo，v.maniezzo和a.colorni于20世纪90年代初提出了一种新型的智能优化算法——蚂蚁系统（antsystem，简称as）。近几年，蚂蚁算法被进一步优化为一种通用的优化即使——蚁群优化（antcolonyoptimization,简称aco）。该算法受到了世界上许多国家的研究者的关注，并被应用到各个领域中。目前该算法已被广泛应用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题中。在交通道路的最优路径算法中，蚁群算法也可以起到很不错的作用。然而交通中通常结点比较多，要计算的因素也较多较复杂，如果直接将蚁群算法用于交通中求解多个约束条件下的最优路径会有以下问题：

(1)效率低：本身蚁群算法的搜索时间就比较长，现在在多个约束条件下，计算量就更加大了。蚂蚁本身是按照转移规则进行选择，转移规则又是按照信息素来计算的。当问题规模较大时，结点之间信息素的计算需要较长的时间，如果蚂蚁数量较多，更会加大算法的运行时间，造成效率很低。

2. 研究的基本内容与方案

2.1基本内容

（1）对现有的最短路径算法进行分析

从最优路径以及蚁群算法的研究现状出发，分析了现有研究中存在的问题；描述最优路径问题以及多约束最优路径的模型；研究分析传统最优路径算法的特点及使用范围。

3. 研究计划与安排

(1)2016/1/11—2016/1/22：查阅参考文献，明确选题；

(2)2016/1/23—2016/3/7：进一步阅读文献，并分析和总结；确定技术路线，完成并提交开题报告；

(3)2016/3/8—2016/4/26：需求分析，算法或系统设计，分析、比较或实现等；(4)2016/4/27—2016/5/27：撰写论文初稿；修改论文，定稿并提交论文评审；(5)2016/5/28—2016/6/7：准备论文答辩。

4. 参考文献（12篇以上）

【1】李刚.《疯狂java讲义（第3版）》.电子工业出版社.2014

【2】李刚.《疯狂android讲义（第2版）》.电子工业出版社.2013

【3】郭金尚.《android经典项目案例开发实战宝典》.清华大学出版社,2013