基于Spark的城市出租车出行路径分析专家系统开题报告

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

本次毕业设计的课题名称为“基于spark的城市出租车出行路径分析专家系统”。众所周知，出租车是城市公共交通的重要组成部分，但出租车在实际运营中，由于缺乏合理的规划和管理，导致空驶率较高、运营效率低下、司机收益较差等问题。

1.1 研究目的

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

本次毕业设计针对出租车司机个体，通过大数据分析，机器学习完成一个路径推荐系统，提高出租车的运营效率。

2.1 基本内容与研究目标

在获取武汉市一个月的出租车GPS数据的前提下，结合路网数据，比较两种最短路径算法：迪杰特斯拉算法和ALS矩阵分解得推荐模型。特别在推荐模型中结合蚁群算法进行适当的改进，建立恰当的数学模型，将原始数据进行数据清洗，通过数学模型转换成Spark大数据平台提供的MLlib机器学习API易于处理的数据，最终在提供起点、终点、当前时间点的前提下为出租车展现一条最优的路径解。完成路径求解之后，通过Spark提供的推荐评价系统对结果进行评估，反馈至专家系统，从而进一步提升专家系统的有效性。

2.2 拟采用的技术方案及措施

首先需要获取路网信息和一个月内的武汉市出租车GPS数据，GPS数据在进行毕业设计之前已经从云平台上获取，路网数据需要从交通部官方获取。GPS数据样本如下表所示：

表1 数据样本

字段含义分别是：出租车标号、时间、维度、经度、行驶速度、行驶方向、行车状态。

路网数据已经从武汉测绘局获取，拟定将路网看作有向图，那么求解的目的就变成了有向图的最短路径寻优问题。迪杰特斯拉算法是最短路径寻优问题中的经典算法，特别适用于带有权值的图结构，将出租车出发点看作图中的一个顶点v,终点看作另一个顶点w，针对路网图G(E,V),迪杰特斯拉算法的流程如下图所示:

图1 迪杰特斯拉算法

针对上述的算法进行改进可以得到其分布式计算的优化版本，从而提升该算法在Spark平台上的执行效率。

虽然这个算法可以求出最短路径，但是并不一定是最优路径，因为有向图中边的权值仅仅是根据路径长度考虑的，如果将天气、时间段、路况、红绿灯等问题考虑在内修改路径权值，将会浪费大量的时间和经历建立数学模型。

针对这个有极多因素影响的问题，单纯从一个或是几个方面考虑得出最佳结果的概率很小。在这种情况下，避开从单个因素研究问题，而是从专家（在此处可以理解为有经验的司机）的角度考虑这个问题，就会使得问题简化。

由于Spark大数据平台下提供了MLlib这样一个简单易用的机器学习算法库，因此可以将路径寻优问题转换成路径的推荐问题，将出租车司机看作用户（user），将行车路径看作事物（item），用户与路径之间的关系使用特定的数值表示。数值越高，表示用户对该事物的满意程度越高。在此之上使用推荐算法就可以针对新的用户，即使用此专家系统的出租车司机推荐路径。因此，用户与事物之间的喜好程度数值的建模至关重要，这也是后一阶段重点研究的问题。

Spark平台的架构如下图所示：

图2 Spark平台总体架构

用户在人机交互界面输入起点、目的地、当前时刻，之后Spark计算模块根据数据仓库中的出租车GIS数据和武汉市路网数据得到路况信息，根据数学模型生成候选路线集。由于Spark计算模块API中大量使用的是RDD数据、因此原始数据必须转换成为RDD数据。根据MLlib库中基于矩阵分解的推荐模型生成最优路径，推荐结果返回至人机交互界面。

在具体实施过程中，拟采用4台虚拟主机建立Spark计算集群，操作系统为CentOS6.5，内存4GB，开发语言Scala，设计过程中终点关注候选路径与出租车之间置信度的数学模型建立。

实验过程中可以根据数据仓库中出租车GIS数据将某一片地区（例如洪山区）作为实验对象，研究数学模型和推荐算法的合理性，然后推广至整个武汉市主城区。

最后将机器学习方案与传统的迪杰特斯拉算法进行比较，比较计算速率和结果的合理性。合理性的评估可以直接根据当天的出租车实际数据进行统计，计算相同起点与终点需求下出租车实际选择的路径和推荐路径中节点相同的数目。

3. 研究计划与安排

1) 第1-3周：完成毕业设计选题调研、文献阅读和外文翻译，收集相关资料，完成开题报告，进行小组内选题答辩。上传开题报告到教务网，完成开题任务。

2) 第4-6周：熟悉最短路径算法知识、linux操作系统、spark大数据平台和scala语言。初步设计出推荐系统的数学模型，编写所需要的语言程序和设计图。

