基于大数据的动态出行管理平台研究

朱中毅　王家珂　孙晨熙

（西南交通大学交通运输与物流学院，四川　成都　611756）



基于大数据的动态出行管理平台研究

朱中毅王家珂孙晨熙

（西南交通大学交通运输与物流学院，四川成都611756）

摘要：随着居民生活水平的提高，近几年我国城市私家车的数量大幅度增加，但与此同时也产生了许多社会问题，如严重的大气污染、大面积的交通拥堵、日益加剧的能源消耗等。针对以上问题，本项目组设计了基于大数据的动态出行管理平台。该平台通过路线匹配算法、自动撮合算法和云计算模型等技术手段，结合实时的路网流量数据，为出行者智能地规划最优路径，并将起讫点相同或相近的出行者匹配在同一次出行当中，建议其共享出行，进而在满足人们出行需求的同时降低私家车的出行数量，也为城市居民普及一种绿色出行理念。本文将从设计思路及技术路线对系统的构建进行相关阐述。

关键词：共享出行；路径规划；大数据；云计算

1　研究背景

随着我国居民生活水平的提升，私家车数量也在不断增多，但与此同时也产生了很多社会问题。机动车尾气的排放是大气污染的主要来源，尤其对雾霾天气的影响最大；私家车的增加也导致了严重的交通拥堵，降低人们的生活品质，浪费人们的出行时间。以北京市为例，中国科学院可持续发展战略研究组发表《2012中国新型城市化报告》显示，由于交通拥堵，2010年北京市居民出行受影响的人数平均每天达1381.8万人次，平均每日每人次延误66min，由此造成的时间价值损失每天高达32386.2万元；此外，汽车行驶时间的增加必然增加燃料消耗，每年仅汽车燃料北京市就浪费722.9万L，经济损失高达201.1亿元。不仅如此，车辆的闲置现象也十分严重。据统计，2012年北京的出租车空载率为30%，“一人一车”现象十分严重。如果能够通过拼车而使“一人一车”现象得到改善，那么在道路上行驶的汽车数量将得到有效减少，机动车尾气的排放量也将会减少。因此，基于这样的思想—满足人们出行需求的同时降低机动车出行率，拼车出行的方式不仅能够在一定程度上缓解交通拥堵，减少汽车尾气排放等社会和环境问题，还同时具有节约出行成本和扩大社交等好处。

2　设计思路

本项目小组拟根据云计算理论，建立私家车交通资源和出行需求的合理配对模型（招标与投标的自动撮合模型），并研发一款结合网页端与手机端的软件，将车、数据库、服务器和用户手机终端进行组网，司机通过GPS模块定位出租车位置，传感层模块采集车内温度等信息上传到远程服务器，实现信息共享［1］。乘客方面，可以通过网页地图信息查看周边街道空车的分布情况以及车内环境、车型等基本信息，从而选择合适的车辆。用户通过软件提供的车主信息向车主发送打车请求，收到打车请求的车主可发回确认信息。同时，该软件依据现今城市交通大数据，以Dijkstra算法为基础，通过对相关理论文献进行研究，对原有算法进行创新，结合城市路网车流量的动态数据，实现多人拼车时的最优路径规划选择，从而实现以用户最优为目标的路径起讫点规划方案，节约用户的出行时间。与此同时，这样一种新型的融合交通出行理论的拼车模式能够在保证居民安全出行的同时，逐渐培养人与人之间的信任感，并树立绿色环保的出行理念。

3　项目目标

该管理平台旨在实现用户快速便捷地找到同路的乘车伴侣，在减少机动车出行数量的同时，帮助车主以自由民主的市场方式完成交通搭乘的选择。在实现合理拼车出行的同时，能够大大减少由于机动车尾气排放而引起的环境污染及交通拥堵等社会问题的出现。

4　项目内容

该管理平台建立了能够融合多终端设备数据的云计算模型，以城市路网车流量的动态数据作为规划拼车路线的首要影响因子；同时，以社区为单位，通过人脉重合度智能推选算法，以人脉重合度的高低值作为次要影响因子，在考虑社区单元因素的同时，优先推选人脉相识度更高的招标人与投标人的信息至用户终端，最终实现在一人或多人，单组起讫点或多组起讫点情况下的最优拼车路径规划［2］。

使用该平台的用户分为二类：①系统游客，只可以浏览该软件的招标信息和投标信息，但无法进行选择和操作，只具备浏览的权限，也不为该类客户提供个性化服务，该类客户无需注册；②正式用户，必须在该动态管理平台注册，登录系统后，这类客户可以浏览已注册私家车的拼车信息，可以实时在线拼车，也可享受该管理平台提供的个性化服务及其他服务等。

