摘 要

打车由线下转移到线上，网约车服务正影响着数亿人的出行习惯。网约车行业是一个面向大众的服务性行业,车辆分散在城市各个地区,对社会的影响和涉及到的范围较广,如何合理调控车辆运力的投放、加强车辆的安全管理、减少车辆空驶里程、降低油耗减少资源浪费、为乘客提供更快更优质的服务等等切实的问题的解决需要更先进的系统来支撑。

滴滴打车是我国国内第一家使用移动互联网技术和网络智能召车系统的应用类软件。目前滴滴打车已经成为全国最大的召车服务软件平台，每天为全国数以亿计的注册用户提供便捷的召车服务。滴滴庞大的用户群体和订单数量为其收集到丰富的出行大数据资源，为其在公共出行领域发挥更大作为奠定了良好基础。

本文通过研究滴滴出行脱敏的真实订单数据，统计调度区域内的出租车需求量，分析总结用车需求较高的热点区域。通过对数据节点的可视化处理，可以清晰的观察到某日或某时段用车需求的总体分布情况。再通过ISODATA聚类算法进一步规范热点区域范围、个数及其中心位置。结合当前热点区域分布情况，提出了基于马尔科夫决策过程（MDP）的空驶出租车辆调度方法，期望实现减轻道路拥堵、节能减排、增加司机收入、提高城市出租车的平均运行效率的目标。

关键词：滴滴打车；ISODATA算法；马尔科夫决策过程；车辆调度

Abstract

Online car service is changing hundreds of millions of people's travel habits. The online tour industry is a service industry that is directly oriented to the public, so the impact on the society are relatively wide. How to rationally plan the delivery of vehicle capacity, strengthen the safety management of vehicles, reduction of fuel consumption, and provision of faster and better services to passengers require more advanced systems to support the solving of practical problems.

Currently, Didi has become the largest taxi software platform in the country, providing convenient taxi service to more than 100 million users nationwide every day. Dramatic user groups and order quantities have collected a wealth of travel big data resources, laying a good foundation for them to play a greater role in public travel.

In this paper, by studying the actual order data of the desensitization of droplets, the demand of taxis in the dispatch area is calculated, and the hot spots with high demand for vehicles are analyzed and summarized. Through the visual processing of data nodes, the overall distribution of car demand on a certain day or time can be clearly observed. The ISODATA clustering algorithm is further used to further regulate the scope, number, and center position of hotspots. Combining the distribution of the current hotspots, a Markov Decision Process (MDP)-based method for scheduling empty taxis is proposed. It is expected to achieve energy conservation and emission reductions, increase the profits of taxi companies and driver income.

Key Words：Didi Taxi；ISODATA algorithm；Markov Decision Processes；Vehicle scheduling

目录

第1章 绪论 1

1.1背景及意义 1

1.2国内外研究现状 2

1.3课题研究内容与预期目标 3

第2章 数据简介与预处理 4

2.1滴滴出行服务数据简介 4

2.2 Pandas介绍及应用 5

2.2.1 Pandas简介 5

2.2.2 Pandas在本次设计中的应用 5

2.3 Pyecharts介绍及应用 6

2.3.1 Pyecharts介绍 6

2.3.2 Pyecharts在本次设计中的应用 6

2.4本章小结 8

第3章 数据挖掘方法及原理 9

3.1 ISODATA聚类算法 9

3.1.1 算法原理介绍 9

3.1.2 ISODATA算法与K-means算法对比 9

3.1.3 ISODATA算法实现过程 11

3.1.4 ISODATA算法流程图 13

3.2聚类结果及分析 14

3.3本章小结 18

第4章 基于马尔科夫决策过程的调度策略 19

4.1 马尔科夫决策过程介绍 19

4.1.1 马尔可夫决策过程概述 19

4.1.2.马尔可夫性质 19

4.1.3.马尔可夫决策过程的形式化定义 20

