一种需求响应式货运公交与众包骑手协同取货动态调度方法

本发明涉及车辆调度及即时零售物流配送，具体为一种需求响应式货运公交与众包骑手协同取货的动态调度方法。

背景技术：

1、随着城乡差距缩小，以县镇及农村为主的下沉市场呈现巨大消费潜力与升级趋势。近年来，即时零售因高时效性受到广泛关注。据2024年统计数据显示，2023年我国即时零售市场规模同比增长28.9％，县域占比23.1％；农村网络消费零售额2.5万亿元，占农村消费品零售额38.9％，带动农村即时零售需求增长。目前，大型商超即时零售服务难以覆盖农村地区，社区团购仅支持次日达至乡镇自提点。2024年交通运输部提倡发展城市共同配送，畅通城乡物流末端，加快农村客货邮融合。本文聚焦城乡公交客货邮融合的前端取货问题，引入“共享经济”整合物流资源，由货运公父协同众包骑手统一收取城市内即时零售订单，配送至客货邮融合首末站，依托城乡公交完成农村末端配送，实现订单当日送达。

2、在农村即时零售订单的前端取货场景中，订单空间分布呈现明显的统计学“长尾”特征：既有位于干道路网周边大型商超、百货商场等大规模、需求稳定的订单，亦存在位于小巷、社区道路等支路便利店、药店等小规模、零散且波动性强的订单。现有研究主要面临以下难点：①单一配送模式下，货运公交服务全部站点导致大量绕行，运营成本高、时效性差；众包骑手单独取货虽灵活但承载能力有限，难以兼顾成本与效率；②多车协同取货时，车辆返程空驶率高，造成运力浪费，如何实现多车任务整合、降低空驶里程缺乏有效机制；③如何依据订单下单时间的随机分布，在发车前处理预约订单、发车后动态响应实时订单，实现静态规划与动态调整的高效协同，现有方法尚不成熟。

3、现有技术中，货运公交模式已在临沂等地运营，能有效解决短距离、小批量、多频次配送问题，但未充分考虑站点间货物量的分布差异，采用固定线路服务所有站点易导致低密度区域的不必要绕行。需求响应式公交兼具常规公交经济性与出租车灵活性，为前端取货提供了新思路，但直接应用于即时零售订单货运场景时，缺乏与灵活运力的协同机制。现有研究通常假设取货周期结束后车辆返回配送中心，未充分考虑车辆返程途中空驶成本，实际运营中若能利用固定站点进行订单合并，可显著节约行驶里程、提高满载率。

4、综上所述，现有技术尚未形成适用于农村即时零售订单的高效取货方案，存在服务效率低、运营成本高、动态响应能力不足等问题。因此，有必要结合即时零售订单的时空分布特征，合理规划取货线路以减少不必要的绕行路程，同时确保时效性，突破传统“点对点”返程模式，实现运力资源的跨周期协同优化。

技术实现思路

1、本部分的目的在于概述本发明的实施方式的一些方面以及简要介绍一些较佳实施方式。在本部分以及本技术的说明书摘要和发明名称中可能会做些简化或省略以避免使本部分、说明书摘要和发明名称的目的模糊，而这种简化或省略不能用于限制本发明的范围。

2、因此，本发明的目的是提供一种需求响应式货运公交与众包骑手协同取货的动态调度方法，以解决现有技术使得即时零售服务难以覆盖农村地区，社区团购仅支持次日达至乡镇自提点，农村居民难以即时享受即时零售服务，以提高取货效率、降低取货成本，实现农村地区“半日达”即时配送目标。

3、为解决上述技术问题，根据本发明的一个方面，本发明提供了如下技术方案：

4、一种需求响应式货运公交与众包骑手协同取货的动态调度方法，其特征在于，步骤如下：

5、s1、调度准备阶段

6、获取预约订单信息、需求站点位置、固定站点位置、货运公交额定载货量、全局时间窗参数。