该平台通过统计城市所有接入本系统服务的车主用户实时发布的车辆信息，可以帮助用户以最便捷的方式找到附近有空座位且有相同或相近出行路线的车辆，并支持提前预定车位、最优路径规划以及语音消息提醒等实用功能。而该平台由于软实体占主要开发和维护部分，因此具有廉价实用的特性，并且能够有效解决当前车主的私家车空座位信息处于信息孤岛的难题；同时，依据城市路网车流量的实时数据为用户选择最优路径，从而降低车辆尾气污染，缓解交通拥堵，提升出行效率。由此可以预见，基于城市交通大数据的以私家车为主体的管理平台将有望成为居民出行必不可少的辅助决策工具。

5　技术路线

5.1技术流程

本项目组从系统角度出发，以PHP编程语言作为服务器动态执行脚本编写语言，以Apache作为服务器端软件脚本服务发布环境，以Eclipse作为Android手机端（用户APP）开发编译环境，以Xcode作为IOS手机端（用户APP）开发编译环境，以云计算技术作为系统后台数据处理手段，实现大数据环境下私家车的智能调度。其技术流程图如图1所示。

5.2相关技术及算法

5.2.1Dijkstra算法介绍分析。目前，常用的计算最短路径的算法主要有Dijkstra算法、Floyd算法和A*算法等。当路网规模不大时，A*算法和Dijkstra算法效率相近，而Floyd算法复杂度为O（n3），在求单源点最短路径时效率较低；而Dijkstra算法复杂度为O（n2），在求解单源点最短路径时，效率比较高。考虑到该管理平台使用的都是单源点路径规划，故采用Dijkstra算法。

在求解最短路径问题时，多使用有向图或无向图来描述问题，即在G=（V，E）中，边E［i］的距离权值设为w［i］，并找出从顶点V1到路网中其他各节点的最短距离。

下面对Dijkstra算法的计算步骤进行描述：①假设在某个路网中有n个节点，在初始时刻，令集合S={V1}，T= {V2，V3，V4，……，Vn}；②在集合T中选取距离V0权值最小的顶点且该顶点不在集合S中，选取后将该点加入到集合S中；③修改集合T中余下各顶点的距离权值；④修改此距离权值，使V0到Vi的距离权值缩短；⑤直到集合S中包含所有集合T中的节点，算法结束。

根据上述步骤的描述可知，Dijkstra算法的主要特点是在路网中设置一个起点，并以该点为中心，向外进行扩展，直到该路网中的所有节点都被囊括为止。Dijkstra算法的运行时间为搜索路网中所有节点的集合中最小元素的运算时间，其时间是路网中节点数n和边数m的函数。

尽管如此，现阶段Dijkstra算法仍然存在不足：①当从集合T中选定一个节点k作为中转点时，需要扫描集合T中的其他节点j并更新其距离权值，而在集合T中还存在着大量与中转节点k不直接相连的节点i（即w［i］=∞）；②Dijkstra算法是由单一方向遍历所有节点，求出以任意一个节点作为起点时到其余各节点的最短路径［3］。对于节点较多，路况复杂的路网，该算法的实时性较差，因此有对其进行创新的需要。

5.2.2Dijkstra算法的创新。Dijkstra算法的复杂度为O（n2），若Dijkstra边数远小于n2，就可以使用子集数据结构对其进行优化，降低算法的复杂度［4］。

算法优化方法：①将与路网源点相连的点加入子集；②选出子集元素u，并对子集进行调整；③处理未被使用的、与u相邻的路网节点；④更新各节点距离，并修改该元素在子集中的位置；⑤直到u为终点时，结束算法。否则，继续重复②③④步骤。

Dijkstra算法创新的流程图如图2所示。

5.2.3路径匹配算法。在基于大数据的动态出行管理平台中，当有用户发出拼车请求，并提供了起讫点的地理位置时，需要在其他用户所发布的路径信息中选择一条合适的路径与其匹配。若该用户为乘客，则需要根据车主的出行路径进行匹配；若该用户为车主，则需要根据乘客的出行路径进行匹配。因此，本项目组使用了路径匹配算法，使该平台能够根据起讫点以及路径的要求为有需求的用户进行适当的匹配。

图1　平台技术流程

当有用户发布拼车请求时，路线匹配算法将根据此用户所选择的起讫点在数据库中规划出合适的拼车路径。在此，提供以下2种路径匹配方式。

5.2.3.1路径直接匹配法