4.1.4.马尔科夫决策过程的描述 20

4.1.5.马尔可夫过程的算法求解 21

4.1.6 策略指标 21

4.2 马尔科夫决策过程在本次设计中的应用 22

4.2.1 定义与假设 22

4.2.2 问题分析与求解 22

4.3本章小结 24

第5章 总结与展望 24

参考文献 25

致谢 26

第1章 绪论

1.1背景及意义

网约车是网络预约出租车的简称，是以互联网技术为基础构建服务平台，整合供需信息，选择符合条件的车辆和司机，提供非巡游的预约出租汽车服务的经营活动。传统出租汽车重新定义为巡游出租汽车，网络预约出租车与其最大的区别就在于获得顾客的方式是对顾客在互联网上发布的需求信息进行接单，而不是在街道巡游，接单方也由传统出租车公司变更为网约车平台企业。

过去十几年主要城市出租车牌照数量增速均远小于人口增速及人均可支配收入增速，出租车牌照供给不足；而私家车保有量的持续增长导致交通、环保等问题严重，限牌、限号由一线转至二线，未来数年公共交通需求将大力发展，出租车服务的刚性需求，以及巨大的市场容量，给予“网约车”绝佳的发展机遇。

打车由线下转移到线上，网约车服务正悄悄改变着数亿人的出行习惯。CNNIC数据显示，截至2017年12月，中国仅网约专车和快车用户规模已超2亿，整体增速迅猛。其中，网约车用户（不含网约出租车）规模增长了40.6%，网约出租车用户规模增长了27.5%。以上数据表明，网约车正在成为越来越多人日常出行的选择。

然而，网约车合法化后的一年多来，打车难、打车贵的难题仍然没有彻底解决，相反还有反弹的迹象。根据滴滴出行的一项调查数据表示，今年6月打车难度与去年6月相比，北京增长12.4%，上海增长17.7%，广州增长13.2%，深圳增长22.5%；难度减少的城市中，成都减少1.8%，三亚减少1.0%。用户主要对等待车辆时长和接单司机距离的满意度较低。一方面召车需求和可用车辆的时间、区域分布不匹配导致了司机接单时间、接单距离、接驾时间变长，而另一方面，一线城市针对网约车出台的政策也间接导致了合规网约车数目的减少。

在不断的发展过程中带来的各种管理问题实实在在的摆到了网约车行业管理的政府单位的面前以及网约车企业管理层面前。网约车行业是一个服务性行业直接面向大众,车辆分散在城市各个地区,对社会的影响和涉及到的范围比较广,如何合理调控车辆运力的投放、加强车辆的安全管理、加强对司机和车辆的监管、减少车辆空驶里程降低油耗减少资源浪费、为乘客提供更快更优质的服务等等切实的问题的解决需要更先进的系统来支撑,通过系统来配合实现本行业的健康稳定发展以及保证企业自身在行业内更具竞争力和更快的决策反应力。

滴滴打车是我国国内第一家使用移动互联网技术和网络智能召车系统的应用类软件。它是由北京小桔科技有限公司于2012年9月9日正式推出的，与高德地图、百度地图进行了战略合作，实施与地图类应用合作联运的新模式。目前，滴滴打车已经成为全国最大的召车服务软件平台，每天为全国数以亿计的注册用户提供便捷的召车服务和本地化的生活服务。2013年底开始，滴滴打车独家接入微信平台，通过微信小程序实现召车功能和支付功能。

滴滴的基础在于拥有庞大的出行数据资源，拥有已覆盖全国各主要城市的车主信息数据库。截至2014年1月，滴滴打车已向北京、上海等30余个大中小城市推广并受到好评，全国注册滴滴打车的司机数量突破千万，用户过亿，日均订单530万，一线城市订单达成率约为85%。目前滴滴打车已经覆盖全国36%左右的出租车，北京、上海司机渗透率达70%。可以看出，滴滴出行的使用率是非常高的。当乘客需要乘车时，它能够立即匹配出与其最适合的车主，其中匹配条件如距离、车型和价钱乘客人数等。采取动态定价策略，通过算法监控交通状况和实际行车时间并根据车辆需求变化调整价格。