3) 第7-10周：完成两种方案软件实现及调试、对比两种方案进行性能分析，做出合理改进。

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

[1] hai yang s.c.-wong-k.i.-wong. demand–supply equilibrium of taxi services in a network under competition and regulation[j]. transportation research part b:methodological, 2002, 36(9): 799-819.[2] hai yang s.c-wong. a network model of urban taxi service[j].transportation research part b: methodological, 1998, 32(4): 235-246.[3] hai yang min-ye-wilson-h.-tang-s.c.-wong. regulating taxi services in the presence of congestion externality[j]. transportation research part a: policy and practice, 2005,39(1): 17-40.[4] liao z.. taxi dispatching via global positioning systems[j]. ieee transactions on engineering management, 2001, 48(3): 342-347.[5] athanasios ziliaskopoulos dimitrios-kotzinos-hani-s.-mahmassani. design and implementation of parallel time-dependent least time path algorithms for intelligent transportation systems applications[j]. transportation research part c: emerging technologies, 1997, 5(2): 95-107.[6] 徐超. 面向最可盈利性的出租车出行路径分析模型与算法 [d].华东师范大学, 2012.[7] 姚亚锋,方贤进,陈代梅. dijkstra算法的一种高效率实现[j]. 计算机与数字工程, 2007(7):7-8, 35-36, 58.[8] 陈益富,卢潇,丁豪杰. 对dijkstra算法的优化策略研究[j]. 计算机技术与发展, 2006 (9):79-81, 84.[9] 张林广,方金云,申排伟. 基于配对堆改进的dijkstra算法[j]. 中国图象图形学报, 2007(5):175-179.[10] jasika. dijkstra's shortest path algorithm serial and[c]//mipro, 2012 proceedings of the 35th international convention, 2012: 1811-1815.[11] yin chao wang-hongxia. developed dijkstra shortest path search algorithm and simulation[c]//computer design and applications (iccda), 2010 international conference on, 2010: 1-116.[12] shu yang chunhua-li. an enhanced routing method with dijkstra[c]//geoinformatics,2010 18th international conference on, 2010: 1-6.[13] arnautovic m.curic-m.dolamic-e.nosovic-n.. parallelization of the ant colony optimization for[c], 2013: 1273-1277.[14] doostmohammadian m.pourazarm-s.khan-u.a.. distributed algorithm for shortest path problem[c]//networking, sensing and control (icnsc), 2014 ieee 11th international conference on, 2014: 463-467.[15] shiyou qian yanmin-zhu-minglu-li. smart recommendation by mining large-scale[c]//wireless communications and networking conference (wcnc), 2012 ieee, 2012: 3267-3272.[16] 唐炉亮,常晓猛,李清泉,等. 基于蚁群优化算法与出租车gps数据的公众出行路径优 化[j]. 中国公路学报, 2011 (2): 93-99, 130.[17] yanagisawa h.. a multi-source label-correcting algorithm[c]//parallel amp;distributed processing (ipdps), 2010 ieee international symposium on, 2010: 1-10.[18] zhang junying. a minimum resource neural network framework[j]. neural networks and learning systems, ieee transactions on, 2014, 25(8): 1566-1582.[19] 叶金平. 车辆导航中多路径推荐算法研究[d]. 重庆大学, 2011.[20] yafei guo zheng-qin-yang-chang. a novel hybrid algorithm for the dynamic shortest path problem[c]//natural computation (icnc), 2010 sixth international conference on, 2010: 2545-2550.[21] 王诏远,王宏杰,邢焕来,等. 基于spark的蚁群优化算法[j]. 计算机应用, 2015 (10):69-72, 89.[22] 郑凤飞,黄文培,贾明正. 基于spark的矩阵分解推荐算法[j]. 计算机应用, 2015 (10):73-75, 80.[23] 唐振坤. 基于spark的机器学习平台设计与实 [d]. 厦门大学, 2014.[24] 杨志伟. 基于spark平台推荐系统研究_杨志伟[d]. 中国科技大学, 2015[25] 胡于响. 基于spark的推荐系统的设计与实现[d]. 浙江大学, 2015.[26] 闫友彪,陈元琰. 机器学习的主要策略综述[j]. 计算机应用研究, 2004(7): 5-11, 14.[27] 陈凯,朱钰. 机器学习及其相关算法综述[j]. 统计与信息论坛, 2007 (5): 106-113.[28] 郭亚宁,冯莎莎. 机器学习理论研究[j]. 中国科技信息, 2010 (14): 210-211, 216.[29] 王家林. spark企业级实战[m]. 电子工业出版社, 2015[30] nick pentreath. machine learning with spark[m]. packt publishing. 2015.2