摘 要

本文针对移动端路径规划展开研究，首先介绍了移动端路径规划的迅猛发展，指出移动端路径规划成为移动通讯领域研究的一大热点。然后对研究中使用到的Android系统、百度地图、GPS等相关技术进行了研究，详细介绍了Android系统架构和调用API接口的功能和实现方法，并了解了路径规划算法的发展现状及评估情况。接下来是定位功能和路径规划功能的实现。

本文主要是在Android Studio平台上利用百度地图开发套件（主要包括Android定位SDK）以及ADT（Android Developer Kit）等工具，并主要使用Java语言编写Android应用程序，通过编译在手机上实现安装该程序作为客户端，接收实时的GPS信号实现定位功能，并在此基础上实现路径规划的功能。最后对该软件在Android系统中进行了测试和评估，并对离线情景下路径规划提出了自己的思考。

关键词：Android；路径规划；定位服务；百度地图

Abstract

This paper studies the path planning of mobile terminal, firstly introduces the rapid development of the path planning of mobile terminal, and points out that the path planning of mobile terminal has become a hot topic in the field of mobile communication. Then, the Android system, baidu map, GPS and other related technologies used in the study are studied, and the Android system architecture and the function and implementation method of calling API interface are introduced in detail, and the development status and evaluation situation of path planning algorithm are understood. Next is the implementation of location function and path planning function.

This paper mainly uses Baidu Map Development kit (mainly including Android Location SDK) and ADT (Android Developer Kit) on Android Studio platform, and uses Java language to write Android application program. After compiling, the program is installed on the mobile phone as a client, receiving real-time GPS signal to realize positioning function, and on this basis, the path planning function is realized. Finally, the test and evaluation results of the software in Android system are presented.

Key Words：Android；path planning；location-based services；Baidu Map

目录

第1章 绪论 3

1.1 研究背景及意义 3

1.2 研究现状综述 4

1.2.1 关于最短路径算法的研究现状 4

1.2.2 关于移动端路径规划的研究现状 5

1.3 研究目标与研究内容 6

1.4 论文章节安排 6

第2章 关于系统相关技术的研究 7

2.1 Android系统简介 7

2.1.1 Android系统概述 7

2.1.2 Android 平台构架 7

2.2 百度地图 9

2.3 GPS 10

2.4 百度API接口类的介绍 12

第3章 关于最短路径算法的研究 15

3.1 Cherkassky等人对最短路径算法的评估 15

3.2 Zhan和Noon对最短路径算法的评估 15

3.3现实道路网络中最快的三种算法 17

3.4 百度地图所使用的最短路径算法 17

第4章 系统的设计、实现与测试 19

4.1 开发环境搭建和资源配置 19

4.1.1 开发工具的选择 19

4.1.2 百度地图API的配置 19

4.2 系统主要功能的实现 21

4.2.1 添加API Key及用户权限配置 21

4.2.2 定位功能的实现 22

4.2.3 路径规划功能的实现 23

4.3 系统功能测试 24

4.3.1 系统测试环境 25

4.3.2 系统测试过程 25

4.4 关于离线路径规划的思考 27

第5章 总结和展望 29

5.1 全文总结 29

5.2 后续工作展望 29

参考文献 31

致 谢 32

第1章 绪论

移动网络技术的快速发展，加上路径规划需求的广泛性，使得路径规划大量应用于人们的日常生活中。较为成熟的算法最早见于上世纪50年代，其中一些直至今日仍被广泛应用。随着运输规模和出行需求的大幅增加，对于路线规划的新需要一直出现，最典型需求的就是移动端的路径规划。路网规模迅速增长，效率低下仍是现阶段最短路径规划中的突出问题，一些对时间节点较为敏感的路径规划仍有待改进以期提高查询的效率。

随着GIS技术的进步和高质量路网数据的可用性，在GIS环境下对大地理区域进行路径分析具有了可操作性。移动端设备和云端的便捷通信，也使得极端情况下要求实时完成的路径分析成为可能。本章首先介绍移动端最短路径规划的研究背景及意义，然后对现状与当前问题进行分析，并给出解题的思路。

1.1 研究背景及意义

互联网技术的飞速发展，催生了大量的基于定位的服务。同时，计算机技术也使得存储和处理大量的路网数据成为可能。移动网络技术的快速发展使得智能手持设备无处不在。内置多个传感器的联网智能手机的发展，可以用来集体检索和贡献环境信息如交通拥挤。除此以外，室内定位技术的提高，如Wi-Fi、iBeacon定位等，使得室内定位和引导更加容易实现。

图1.1展示了中国手机地图市场用户规模的发展趋势，截止2017年6月，我国手机端电子地图用户累计规模达到了惊人的6.86亿人且还在不断增长。图1.2展示了全球范围内电子地图2014-2019年的市场规模趋势，预计2019年末，全球移动端电子地图市场规模将增长至44.8亿美元，年均复合增长率为11.07%^[1]。

