基于无人机——骑手协同模式的即时配送优化研究

摘要

针对即时配送高峰期效率瓶颈，提出无人机—骑手协同配送模式。构建带时间窗的混合整数规划模型，设计改进遗传算法：通过构造启发式算法生成初始解，采用双点交叉算子和成对交换变异算子增强搜索能力，结合局部搜索提升收敛速度。算例实验表明，协同模式较传统配送成本降低38.1%，有效缓解骑手工作负荷与时间窗违约风险。

关键词

即时配送；无人机—骑手；协同配送；改进遗传算法；路径优化问题

Abstract

Aiming at the efficiency bottleneck during the peak period of instant delivery, a drone-rider collaborative distribution mode is proposed. A hybrid integer programming model with a time window is constructed, and an improved genetic algorithm is designed: the initial solution is generated by constructing a heuristic algorithm, and the search ability is enhanced by using a two-point crossover operator and a pairwise exchange mutation operator, and the convergence speed is improved by combining with local search. Numerical example experiments show that the collaborative mode reduces the cost by 38.1% compared with traditional distribution, which effectively alleviates the risk of rider workload and time window default.

Keywords

Instant delivery；Drone-rider； Cooperative delivery；Improved genetic algorithm；Path optimization problem

1 引言

近年来，电子商务的迅猛发展推动即时配送市场的快速扩张。2023年，中国即时配送市场规模达15254亿元，用户增至5.45亿人，未来几年仍将增长[1]。艾瑞咨询预计，全球即时配送市场将以两位数年复合增长率增长，2030年达到3.6万亿美元[2]。

随着外卖市场规模扩张引发高峰期问题：高峰期订单激增导致运力不足、成本上升及骑手违规。企业探索无人机配送作为补充方案，如美团通过无人机航线缩配送时40%[3]，京东/顺丰同步优化运力。因此，无人机协助骑手成为潜力方案，但因订单时效严苛、地理分散及骑手动态性，高效路径规划面临挑战。

即时配送属车辆路径问题拓展，需在规定时限完成“取货—送货”全流程。按订单量可分为两类模式：一对一配送（如医疗用品取送[4]）与并发订单配送（外卖高频场景）。学者们聚焦路径优化与动态响应：徐菱等[5]建立需求可拆分模型提升响应效率；陈萍等[6]融合客户满意度指标改进算法；Ulmer[9]针对出餐随机性构建马尔可夫决策模型；Yildiz等[10]开发订单打包的混合整数规划模型；Reyes[11]则提出增量禁忌搜索算法增强求解能力。

无人机配送研究聚焦协同模式创新。Murray和Chu[12]开创车辆—无人机协同框架，提出FSTSP（车载平台）与PDSTSP（仓库平台）两类基础问题。学者们在此基础上持续拓展：吴廷映等[13]研究可收派件协同路径；Zhang等[14]构建多目标优化模型；颜瑞等[15]探索限行禁飞约束下的配送方案；Poikonen等[16]突破单机约束研究多无人机调度。

即时配送研究在路径优化与成本控制方面虽取得进展，但应对高峰期运力不足及复杂场景时存在明显局限。现有方案主要通过增加骑手数量或提升单骑手订单量补充运力，但高峰期与交通高峰重叠，传统配送易因拥堵导致延迟，大幅增加时间窗惩罚成本。而提高单骑手订单量易引发过度劳累增加配送事故风险。

本文提出一种无人机—骑手协同配送模式，引入无人机作运力补充，利用其快速响应与绕过拥堵的能力缓解效率瓶颈。该模式优先将客户点分配给无人机处理短途高时效订单，骑手服务超出无人机范围的订单，通过设定最大服务点数降低疲劳配送风险。无人机与骑手协同提升配送效率，也减少交通延误带来的惩罚成本，同时减轻骑手工作强度与安全隐患。为实现该模式，本文针对商圈配送特点设计虚拟节点处理方法，并结合时间窗约束建立优化模型。提出改进遗传算法，采用构造启发式初始解、双点交叉算子等提升求解质量。实验表明，该协同模式在高峰期显著降低配送成本达38.1%，为即时配送可持续发展提供有效解决方案。

2 问题描述与数学模型

2.1问题描述