滴滴通过收集到的出行大数据，实现区域热力图、城市运力分析、城市出行报告、城市交通出行预测、OD数据分析以及信号灯动态配时等，同时还能在公共出行服务如实时路况、实时公交、城市运力补充等方面发挥能效。当然，滴滴打车的最大价值是在于匹配用户和司机的需求，改变传统打车模式，在移动互联网时代下引领用户现代化的出行方式。

1.2国内外研究现状

国内研究现状：

（1）作者冯琦森在《基于出租车轨迹的居民出行热点路径和区域挖掘》^[1] 一文中研究了重庆市配备GPS设备的1万多辆出租车所采集的轨迹数据。通过预处理大量的GPS数据，生成可用于聚类的有效轨迹，并进一步筛选出出租车上下车轨迹点。然后根据城市居民出行的一般规律，考虑居民出行不同的时间段，应用不同的聚类方法分析出租车轨迹和轨迹点数据，从而发现不同时间段居民出行的热点路径、获取出租车上下客热点区域，挖掘其隐含的出行行为规律信息，最后研究了多种可视化技术，将居民出行热点区域和路径进行了直观的展示。

（2）作者贾婷在《基于乘客需求及分布的出租车调度方法技术研究》^[2]一文中针对出租车行业的管理特点和技术要求，根据历史轨迹数据估算调度区域内的出租车需求量。分析总结了该地区乘客的出行规律，并结合当前区域内出租车分布情况，提出了基于载客热点区域出租车饱和率的空驶出租车辆调度方法。该调度方法不但可以指导出租车的巡游方向，还能生成可以较快搭载到潜在乘客的具体巡游路线。采用集中调度模型来响应乘客叫车信息，该模式结合空载车和已载客出租车的目的地两方面来调度区域内所有车辆，采用实时平均速度来划分时间最短区域。然后在乘客上车时，应用基于道路阻抗的蚂蚁算法为乘客选择时间最短路径，这种调度模式可以使乘客在最短的时间内搭载到预约的出租车。

（3）作者刘丽在《基于出租车GPS数据的高效益寻客推荐策略研究》^[3]一文中研究了深圳市一万余辆出租车轨迹数据,分析影响出租车寻客效益的指标因素。在充分考虑载客热点区域出租车辆的供需关系和交通状况后,提出了一种出租车高效益寻客推荐策略,为出租车高效益寻客提供辅助决策支持。并且提出了出租车载客态单位时间收入及空载态寻客时间的效益指标模型。根据该模型,在对出租车GPS数据进行数据预处理及地图匹配的基础上,采用经典数理统计分析方法,对出租车高效益客源的时间空间分布特征进行了研究，为出租车载客热点推荐提供支撑。

国外研究现状：

（1）Arun Kumar Sangaiah等人在《Mining Efficient Taxi Operation Strategies From Large Scale Geo-Location Data》^[4]一文中着重对一年内收集的大规模历史出租车轨迹进行数据挖掘，从而提高效运营策略。 他们的方法对出租车服务进行了动态的观察，目的是最大程度地提高出租车利润率。他们提出重要指标，例如出行频率，热点和出租车里程，为更有效的运营策略提供有价值的见解。他们使用牛顿多项式插值和伽玛分布等技术来分析这些指标，了解它们的变化情况。他们的策略使用真实的出租车轨迹，通过控制每次行程的适当里程，可以预测不同时间段内出租车90.68％的乘坐率，并将出租车司机平均收入水平提高了19.38％。