7、s2、静态调度阶段

8、发车前，配送中心依据预约订单规划初始取货线路，并召集众包骑手协同取货。

9、s201、改进k-means聚类分区：基于预约订单空间分布，采用改进k-means聚类算法对需求站点聚类；以额定载货量为约束划分取货任务区域，确保每区订单总量不超过车辆额定载货量，确定初始发车数量。

10、s202、订单分配：生成货运公交基准路径，设置偏移距离阈值；基准路径阈值内站点由货运公交响应式取货，阈值外零散站点分配给众包骑手取货并送至最近固定站点。

11、s203、静态路径规划求解：构建以取货总成本最低为目标的静态路径规划模型；采用遗传-变邻域搜索算法求解初始取货路径，验证载货量与全局时间窗约束；不满足约束则增派车辆、重新分区，最终确定发车数量与初始调度方案。

12、s3、订单中转合并调度阶段

13、单辆货运公交作业时间较长，将取货任务拆分，由多辆车共同取货以提高时效。多辆车参与取货且各自有剩余载货量时，利用固定站点作为中转站以合并订单，卸货车辆直接返回配送中心，以提高满载率、降低空驶率。

14、s301、中转触发判断：若发车数量大于1，判断各货运公交剩余载货量；两车剩余载货量之和不超过单车额定载货量时，触发订单中转合并。

15、s302、备选中转站筛选：选取两辆货运公交最后服务的固定站点作为备选中转站，验证中转站合并是否满足全局时间窗约束。

16、s303、中转路径优化：采用遗传-变邻域搜索算法更新取货路径；两站均满足约束则按总成本选最优站，单一满足则选该站，均不满足则不中转。

17、s304、合并执行：订单合并至一辆货运公交，统一配送至城乡公交首末站；空载货运公交直接返回配送中心，避免空驶返程。

18、s4、动态调度与实时订单处理阶段

19、s401、实时订单采集：货运公交发车后，按固定时间间隔批量收集新增实时订单。

20、s402、车辆状态获取：获取各货运公交当前位置、剩余载货量、未服务预约站点信息。

21、s403、动态路径重规划：构建以当前周期总成本最低为目标的动态路径调整模型；采用遗传-变邻域搜索算法对剩余路径重优化。

22、s404、判断实时订单是否可插入剩余路径并满足全局时间窗、剩余载货量约束；满足则接受订单并更新路径，不满足则转为下一周期预约订单并施加拒单惩罚。

23、根据权利要求1所述的一种需求响应式货运公交与众包骑手协同取货的动态调度方法，其特征在于，步骤s2中，静态调度阶段的调度模型目标函数为：

24、min z＝z1+z2+z3    (1)

25、

26、

27、式中：α1是每辆货运公交启动固定成本；α2是货运公交单位距离运输成本；α3是众包骑手单位距离配送成本；众包骑手q从预约需求站点s取货后配送至固定站点g时，xsgq＝1，否则取0；｜k｜是配送中心货运公交规模；预约需求站点s由众包骑手q服务时，osq＝1，否则取0；tgq是众包骑手q到达固定站点g的时间；v是正无穷大实数；众包骑手q将订单取货后配送至固定站点g时，egq＝1，否则为0；tgk是货运公交k到达固定站点g的时间；是订单中转合并后直接返回配送中心o的货运公交到达中转站z的时间；货运公交中转合并订单时，否则为0；是订单中转合并后前往城乡公交首末站d的货运公交到达中转站z的时间；是货运公交kz服务的固定站点、预约需求站点和中转站的集合；是订单中转合并后前往城乡公交首末站d的货运公交到达首末站的时间。