本文研究的即时配送问题如图1所示：骑手从配送中心出发服务取货点和客户点，遵循“先取后送”规则；无人机从机场完成取货后配送并返回。图中内圈为商圈范围，外圈为无人机服务范围，机场设于商圈中心。服务范围内客户点可由骑手或无人机配送，范围外仅由骑手配送。采用软时间窗约束，超时产生惩罚成本。对于取货点服务多客户点情况，采用虚拟节点（如109）处理。为保障骑手权益，限制其最大服务客户数。

图 1“无人机—骑手”协同配送模式下的车辆路径优化问题示意

2.2模型假设与符号定义

2.2.1模型假设

根据实际配送过程，设定以下假设：（1）客户、商家及配送中心的位置与距离已知，客户时间窗和需求量已知；（2）骑手、无人机及取货员速度恒定；（3）仅考虑运输时间，忽略备餐、取餐和交付等待时间；（4）忽略货物重量对无人机性能的影响；（5）骑手不受载重限制，仅约束其最大服务客户数。

2.2.2符号定义

本文模型所需符号的定义如表1所示。

表1模型符号定义表

2.3数学模型

本文基于混合整数规划法构建了以下数学优化模型：

式（1）为目标函数，最小化总配送成本，包括骑手、无人机和取货员的路径成本及时间窗惩罚成本；式（2）确保所有客户点均被服务；式（3）和式（4）定义无人机服务节点标记与限制；式（5）为骑手服务客户点数上限；式（6）和式（7）保证取货点与对应客户点服务一致性；式（8）计算时间窗惩罚成本；式（9）~（11）为骑手、取货员和无人机的路径返回约束；式（12）~（14）为进出守恒约束；式（15）和式（16）为先取后送约束；式（17）为0~1决策变量约束。

3 算法设计

无人机—骑手协同配送属NP-Hard问题，传统遗传算法存在不可行解多、局部搜索弱等缺陷。本文提出改进遗传算法(IGA)：（1）构造启发式初始解优先分配无人机订单；（2）双点交叉算子保持路径连续性；（3）成对交换变异维持“先取后送”规则；（4）局部搜索优化短途—长途协同路径。改进遗传算法的具体流程图如下：

图 2 改进遗传算法流程图

3.1解的编码

本文设计的改进遗传算法采用自然数编码，操作如下：首先将客户点随机排列；然后以骑手最大服务客户点数为间隔（这里设置为4），插入0节点进行分割，来表示不同骑手的服务节点；最后，将取货点插入其对应的客户点前面，完成染色体的编码。

图 3 染色体编码示意

3.2构造启发式算法

本文算法思路如下：考虑无人机配送模式成本上的优越性，优先将可分配给无人机的客户分配给无人机配送以降低配送成本；而后将未被分配给无人机的客户指派骑手配送；最后按照染色体的编码方式，采用随机生成的方法得到初始解。本文对于取货员最优路径的求解采用最近邻算法。

伪代码如图4所示：

图 4构造启发式算法伪代码

3.3选择算子

在算子的选择上，本文采用精英保留策略和轮盘赌策略。

3.4双点交叉算子

本文在交叉算子的选择上，采用双点交叉算子，采用前向交叉方法，具体操作如图5所示：

图 5双点交叉算子示意

3.5成对交换变异算子

针对即时配送中取货点与客户点配对的特点，传统变异算子易产生大量不可行解。为此，本文设计成对交换变异算子：随机选取两取货点及其对应客户点，交换取货与客户点组合，生成新子代。该方法在增强解多样性的同时，显著减少不可行解产生。

3.6修复算子

在修复算法运行前，需评估染色体的可行性。本文设计的改进遗传算法在交叉变异时采用双点交叉，这可能导致部分子代染色体违反“先取后送”或“同骑手服务”约束。为此，本文设计修复算子，通过交换、删除和插入节点来修复不可行染色体。修复算子流程如下：①可行性评估：检查子代染色体是否满足约束。②节点调整：将不可行节点进行删除、插入操作。③顺序修复：检查每对客户—取货点顺序，若不符则交换位置。

3.7局部搜索算子

本文改进遗传算法时加入了局部搜索算子，以概率选择染色体进行精细搜索，提升解质量与收敛速度。以染色体c1为例：先按0节点分割为片段c11、c12；分别提取各片段内的客户点和取货点；将取货点随机排序后插入，再插入对应客户点（确保位于取货点之后）；最后合并片段，获得新染色体c2。

