融合时空耦合聚类与状态压缩动态规划的城际定制客运调度方法及系统

摘要: 本技术涉及智慧交通,特别是涉及融合时空耦合聚类与状态压缩动态规划的城际定制客运调度方法及系统。背景技术:1、随着城市群一体化发展和跨城通勤需求不断增长,中短途城...
融合时空耦合聚类与状态压缩动态规划的城际定制客运调度方法及系统

本技术涉及智慧交通,特别是涉及融合时空耦合聚类与状态压缩动态规划的城际定制客运调度方法及系统。

背景技术:

1、随着城市群一体化发展和跨城通勤需求不断增长,中短途城际客运已成为综合交通体系的重要组成部分。传统城际客运采用固定站点、固定班次运营模式,存在灵活性不足、满载率低及运营效率不高等问题;而铁路运输和网约车等方式则分别存在接驳不便或出行成本较高的问题。因此,能够根据乘客需求动态组织运力的定制客运逐渐成为城际出行的重要补充。

2、然而,现有定制客运调度方案大多未充分考虑订单上下车点的时空关联性、城际出行的方向性特征以及大规模订单场景下的计算效率问题,容易导致车辆绕行严重、搜索空间过大和运营收益下降。同时,现有研究多以距离最短或成本最低为优化目标,对客运企业运营利润与乘客服务质量的协同优化考虑不足。

技术实现思路

1、基于此,有必要针对上述技术问题,提供一种智能化调度水平更高的融合时空耦合聚类与状态压缩动态规划的城际定制客运调度方法及系统。

2、本发明提供融合时空耦合聚类与状态压缩动态规划的城际定制客运调度方法,包括:

3、s1:获取定制客运乘客订单信息;

4、s2:根据定制客运乘客订单信息基于时空耦合聚类的订单需求聚合;构建融合空间距离与时间距离的时空综合距离度量对订单进行聚类,形成逻辑站点;

5、s3:以逻辑站点质心作为虚拟站点,检索候选公交站点,并结合地图路网距离计算,完成虚拟站点与真实站点的匹配映射;

6、s4:根据定制客运乘客订单信息构建滚动时间窗,对时间相近且空间可兼容的订单进行班次聚合,形成候选发车任务;

7、s5:根据定制客运乘客订单信息中订单起终点所在区域及主流出行方向,对候选发车任务进行方向一致性划分;并依据空间绕行边界和时间窗边界,对明显不可行的候选任务进行前置过滤得到待选发车任务;

8、s6:以定制客运服务综合效用值最大化为目标,构建包含总收入、总行驶成本、总用户侧时间惩罚的优化模型;

9、s7:根据待选发车任务以及包含总收入、总行驶成本、总用户侧时间惩罚的优化模型进行客运调度。

10、进一步地,在步骤s2中,具体为:

11、s2.1:构建融合空间距离与时间距离的时空综合距离度量,用历史数据对调度参数进行闭环微调,时空综合距离度量定义为:

12、

13、其中,是订单与订单上车点之间的地理距离,为两者预约时间的绝对差值,、为归一化因子,、为权重系数,通过历史数据闭环微调;

14、s2.2:canopy 粗聚类:利用 t1、t2 阈值快速划定需求池,减少计算量并避免死循环,定义为:

15、

16、其中,。

17、s2.3:在完成需求池构建后,对未能进入任何需求池的订单判定为候选孤立订单,引入量化权衡接驳孤点的额外绕行成本和订单人数的孤点接纳系数,并计算孤点接纳系数,定义为:

18、

19、其中,是订单人数,是接纳该孤点预计增加的绕行距离,、是调节系数;

20、当时,保留该孤点作为独立需求单元参与后续调度;否则予以舍弃。

21、s2.4:在每个 canopy 内部寻找几何质心μ,生成虚拟站点坐标,定义为:

22、

23、其中,是簇的几何质心,作为虚拟站点的坐标。

24、进一步地,在步骤s4中,具体为:

25、s4.1时序排序:将所有虚拟站点按平均出发时间升序排列;

26、s4.2动态窗收纳:采用 time_window进行一维滚动聚类,将每内的所有站点需求合并至同一班次池 。

27、s4.3约束过滤:剔除已分配订单并校验,确保班次具备运营盈利性。

28、进一步地,在步骤s5中,根据定制客运乘客订单信息中订单起终点所在区域及主流出行方向,对候选发车任务进行方向一致性划分具体为:

29、s5.1四维特征耦合:提取订单经纬度与预处理得到的方向向量;

30、s5.2特征矩阵构建定义:

31、

32、其中,、是订单上车点的经纬度坐标,是订单出行方向向量,、是权重系数,用于平衡空间位置与方向特征的重要性;

33、s5.3k-means++ 任务分裂:计算需派车辆 k = [总人数/容量数];在四维特征空间执行k分类,将顺路的订单分给同一辆车。

34、进一步地,在步骤s5中,依据空间绕行边界和时间窗边界,对明显不可行的候选任务进行前置过滤得到待选发车任务具体为:

35、s5.1空间防绕行剔除:基于haversine公式与行驶方向角,提前评估站点间的空间拓扑关系;若接送点序列的连线严重背离跨城主干线,则直接剪枝;

36、s5.2时间窗界限阻断:校验任意两节点间的预计行驶耗时;若节点的最短到达时间已超出乘客可容忍的极端等待时间窗,则在状态空间矩阵中直接将该边权重设为无穷大,从源头阻断无效状态分支的生成。

37、进一步地,在步骤s6中,具体为:

38、s6.1分阶段增量效用精算:算法将全路径转移分解为两个有序子序列。令起点城市逻辑站点集,为终点城市逻辑站点集。

39、接人阶段:从起点o出发,在中寻访问顺序最优,止于高速入口,状态转移记为:

40、

41、送人阶段:从高速出口出发,在中寻访问顺序最优,止于终点,状态转移记为:

42、

43、(3)跨城连接点:接人段的终态作为送人段的初始成本,即:

44、

45、其中为跨城高速公路的通行成本(含路桥费与油耗)。

46、s6.2核心递推机制:为了降低计算复杂度,直接嵌入单目标函数u,采用效用增量u进行累加:

47、(1)单目标函数u:以服务综合效用最大化(总收入-总行驶成本(固定成本+变动成本)-时间窗惩罚成本)为目标,定义为:

48、

49、展开为:

50、

51、其中:是订单r的单价,是订单人数,是单车固定运营成本,是派车数量,是每公里变动成本,为维护成本,为路桥费,是站点到站点的行驶距离,是车辆k是否从行驶到的决策变量,是时间窗惩罚权重系数,是混合时间窗惩罚函数定义为:

52、

53、其中早到和晚到的惩罚系数。

54、(2)单步效用增量,每增加一个站点,仅需计算该站点的新增收入扣除当前路段的变动成本与时间窗惩罚成本,定义为:

55、

56、其中,是站点i上车乘客的总票务收入,是单位距离变动成本,是站点到站点的行驶距离,是时间窗惩罚系数,是因到达时间偏差产生的时间惩罚值。

57、(3)全局状态转移,利用位掩码记录已服务的站点集合,通过增量累加最终实现全局服务综合效用u的最大化,定义为:

58、

59、其中,是当前最后一个访问的站点,是上一个访问的站点。

60、s6.3约束驱动的算法剪枝:在状态转移过程中,将乘客等待时间窗、绕行系数、车辆载客容量、订单唯一性服务及车辆进出平衡等约束嵌入搜索过程;其中,超过极限容忍时间窗的路径直接剪枝,而允许范围内的等待偏差通过目标函数中的时间窗惩罚成本进行优化。

61、进一步地,s6.3约束驱动的算法剪枝具体为:

62、(1)乘客等待时间窗约束:车辆到达站点 j 的时刻必须满足乘客的耐心边界。定义为:

63、

64、其中,是最大可容忍等待时间;

65、(2)绕行系数约束:定义乘客的实际行驶距离与最优距离的比值,确保绕行在可接受范围内;定义为:

66、

67、其中,是最大绕行系数;

68、(3)载客量与最低发车人数复合约束:单车容量上限与盈利底线,定义为:

69、

70、其中,是最低发车人数,是车辆最大载客容量;

71、(4)订单唯一性服务约束:确保每个被接纳的订单只被服务一次,不重复派车,定义为:

72、

73、(5)基于固定和弹性互补的发车策略约束;

74、(6)流向偏离上限:

75、

76、其中,是订单的出行方向向量,是车辆k当前行驶路段的方向向量。

77、进一步地,基于固定和弹性互补的发车策略约束具体为:

78、触发并入固定班次:若存在一个固定班次,其预设发车时间为,且满足:

79、

80、其中,是时间窗阈值,则将订单并入固定班次。

81、触发创建弹性班次:对于所有的情况,为该需求开辟一个新的弹性班次集合,其预设发车时间变为优化决策变量,需满足订单本身的弹性时间窗:

82、

83、其中:

84、

85、即取当前任务池中最早订单的预约时间作为弹性班次的时间基准。

86、进一步地,在步骤s7中,具体为:

87、s7.1容量分裂:若任务池人数超过载客容量 q,根据原则自动筛选最优订单子集优先派车,实现任务分裂;

88、s7.2发车指令触发:当最优路径对应的服务综合效用值时,表明该方案的综合效用为正,即票务收入足以覆盖运营成本与服务质量惩罚,具备发车价值;,则取消该次发车任务以规避运营亏损或服务质量不达标。

89、此外本发明提供融合时空耦合聚类与状态压缩动态规划的城际定制客运调度系统,包括:

90、获取模块:获取定制客运乘客订单信息;

91、逻辑站点构建模块:根据定制客运乘客订单信息基于时空耦合聚类的订单需求聚合;构建融合空间距离与时间距离的时空综合距离度量对订单进行聚类,形成逻辑站点;

92、映射模块:以逻辑站点质心作为虚拟站点,检索候选公交站点,并结合地图路网距离计算,完成虚拟站点与真实站点的匹配映射;

93、候选发车任务模块:根据定制客运乘客订单信息构建滚动时间窗,对时间相近且空间可兼容的订单进行班次聚合,形成候选发车任务;

94、前置过滤模块:根据定制客运乘客订单信息中订单起终点所在区域及主流出行方向,对候选发车任务进行方向一致性划分;并依据空间绕行边界和时间窗边界,对明显不可行的候选任务进行前置过滤得到待选发车任务;

95、优化模块:以定制客运服务综合效用值最大化为目标,构建包含总收入、总行驶成本、总用户侧时间惩罚的优化模型;

96、调度模块:根据待选发车任务以及包含总收入、总行驶成本、总用户侧时间惩罚的优化模型进行客运调度。

97、本发明构建融合空间距离与时间距离的时空综合距离度量,对定制客运订单进行聚类,形成逻辑站点;同时对孤立订单进行保留或剔除决策,实现大规模订单的自适应聚合与需求整合,并进一步通过虚拟站点到真实公交站点的精确映射,有效降低后续路径优化的问题规模。