第一章 绪论
1.1课题背景和研究意义
近年来，移动物联网技术和无线通信技术高速发展，空间定位和全球导航系统日益完善，时空轨迹大数据也随之增多。新型的计算技术可以用于轨迹数据的存储，预处理，检索和挖掘[1]。因此，时空轨迹计算已成为越来越重要的研究课题。不仅在计算机科学领域受到了广泛的关注，而且在社会学，经济学，生物学等众多领域也有着广泛的应用。空间轨迹是由地理空间中的物体运动而产生的，通常由包含时间和经纬度的点集来表示。时空轨迹大数据包括车辆交通数据、人类运动数据、动物迁移轨迹数据和自然现象轨迹数据等[2]。随着移动终端的普及以及位置定位等技术的迅猛发展，人类社会产生了海量的轨迹数据。
在基于位置的社交网络中，例如微博、微信等，每天产生的带有位置信息的签到数据数以亿计。这些轨迹数据在一定程度上暗示着用户的生活兴趣和喜好，例如在线生活经验分享[3]和社交网络构建[4]等。在基于位置的出行服务中，例如滴滴出行，Uber 和共享单车等，日订单高达千万级别[5]。在外卖系统、物流配送系统中，随着用户数量的增加，轨迹数据呈现爆炸式增长。这些数据表明人类社会已经进入时空轨迹大数据时代[6]。在这其中，基于交通轨迹数据的挖掘是时空轨迹大数据挖掘的一个重要分支，在热门路线查询[7]，交通监管[8]，城市规划[9]，车辆排放[10-11]等方面有着成熟的应用。
车载 GPS 的应用和普及，使得传统的交通系统向智能交通系统发展。出租车轨迹是比较容易获取的时空轨迹大数据，而且包含了丰富的时间和空间维度信息，具有很大的挖掘空间。基于出租车的轨迹数据对分析城市居民出行特征，城市交通状况，路径规划等方面有着重要的作用。如何从出租车轨迹的历史数据中提取有用的路线信息，并将这些信息用于新的路线计算是当今学者研究的热点[12-13]。国内外学者在优化交通路线[14-15]、个性化推荐路线[16-17]、城市功能区发掘[18-20]等方面给出了很好的解决方案。
......................
1.2研究内容
基于时空轨迹大数据的路线规划机制的研究与系统构建的主要创新工作如下：
（1）出租车轨迹数据的时空分布分析。首先将原始的出租车轨迹数据进行清洗，剔除噪声数据并且筛选出轨迹中的高价值点。然后我们对数据进行时段的划分，目的是了解不同时段数据的变化趋势。最后，按照地理位置对轨迹数据进行分区，目的是分析城市不同区域间的数据分布。通过对出租车轨迹数据的时空划分，可以分析出租车整体的时空分布，为路线规划做铺垫。
（2）基于出租车轨迹数据的最佳客源点的挖掘。最佳客源点是出租车历史轨迹数据中最密集点集中的中心点，这表明大量的出租车司机曾经访问过该区域。如果空载的出租车司机能够精准地找到这些地点，必然能最大概率地接到乘客，提高盈利能力。我们采用了两种不同的聚类算法来挖掘轨迹数据中的最佳客源点。利用 DBSCAN 聚类算法能够在剔除噪声数据的同时挖掘出轨迹数据中的簇。出租车的历史轨迹数据分布存在核心区域分布广，偏远地区分布稀疏的特点，DBSCAN 聚类算法能够很好地检测各个地区的簇。数据经过第一次聚类形成了数据量大小不同的簇，每个簇对应现实生活中大小不一的区域，也即一些热门的区域。对于出租车司机而言，在区域之间的规划，尤其是大面积区域之间规划相比较于点到点的规划来说并不精准快速。因此，我们需要用中心点来代替一片区域。K-Means 聚类算法可以找出每个簇的中心点，也即最佳客源点。通过对每个簇的再次聚类，区域之间的路线规划问题就转换成点到点的精准路线规划问题。
（3）盈利路线的规划。数据经过聚类处理，形成了一系列的最佳客源点的集合。我们将基于点到点的路线规划问题转化为旅行商问题（Travelling Salesman Problem，TSP）。提出了基于最佳客源点的优化蚁群算法（Ant Colony Optimization Algorithm based on Optimal ProfitPoints，ACO-OPP）。在路径的选择概率上，我们通过加入影响因子来提高司机对于热门最佳客源点的选择。通过使用全局信息素更新和局部信息素更新相结合的规则来增加算法的探索能力，避免算法进入停滞状态。利用百度地图 API 中驾车距离实时计算函数来代替原始距离计算公式，使得算法计算结果更加贴合实际。
...........................
第二章 相关背景知识介绍
2.1时空轨迹大数据
轨迹数据符合大数据的 5V 特点：Volume（大量）、Velocity（高速）、Variety（多样）、Value（低价值密度）、Veracity（真实性）[31-32]。同时它还具备以下特征：
（1）时空序列性。轨迹数据是一系列带有时间戳的位置点数据。对于密集型轨迹数据集而言，相邻的数据之间，在时间上具有连续性，在空间上具有相似性，整体呈现序列性。
（2）异频采样性。首先轨迹的产生因个体行为而异，有较大的随机性和不确定性。例如带有位置信息的信用卡消费数据可能以小时、天数或者月份为单位。其次在数据的采集上，由于各个数据平台记录频率不同，轨迹数据的采样间隔差异显著。例如共享单车采集频率往往会低于出租车轨迹采集频率。
（3）数据丰富。数据类型丰富，例如 GeoLife 数据集是连续点的集合[3]而 Flickr 包含的是带地理标签的照片集[33]。数据维度丰富，例如 Gowalla 包含的是用户 ID、日期时间、经纬度和签到位置 ID 等[34]，而 GeoLife 包含的是经纬度坐标、海拔和日期时间等[3]，T-Driver包含出租车 ID、时间和经纬度[35]。数据规模大，轨迹数据的地理跨度很大，可能是小范围的跨度，例如某个城市区域的共享单车数据。可以是全球范围的跨度，例如飓风轨迹数据[36]。
（4）数据质量差。在数据的采集过程中，存在采样点丢失问题而导致轨迹数据偏移，与实际路网不匹配的情况。或者采样精度太高导致大量冗余数据等问题，数据质量差也给基于轨迹数据的研究课题带来巨大的挑战。
.....................
2.2路线规划
2.2.1 聚类算法
K-Means 算法[37]是在 1967 年由 MacQueen 提出，是最常用的动态聚类算法。该算法思路简单，易于实现，被广泛应用于各种学科领域。数据集经过 K-Means 算法聚类后，簇内对象具有高度的相似性，不同簇的对象具有很大的差异性。
基于 K-Means 算法的执行步骤：
输入：需要聚类的数据集和K 值
输出：每一个类的中心点
步骤 1：从数据中随机选取K 个轨迹点作为初始聚类中心；
步骤 2：遍历整个数据集，计算每一个轨迹点到 K 个聚类中心的距离。对距离进行排序，选择其中最近的那个聚类中心并把该轨迹点并入该类中；
步骤 3：对于步骤 2 中形成的每一个类，再次计算它们的中心点；
步骤 4：重复步骤 2 和步骤 3 直到聚类中心和上次中心点的差值小于规定的阈值。
DBSCAN[38]是一种基于密度的聚类算法。该算法需要输入一对全局密度参数 MinPts和Eps 。其中，参数 MinPts 是指某对象一定邻域范围内轨迹数据点的个数，而 Eps 则是邻域范围的半径。DBSCAN 可以检测出数据中的类和噪声点。对于出租车轨迹数据而言，必然存在部分地区轨迹分布不均匀的情况，因此基于密度的 DBSCAN 算法非常适合这种情况。
...............................
第三章 基于优化蚁群的路线规划机制 ................................. 16
3.1问题建模............................. 16
3.2算法描述............................... 17
第四章 基于博弈论的路线规划机制 ........................ 31
4.1问题建模........................... 31
4.2算法描述.................................. 32
第五章 系统设计与实现.................................. 45
5.1系统分析..................... 45
5.2系统设计............................ 45
第五章 系统设计与实现
5.1系统分析
随着科技的发展，5G 时代的到来，人们的生活越来越依赖于地图类服务软件。例如用于打车的滴滴出行、用于导航的高德地图和用于路线搜索的百度地图等等。地图服务平台是基于 Web 技术的全功能地理信息服务系统，各类的地图类服务会根据用户的需求搭载不同的功能区。本章的目的是基于本文第三章挖掘的最佳客源点进行路线规划，实现出租车司机快速寻客，同时引入第四章的 Stackelberg 博弈来避免热门路径的拥堵问题，提高路网利用率。
在系统的整体设计上我们采用了 SSM 框架，即 Spring + Spring MVC + MyBatis。Spring实现业务对象管理。Spring 提供了控制反转技术，这样容器会帮用户管理依赖的对象，实现程序的解耦。同时，Spring 还提供了面向切片编程，通过预编译方式和运行期动态代理实现程序功能的唯一维护。SpringMVC 负责请求的转发和视图管理。SpringMVC 是使用了 MVC设计思想的轻量级 Web 框架，对 Web 层进行解耦，使我们开发更简洁。Mybatis 是对 JDBC的封装，它让数据库底层操作变的透明。我们将系统部署在 Tomcat 服务器上，Tomcat 是 Servlet容器，实现了对 Servlet 和 JSP 的支持。
..................
第六章 总结与展望
6.1总结
本文是基于时空轨迹大数据的路线规划机制的研究和系统构建，一方面，针对出租车没有订单的情况下寻客比较困难，我们提出了一种基于最佳客源点的路径规划算法 ACO-OPP。另一方面，针对在路径规划中存在热门路径的拥堵问题，我们引入了 Stackelberg 博弈的思想，通过对交通管理者和出行者进行建模求解，实现管理者和出现者的利益最大化。现将本文工作总结如下：
（1）出租车轨迹数据时空分布分析。对筛选出的上下客点数据先进行时段的划分，对于每一个时段再进行分区。通过对出租车轨迹数据的时空划分，可以分析出租车整体的时空分布，为路线规划做铺垫。
（2）基于出租车轨迹数据的最佳客源点的挖掘。我们采用了两种不同的聚类算法来挖掘轨迹数据中的最佳客源点。利用 DBSCAN 聚类算法挖掘出轨迹数据中的簇。通过 K-Means 聚类算法可以找出每个簇的中心点，也即最佳客源点。
（3）盈利路线的规划。我们提出了基于最佳客源点的优化蚁群算法 ACO-OPP。在路径的选择概率上，我们通过加入影响因子来提高司机对于热门最佳客源点的选择。通过使用全局信息素更新和局部信息素更新相结合的规则来增加算法的探索能力。利用百度地图 API 中驾车距离实时计算函数来代替原始距离计算公式。
（4）Stackelberg 博弈模型。我们引入 Stackelberg 博弈模型，通过固定的时间间隔进行交通诱导。Stackelberg 博弈的双方分别是交通管理者和出行者。交通管理者希望高效利用路网资源，而出行者希望自己的出行需求得到满足。管理者和出行者之间通过合理诱导，最终达到一种均衡状态，从而实现管理者和出行者效益最大化，路网资源能得到极大利用并有效解决热门路径的拥堵问题。
（5）基于 SSM（Spring + Spring MVC + MyBatis）框架构建了出租车路线规划系统，实现了地图展示、定位、最佳客源点的检索和查询、路线规划、路线导航等功能。该系统首先会根据司机的当前位置显示周围的最佳客源点，其次会基于附近的最佳客源点规划一条路线。在路线规划上，由于考虑到热门路径的拥堵问题引入了 Stackelberg 博弈模型，并在管理者决策方求解时利用了提出的 ACO-OPP 算法。最后系统会对规划的路径进行路线导航。
参考文献（略）