4 实验分析

本文使用所有算法部分的设计通过MATLAB进行编写，使用版本为MATLAB2020b，在Windows 10 系统下运行。电脑处理器为Intel(R)Core(TM) i5-8250U ，有1.60 GHz 和8.00 GB RAM内存。

4.1算例设计

为验证无人机—骑手协同配送模型和改进遗传算法的有效性，本文基于三种规模的15组算例进行实验。数据来自美国外卖公司与佐治亚理工学院2018年公开在GitHub上的算例集，本文进行改进，使其适用本文所研究无人机-骑手协同配送问题。本文使用三组不同订单规模的算例组，每组算例包含五组独立的小算例。instance20_1到instance20_5订单规模为20，instance35_1到instance35_5订单规模为35，instance50_1到instance50_5订单规模为50。

算例参数设置如表2所示。

表2 算例参数信息表

4.2算例实验

为测试算法性能，本文使用改进遗传算法进行数学模型求解，为综合评价算法性能，本文还使用传统遗传（GA）算法与贪婪算法在15组算例下进行对比实验。

改进遗传算法与GA算法参数设置相同，本文设置种群规模 N=100，交叉概率pc= 0.9，变异概率pm= 0.1为两种算法的输入，对于改进遗传算法局部搜索概率ps= 0.1，模拟退火策略初始温度T0 = le5，降温速率q=0.6，精英个体保留概率m=0.2，两算法迭代次数均设置为800次。

表3为各组实验下优化情况总体汇总，由该表可以看出，客户规模分别为20、35、50时，改进遗传算法比遗传算法求解时间分别缩短8.2%、5.7%、4.8%；总成本求解上，改进遗传算法在三个算例规模上比GA算法分别降低了26.4%、38.4%、32.1%，比贪婪算法分别降低了41.6%、52.9%、41.7%。这表明本文设计算法实现了更好的优化效果，迭代速度相较传统遗传算法更快。

表3 各算例结果整合表

为更好展示改进遗传算法的优化表现，本文以instance20_1、instance35_1和instance50_1为例，绘制了改进遗传算法与遗传算法在优化目标上的收敛表现。如图6-图8可以看出改进遗传算法相较于传统的遗传算法在求解无人机-骑手协同配送问题时，在优化表现上更好，并且具有更强的跳出局部最优能力。

图6 instance20_1迭代对比图 图7 instance35_1迭代对比图

图8instance50_1迭代对比图

4.3模式对比

以实例instance35_1分析无人—骑手协同与传统配送模式成本，由表4和表5可知，协同模式显著降低成本并优化线路。该模式将远距离或高时效订单交由无人机完成，减轻骑手负荷，缩短配送时间，高峰期可灵活扩展运力，在效率和经济性上具有明显优势，适用于复杂场景。

表 4传统模式下骑手配送方案

表 5无人机-骑手协同配送模式下配送方案

表 6 配送效果对比分析

由表6可知，无人机—骑手协同配送模式较传统模式成本降低38.01%。该模式下，骑手路径成本与时间窗惩罚成本得到优化：无人机分担配送任务，减少骑手长途奔波，降低路径成本；同时无人机高效覆盖提升了准时配送率，减少了延迟惩罚。该模式通过资源优化配置，实现了效率与成本更优平衡。

5 结论

面对电子商务快速增长所带来的城市末端配送需求压力，本文提出了一种无人机与骑手协同的即时配送模式，并构建了以成本最小化为目标的混合整数规划模型。为解决该优化问题，设计了一种改进遗传算法，在不同配送场景下实现配送效率和成本的平衡。通过无人机和骑手的协同优势，模型在路径优化和运力配置上取得了显著提升。

算例实验结果表明，在城市场景中，无人机-骑手协同模式在配送效率和成本控制方面表现出显著优势。与传统骑手模式相比，协同模式能降低约38%的配送成本，在高峰期有效提升响应速度，降低时间窗惩罚成本，改善客户服务体验。

本研究尚有不足，如假设无人机续航不受载重影响，但实际上续航会随载重增加而下降；商家出餐时间存在不确定性；未来可研究订单需求、配送路况不确定条件下的配送模型构建。

作者简介

牛国栋，武汉科技大学硕士研究生

王鑫鑫，武汉科技大学管理学院教授

参考文献