利索能及
我要发布
收藏
专利号: 202110222684X
申请人: 湖南师范大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-10-14
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

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算法的网约车调度方法,其特征在于,每个网格的左下角点经纬度、右上角点经纬度,即可获取该区域内实时路况数据,针对每个网格路况按照其严重拥堵、缓行、畅通优先级确定该区域的实时路况状态,为确定时间影响因子提供依据。