28、式(1)为协同取货总成本z，包含3个部分：式(2)货运公交启动固定成本z1；式(3)货运公交取货运输成本z2；式(4)众包骑手协同取货成本z1；式(5)～式(16)为约束条件：式(5)保证发车货运公交数不超过配送中心货运公交规模；式(6)～式(9)表示站点只能由一辆货运公交或一名众包骑手负责取货；式(10)表示众包骑手取货后配送至固定站点；式(11)表示众包骑手早于货运公交到达固定站点；式(12)表示货运公交载货量约束；式(13)表示中转合并的货运公交订单总数不超过货运公交额定载货量；式(14)表示中转合并的货运公交到达中转站时间的同步；式(15)、式(16)保证订单中转合并后前往城乡公交首末站的货运公交满足时效性。

29、根据权利要求1所述的一种需求响应式货运公交与众包骑手协同取货的动态调度方法，其特征在于，步骤s201中，改进k-means聚类算法划分取货任务区域的具体步骤如下：

30、step 3.1：确定聚类数k。设定k值为发车数，即每个聚类簇安排一辆货运公交取货。

31、step 3.2：随机选择k个取货站点坐标作为初始簇中心，以额定载货量作为聚类规模。

32、step 3.3：优先分配至最近且剩余载量满足的簇，否则尝试次优簇。

33、step 34：完成所有站点簇分配后，计算各簇质心并更新为新的簇中心坐标。

34、step 3.5：重复步骤3、4，直到簇中心坐标不再变化，输出聚类结果。

35、根据权利要求1所述的一种需求响应式货运公交与众包骑手协同取货的动态调度方法，其特征在于，步骤s202中，预约需求站点分配的具体步骤如下：

36、step 4.1：确定虚拟固定站点

37、为提高取货效率并充分发挥货运公交的规模效应，对预约需求站点进行聚类处理，旨在查找分布集中的预约需求站点。在此基础上，进一步确定各簇对应的预约需求站点位置，生成虚拟固定站点位置并加以标记，以供后续生成货运公交基准线路。假设聚类簇内的预约需求站点坐标分别为(x1，y1)、(x2，y2)、…、(xn，yn)，依据质心法可得对应虚拟固定站点位置为得到虚拟固定站点集合ga。

38、step 4.2：统计固定站点和预约需求站点订单总数，确定初始取货车辆数b′：

39、step 4.3：划分货运公交取货任务区域

40、为减少路径重复，采用改进的k-means算法划分取货任务区域，使货运公交服务同簇内邻近站点，降低区域跨度。定义货运公交k负责的取货区域内的固定站点集合为gk，预约需求站点集合为skq，虚拟固定站点集合为gak。因此，固定站点集合预约需求站点集合虚拟固定站点集合此时每辆货运公交k取货区域内站点订单总数不大于货运公交额定载货量：

41、

42、step 4：分配区域内货运公交和众包骑手订单

43、以配送中心o和城乡公交客货邮融合首末站p为货运公交起点和终点，货运公交k基准路径站点集合wk＝{o}∪gk∪gk∪{p}，生成基准路径lk。货运公交k服务距离基准路径wkm以内的预约需求站点。若预约需求站点在货运公交k基准路径偏移范围外，由众包骑手取货送至最近的固定站点。

44、根据权利要求1所述的一种需求响应式货运公交与众包骑手协同取货的动态调度方法，其特征在于，步骤s3中，订单中转合并策略的具体步骤如下：

45、step 5.1若发车数量大于1，转入step 6.2；否则，保持当前取货路径等待发车。

46、step 5.2判断货运公交是否满足订单中转合并载货量约束。

47、商超装卸货场地资源有限，若多辆货运公交同时进行中转合并，易造成站点拥堵，增加额外管理成本。因此，假定中转合并在两辆货运公交间进行，即车辆k1和k2装载订单数为和pk，若pk+pk≤m，转入step 5.3，否则保持当前取货路径等待发车。

48、step 5.3判断货运公交进行订单中转合并操作是否满足送达时间窗约束

49、选择货运公交k1和k2最后服务的固定站点和作为备选中转站，依据实际情况采取相应决策。