图1.1 中国手机地图市场用户规模

手机地图采用4G或Wifi进行通信，并且智能手机的便携性和实时数据交换性，轻松打破了地理环境造成的局限性，给人们的出行活动带来了很大便利。因此，手机导航软件的设计成了当今移动端软件开发的一大热点^[2]。

图1.2 全球电子地图市场规模

1.2 研究现状综述

1.2.1 关于最短路径算法的研究现状

对路径规划算法的研讨可追溯到上世纪50年代，它起源于图论中一些数学游戏引发的思考。解决这一问题的基本思想和详细算法流程，在1959年由荷兰科学家Dijkstra在前人广泛研究的基础上提出，即著名的Dijkstra算法^[3]。主要目的是处理一定点到其他定点之间的路线规划问题。

现有的最短路径规划问题可根据固定点个数大致分为两定点之间路径规划问题、单定点路径规划问题、多对多最短路径规划和全标记点最短路径规划问题^[4]。两定点之间最短路径规划是当前最为热门的研究分支之一，根据不同的搜索查询策略^[5]，大致可以分为经典类、引导类、分层类和组合类几种^[6]，如图1.3所示。

图1.3 最短路径算法分类

1.2.2 关于移动端路径规划的研究现状

高德和百度是国内两家较为成功的能够提供电子地图路径规划服务的公司，所提供的服务也相对完善，包括POI检索、实时定位、路线规划乃至天气预提醒服务等等。

2005年百度公司推出了百度地图电脑版^[7]，2010年百度以不收费服务形式开放了百度地图API接口，2011年4月百度地图发布了Android版本，至此移动端路径规划搭乘智能手机的快车进入了家家户户。从用户使用量和覆盖范围（据统计已经覆盖了全球200多个国家和地区）两个方面来看，百度地图都是该领域的领军企业。

高德地图是由高德公司主导开发的电子地图，因其精度高，响应快，路径规划清晰的突出特点而广受好评,2010年高德登陆纳斯达克全球精品市场^[8]。另外，腾讯^[9]、搜狗^[10]等公司也推出了各自的移动端地图。

伴随着移动通信技术的发展，人们对智能出行等方面的要求也变得更高，定位服务和互联网的结合将会是一个主流的发展方向，网络技术的发展将会推动移动地图服务进一步完善。

1.3 研究目标与研究内容

综合分析移动端路线规划软件，以研究Android系统架构和最短路径算法为基础，实现手机端基础地图浏览功能，在其基础上完成最短路径查询。通过编译后以软件的形式在Android手机上进行实体安装测试，并实现拥有放大缩小地图、平移浏览地图、实时定位、查询目标地点、路径规划等功能。

围绕上述所提出的目标，拟开展以下几方面的工作：

1. 对Android系统架构进行学习。首先对Android系统的开发环境、基本控件进行了解，其次，对监听、回调等事件的处理进行学习，并掌握地图调用的方法；
2. 对最短路径规划算法进行学习。了解各种算法的优缺点，理解算法改进的出发点和着手点，尝试进行算法的比较；
3. 综合上述两点，在移动端实现任务要求所提到的基本功能。

1.4 论文章节安排

本论文围绕移动端最短路径的查询及其实现展开研究，本论文共由5 章组成，各章节的研究思路安排如下：

第一章：绪论。该章简述了本课题的研究背景和意义，对本课题的研究发展现状进行分析，掌握最新研究方向和研究思路。对要实现目标所需的知识体系细化安排，最后对本论文的章节安排进行说明。

第二章：Android系统和百度地图API接口的相关知识。概要介绍Android系统的架构、百度地图、GPS定位系统以及常用的API接口。

第三章：对最短路径算法的发展进行研究。该章首先对最短路径算法进行分析并介绍几个对最短路径算法较为全面的评估情况，对设计依托的百度地图所用到的最短路径规划算法进行研究。

第四章：该章阐述了设计思路、实现功能的过程，最后对该设计软件进行功能测试。

第五章：总结与展望。总结本设计的研究情况及分析已经取得研究成果，提出研究不足之处并根据研究不足指出本课题今后的研究方向。

第2章 关于系统相关技术的研究

2.1 Android系统简介

2.1.1 Android系统概述

Android是谷歌开发的移动操作系统^[11]。它基于修改版的Linux内核和其他开源软件，主要为智能手机和平板电脑等触摸屏移动设备设计。Android一直是全球智能手机行业最畅销的操作系统，拥有数量最多的生产商家。截至2017年5月，它拥有超过20亿的月活跃用户，安装数量是所有操作系统中最大的。

