专利摘要

专利摘要

本发明公开了一种基于改进Dijkstra算法的网约车调度方法，首先获取指定区域内路网数据、POI数据、出租车行程GPS数据和实时路况数据；其次，选取了经典的Dijkstra算法，并在其基础上调整权重，把路网距离影响因子和基于实时路况的时间影响因子综合考虑，形成新的乘客需求与司机匹配策略；最后，依据POI数据与出租车行程GPS的综合数据产生随机乘客与司机分布，为每一个随机产生的乘客设定一个调度范围，通过改进Dijkstra算法在调度范围中进行司机和路径搜索，得到兼顾乘客、司机和网约平台三者利益的最优化路径。本发明有效地提高了司机的利用率，平台的接单率，以及减少了乘客的等待时间。

权利要求

1.基于改进Dijkstra算法的网约车调度方法，其特征在于，包括以下步骤：

S1、获取指定区域内路网数据、POI数据、出租车行程GPS数据和实时路况数据；

S2、基于Dijkstra算法，在权重中添加路网距离影响因子和基于实时路况的时间影响因子，形成改进Dijkstra算法；

S3、依据POI数据与出租车行程GPS的综合数据产生随机乘客与司机分布，为每一个随机产生的乘客设定一个调度范围，通过改进Dijkstra算法在调度范围中进行司机和路径搜索，得到兼顾乘客、司机和网约平台三者利益的最优化路径。

2.根据权利要求1所述的基于改进Dijkstra算法的网约车调度方法，其特征在于，所述路网数据通过Open Street Map下载至路网osm文件中，且路网数据中的点集与边集都是采用墨卡托投影坐标系，将墨卡托投影坐标系转换为GCj-02坐标系统，得到转换后路网交叉点集和转换后路网边集。

3.根据权利要求2所述的基于改进Dijkstra算法的网约车调度方法，其特征在于，所述转换后路网交叉点集由Allid栏、lon栏和lat栏组成，Allid栏表示全地图中的节点ID，lon栏表示节点经度，lat栏表示节点纬度；所述转换后路网边集由id栏、newStart栏、newEnd栏、length栏和freespeed栏组成，id栏表示全地图中的边ID，newStart栏表示起点的节点Allid，newEnd栏表示终点的节点Allid，length栏表示边权值，即路段的长度，单位为米，freespeed栏表示最高限速，单位为米每秒。

4.根据权利要求1所述的基于改进Dijkstra算法的网约车调度方法，其特征在于，所述POI数据使用爬虫技术从现有的APP地图软件上获取得到，每条POI数据包括经度、纬度、namePOI名称、地址、省份、城市、商业区域、big_type、meddle_type和small_type；所述出租车行程GPS数据至少包含车辆id、设备号、方向角、GPS经纬度；通过综合POI数据与出租车行程GPS数据，获得指定区域内人群分布以及人流量的汇总集合，将地图进行路网分割，分割成1km*1km的网格，其中，网格中数据量越大，则表明该区域的人流量及人口密度越大。

5.根据权利要求4所述的基于改进Dijkstra算法的网约车调度方法，其特征在于，所述实时数据通过利用现有的APP地图软件API提供的交通态势接口，使用python爬虫技术获取得到。

6.根据权利要求1所述的基于改进Dijkstra算法的网约车调度方法，其特征在于，所述兼顾乘客、司机和网约平台三者利益的最优化路径具体为平台接单成功率高，乘客等候时间短，司机空载时间与距离小的路径。

7.根据权利要求1至6中任一项所述的基于改进Dijkstra算法的网约车调度方法，其特征在于，所述步骤S3具体表现为：

以一个随机产生的乘客为原点在调度范围内进行搜索，计算出调度范围内所有司机中距离最短的司机的距离，计算在当前路况下预计到达时间最短的司机的时间，根据公式（1），计算出每一位司机的综合权重，并根据司机的综合权重大小，选择所有司机中综合权重最大的那一位司机接单派送：

（1）

式中，为第i个司机距离原点乘客的距离，为第i个司机在当前路况下到达原点乘客的预计抵达时间，为第i个司机的综合权重，A为路网距离影响因子，B为时间影响因子，其中，的表达式如下：

（2）

其中，Lm为第i个司机接送乘客的路径中第m段道路的长度，Sm为第i个司机接送乘客的路径中第m段道路的限速，Rsm为第i个司机接送乘客的路径中当前的拥堵情况，n表示司机接送乘客的路径中的道路总段数。

8.根据权利要求5所述的基于改进Dijkstra算法的网约车调度方法，其特征在于，每个网格的左下角点经纬度、右上角点经纬度，即可获取该区域内实时路况数据，针对每个网格路况按照其严重拥堵、缓行、畅通优先级确定该区域的实时路况状态，为确定时间影响因子提供依据。

基于改进Dijkstra算法的网约车调度方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。