50、根据权利要求1所述的一种需求响应式货运公交与众包骑手协同取货的动态调度方法，其特征在于，步骤s203、s303、s403中，遗传-变邻域搜索算法求解的具体步骤如下：

51、货运公交与众包骑手协同取货路径规划是np-hard问题，改进的k-means聚类算法能缩短求解时间，但随站点数量增加，精确算法求解导致搜索空间呈指数扩展，计算复杂度显著上升，适合采用启发式算法求解。遗传-变邻域搜索算法(genetic algorithm andvariable neighborhood search，ga-vns)结合遗传算法的全局搜索和变邻域搜索局部优化能力，能在较短时间内获得更优解并避免局部最优。

52、(1)遗传算法

53、采用自然数编码，站点排列顺序为取货顺序，依据编码规则随机生成初始种群。个体适应度设为目标函数的倒数。进行选择操作结合精英保留策略与轮盘赌法以保证优胜劣汰。因染色体首尾基因(配送中心和客货邮融合首末站或中转站)固定，故在第2至倒数第2个基因之间采用随机两点进行交叉与变异，得到新染色体后进行变邻域搜索。

54、(2)变邻域搜索

55、为弥补遗传算法局部搜索能力不足、扩大搜索空间，引入变邻域搜索算法，在当前解邻域内快速寻找局部最优解，每次迭代筛选高质量结果，逐步向最优解收敛，为增强其局部搜索能力，设计3种邻域结构。

56、(1)区间反转邻域n1：随机选取路径中的两个取货站点作为区间端点，将该区间内的所有站点的取货顺序逆向排列，调整局部取货顺序。

57、(2)节点插入邻域n2：随机选取路径中两个取货站点，将其中一个站点插入至另一个站点的前或后相邻位置。

58、(3)交换邻域n3：随机选择路径中两个取货站点，进行交换。

59、随机选择邻域结构对当前解扰动以防陷入局部最优，扰动后使用三种邻域结构进行局部搜索并评估新个体适应度：若优于当前最优个体则更新，否则保留最优并返回扰动继续迭代，达最大迭代次数后输出子代种群。采用精英保留策略合并父代与子代种群，按适应度排序筛选高适应度个体进入下一代，直至达遗传算法最大迭代次数。

60、7.根据权利要求1所述的一种需求响应式货运公交与众包骑手协同取货的动态调度方法，其特征在于，步骤s4中，动态调度阶段的调度模型目标函数为：

61、

62、式中，是未被取货的货运公交预约订单站点(固定站点和预约需求站点)集合；是货运公交响应的实时需求站点集合；是拒绝的实时需求站点集合；是未被取货的货运公交预约订单站点、响应的实时需求站点和正在取货车辆所在位置r的集合：α4是单位拒单惩罚费用；实时需求站点i被拒单为1时，否则为0；

63、式(17)最小化货运公交取货总成本，包含2个部分：式(18)货运公交运输成本；式(19)拒单惩罚成本；式(20)～式(26)为约束条件：式(20)和式(21)确保未取货站点及响应的实时需求站点均被取货；式(22)～式(26)是实时订单规划阶段的货运公交相关约束，含义可参见式(12)～式(16)。

64、与现有技术相比，本发明具有的有益效果是：

65、1、本发明依据订单空间分布特征，将零散订单交由众包骑手、高密度订单由货运公交集中处理，把取货任务分配权结合订单实际分布灵活划分，避免单一运力模式的局限性；省去为全部站点规划统一线路的复杂优化步骤，减少低密度区域绕行，规避因订单分布预测偏差、过度优化带来的成本增加与计算耗时过长问题。

66、2、本发明仅需设定偏移距离阈值、固定站点及需求站点坐标，通过改进k-means聚类快速划分任务区域、生成基准路径，精准匹配货运公交与众包骑手的服务范围；订单规模、站点位置、载货量及时间窗参数可根据农村订单分布特点、城乡物流运营条件动态调整，适配不同县域、乡村的即时零售取货场景，普适性与可落地性强。