根据用户提供的起点和终点生成k条路径，这k条路径会依照用户侧重的优先级排序。在此，设匹配函数：

其中，λ为匹配系数；pathm表示用户所选择的第i条路径与系统给出的第m条路径中完全相同的子路径；di为第i条路径的长度。

5.2.3.2节点与路径相匹配的方式

这种方法分为2种情况：①最好情况（见图3），其起点和终点都在已知的某条路径上，如起点A和终点B都在线路2上，此时不需要修正原来的行车路径，在系统数据库已有的路径数据足够多的情况下，这种情况出现的概率最高；②最差情况（见图4），其起点和终点都不在已知路径上，即起点A和终点B都不在线路2上，这时需要修改原有的行车路径，这种条件下若需满足拼车需求，则车主必须要绕路接送乘客，或者乘客步行一段距离到达乘车地点。这种情况虽然有些不合理，但只要乘客和车主能够沟通协调，仍然可以使问题得到解决［5］。

图2　算法创新流程图

图3　最好匹配情况

图4　最坏匹配情况

路径直接匹配法在最开始就给出了路径，不再需要再次求路径以及路径长度；节点与路径相匹配的方式还需要对现有路径进行调整，规划出新的路径并计算路径长度。尽管如此，路径直接匹配法同样存在不足，该方法只能在λ值为1的情况，即完全匹配时才能给出匹配路径。当存在最差情况时，用户选择的n条路径与系统规划的k条路径进行匹配，不存在使得λ值为1的匹配情况，但在已知路径足够多的情况下，可以通过这个方法尽量满足用户需求。因此，在该平台中，结合了上述的两种匹配方法来更好地满足用户需求。

路径匹配算法可以在Dijkstra算法基础上设计实现。通过用户对平台的使用，系统数据库可以对已有的路径进行储存，在有用户提出新的拼车请求时，系统可以根据其提供的起讫点在数据库中对已有数据进行检索并提供合适的路径规划，然后依据匹配度从高到低的路径排列顺序给予推荐。

6　结语

基于大数据的动态出行管理平台主要通过拼车这一方式来缓解现今城市中交通拥堵的问题，同时结合城市路网中车流量的动态数据来为出行者规划最优路径。对用户而言，该平台可以为其出行提供优质的服务，节约出行时间，提高出行效率；对于城市交通部门而言，该平台通过拼车这一方式来缓解交通压力，减轻有关部门的管理负担；对于政府而言，通过该平台不仅能够有效地宣传绿色环保的出行理念，同时拼车也有利于拉近人与人之间的距离，为构建和谐社会发挥积极作用。

参考文献：

［1］李由.路径搜索和匹配算法在交通信息服务中的应用［J］.航空计算技术，2009，39（1）：98-106.

［2］张靓.基于子集优化的Dijkstra算法的交通最短路径查询系统的设计与实现［D］.长春：吉林大学，2015.

［3］田智勇.基于Android平台的实时拼车系统的设计和实现［D］.武汉：华中科技大学，2007.

［4］张凯杰，潘奇.基于最短路径的求解与创新［J］.科技创新导报，2012（29）：38-41.

［5］雷东升，诸彤宇.一种基于实时路况信息的动态路径规划算法［J］.计算机科学，2008，35（4）：28-30.

中图分类号：U491.1

文献标识码：A

文章编号：1003-5168（2016）01-0056-04

收稿日期：2015-12-25

作者简介：朱中毅（1994-），男，本科在读，研究方向：交通运输；王家珂（1994-），男，本科在读，研究方向;交通运输；孙晨熙（1994-），男，本科在读，研究方向：交通运输。

Research on Dynamic Travel Management Platform Based on Big Data

Zhu ZhongyiWang JiakeSun Chenxi
（School of Transportation and Logistics,Southwest Jiao Tong University，Chengdu Sichuan 611756）

Abstract:With the improvement of people's living standards,the number of private cars increased significantly in re⁃cent years.However,at the same time it caused many social issues,such as serious air pollution,traffic congestion, increasing expenditure of energy and so on.To solve the above problems,we designed theDynamic Travel Manage⁃ment System based on Big Data.Using the technical means such as the line matching algorithm and automatic match⁃ing algorithm and cloud model,and combining with the seasonable network traffic data,this system can planning opti⁃mal path for traveler intelligently.And it can also match the travelers who have the same or similar begin and end point in the same trip,thus can meet the demand of people’s travel and meanwhile reduce the number of private cars in cities,which populars a kind of“green travel”concept for city dwellers.This article is related from the design ideas and technical route of system construction.

Keywords:sharing travel；ath planning；big data；cloud computing