（2）Fransiskus Tatas Dwi Atmaji等人在《Mining the GPS big data to optimize the taxi dispatching management》^[5]一文中通过挖掘出租车原始GPS大数据，提出首尔市出租车客流分布的基本信息。主要使用参数位置、时间和频率的多维分析来分析数据。普通出租车人数分布结果显示，江南区乘客人数最多，特别是在德黑兰街。并且特定区域，如东大门市场也为出租车载客提供了很大的贡献，当许多人出去购物时，约有25％的乘客乘坐出租车。乘车时间分析结果显示，30％的乘客在短时间内乘坐出租车仅限区内，不跨越其他地区。利用这些基本信息，出租车公司可以管理他们的出租车调度情况，以提升公司的服务水平。

1.3课题研究内容与预期目标

本文通过对滴滴出行的轨迹及订单数据的挖掘，发现城市出行热点区域及其随时间的变化趋势, 并将数据进行可视化处理。接着使用马尔科夫决策过程（MDP），探索出一种合适的车辆调度算法。一方面使空载出租车能快速搭载到乘客，另一方面使城市空载出租车的时空分布与乘客需求相匹配，在减少出租车空驶率的同时，减轻局部交通负担。其社会效益在于：实现节能减排、减轻道路拥堵、增加出租车公司的利润和驾驶员收入等^[6]。预期目标为完成数据的预处理；生成可视化界面；找到合适的聚类算法对轨迹点进行进一步的整合分析；最后应用MDP建立车辆调度模型。在有效缩短乘客等车时间、提高出租车的乘载率的同时，提升城市出租车的平均运行效率。

第2章 数据简介与预处理

2.1滴滴出行服务数据简介

本次实验所用到的数据均来自于滴滴出行实际脱敏数据资源，源于滴滴公司所推行的盖亚数据开放计划^[7]。项目具体内容为：依托于滴滴领先的大数据和技术优势，面向学术界提供真实的脱敏数据资源，以产学研深度融合推进交通领域的基础性与前瞻性研究和成果转化，提速智慧交通领域的科研发展，为社会发展创造更大价值。

数据集格式如下：

2.2 Pandas介绍及应用

2.2.1 Pandas简介

Python Data Analysis Library 或 Pandas 是基于NumPy 的一种扩展支持类库，该工具是专门针对于完成数据分析任务而创建的。Pandas 容纳了大量库和标准的数据模型，为高效地操作大型数据集提供了所需的工具。Pandas提供的大量高效便捷地处理数据的函数和方法，是使Python成为强大而高效的数据分析环境的重要因素之一^[8]。

Pandas 有自己独特的基本数据结构：（1）Series：一维数组。与Python基本数据类型List的区别在于，List中的元素可以是不同的数据类型，而Series只允许存储相同的数据类型，这样可以更有效的使用内存，提高运算效率。（2）Time- Series：代表以时间为索引的Series。（3）DataFrame：二维的表格型数据结构，可以将DataFrame理解为Series的容器，是Pandas中最常用的数据结构。（4）Panel ：三维数组，可以理解为DataFrame的容器。

2.2.2 Pandas在本次设计中的应用

作为操作数据集的重要支持工具，本次设计使用Pandas实现对数据文件的读取和写入；实现对数据的选择、排序、分类、去重和替换。详细介绍如下：

2.3 Pyecharts介绍及应用

2.3.1 Pyecharts介绍

Pyecharts 是一个用于生成 Echarts 图表的类库。Echarts 是百度开源的一个数据可视化JS库，由于其较好的可视化效果而受到广泛应用。Pyecharts 是为了与 Python 进行对接，方便在 Python 中直接使用数据生成图而创建的扩展支持类库^[9]

2.3.2 Pyecharts在本次设计中的应用

本次实验中应用Pyecharts（1）生成数据云图，将数据点显示在实际地图上 （2）生成统计图表，包括柱状图、折线图等（3）应用TimeLine得到数据点随时间变化的波动情况。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：