Android统一的开发平台得益于其免费开放外围开发工具的举措，这一举措既保证了程序的可移植性，又降低了开发成本。这使得Android具有无可比拟的吸引力，市场份额也远超竞争者，并且仍在不断完善更新版本，后续发展势头十分迅猛。

图2.1列出了近几年各种操作系统手机的销量情况，在2017年第一季度，采用Android 系统智能的手机销量占比达到了86.1%，这一比率在2016年第三、四季度也分别达到了惊人的87.8%和81.7%，这说明Android是移动设备操作系统的主流选择方案。

图2.1 操作系统市场销量占比示意图

2.1.2 Android 平台构架

Android系统架构^[12]自下而上可以分成5层，是系统由基础向应用级发展的一个层次，这5层分别是Linux内核、硬件抽象层(HAL)、ART和库、应用程序框架以及应用程序，具体分层情况如图2.2所示。

图2.2 Android平台构架示意图

1. Linux内核。Linux是安卓系统的核心。因为Linux内核要负责驱动硬件正常工作，比如蓝牙、显示屏、扬声器、摄像头以及各种接口。同时负责分配硬件资源提供系统核心服务。
2. 硬件抽象层(HAL)。主要作用是提供一个接口，连接软件和硬件，同时也是为了方便开发者开发，不用为了各种各样的硬件而去做特别的定制。

3.1 ART。设计用于在电池、进程和内存方面的能力有限的环境下运行应用程序。从Android 5.0开始，独立的应用程序在ART中有独立的进程，这样对于应用程序的进程管理提出了更高的要求。ART使用DEX文件，这是一种字节码，专门为Android设计，帮助ART更有效地管理内存。包含一组核心库，在Java编程环境下使开发人员能够编写Android应用程序。在Android 5.0之前，Dalvik被用作ART。ART既可以提前(AOT)编译，也可以即时(JIT)编译。它还具有非常有效的垃圾收集能力。

3.2 库。通过Android应用程序框架向开发人员公开。包含Android系统组件使用的C/C 库。一些功能包括,SQLite库用于数据存储和轻量的移动内存占用和任务执行。WebKit库主要提供Web浏览引擎和许多相关功能。surface manager库负责在屏幕上渲染窗口和绘制各种应用程序的表面。媒体框架库为音频和视频提供媒体编解码器。OpenGL(Open Graphics Library)和SGL(Scalable Graphics Library)分别是用于3D和2D渲染的图形库。FreeType库用于呈现字体。

1. 应用程序框架。它是一组用Java编写的API，允许开发人员访问Android操作系统的完整特性集。开发人员可以访问核心应用程序使用的全部相同框架API，这样他们就可以在应用程序的功能方面得到更多的增强。启用及简化核心组件及服务的重用，例如:窗口管理器:管理窗口和绘图表面，是表面管理器库的抽象。内容提供程序:使应用程序能够访问来自其他应用程序的数据或共享自己的数据。

它提供了在应用程序之间交换数据的机制。视觉图像系统:包含用于构建应用程序UI的用户界面构建块，包括列表、网格、文本、框、按钮等。并且还执行UI元素的事件管理。包管理器:管理与当前安装在设备上的应用程序包相关的各种信息。电话管理器:允许APP使用设备的电话功能。位置管理器:处理位置感知功能。通知管理器:允许应用程序在状态栏中显示自定义警报。

5.应用程序。Android应用程序层除了包含系统应用程序也包用户安装的程序，用户可以从Android的官方商店下载这些应用程序。这一层使用它下面的所有层来实现这些移动应用程序的正常运行。因此，正如我们所看到和理解的，Android拥有分层的功能，或者我们可以把分组的功能称为软件堆栈，这使得Android在任何设备上都可以非常流畅地工作。

2.2 百度地图

百度地图是由百度提供的一个桌面和移动互联网地图服务应用程序,提供卫星图像,街道地图、街景视角和室内视图,以及徒步旅行,汽车,或公共交通工具的路线计划等功能。百度地图使用墨卡托投影的一种变体，将地图数据分割成块，距离用度数表示。它与一个基础的经纬度引用相关联，使用BD-09坐标系，百度地图 Android API允许应用程序包括百度地图或街景，而不需要打开单独的应用程序，允许完全控制相机，并提供添加自定义标记和覆盖地图的方法。

百度地图API指定必须通过坐标转换接口转换“真实”(WGS-84) GPS坐标。提供HTTP接口、JavaScript API、Android SDK和iOS SDK。百度地图API是由百度开发的一组应用程序编程接口(API)，它允许与百度服务通信并将其集成到其他服务。第三方应用程序可以使用这些API来利用或扩展现有服务的功能。

百度地图提供有基本地图调用显示、路径规划、LBS云存储和检索等功能，百度地图通过GPS、Wifi或者基站提供定位服务。创建一个Android客户端的应用需要申请如图2.3所示的百度地图API Key。