应急物资的无人机与车辆并行在线配送问题

余海燕，苟梦圆，吴腾宇

1.重庆交通大学 经济与管理学院，重庆 400074

2.重庆口岸物流与航运发展研究中心，重庆 400074

3.智能物流网络重庆市重点实验室，重庆 400074

4.重庆邮电大学 经济管理学院，重庆 400065

疫情的高传播性使部分地区加强了道路管控措施，物资配送严重受阻，对于医药等应急物资如何高效、准确、安全地配送已是当务之急。其间无人机在“最后一公里”药物配送中获得亮眼表现，可见无人机在应急物资配送中的适用性。但是，无人机存在飞行半径有限等短板，将其与车辆进行组合配送更适应现实场景。除此之外，在现实应急配送场景中，决策者往往必须在对未来一无所知或部分信息未知的情形下进行对全局有影响的决策。因此，需求产生的突发性、高度不可预见性及不确定性是应急物资配送难以组织实施的重要原因之一。然而，当前无人机与车辆并行配送领域中对需求不确定性研究较少，将此类动态因素引入车辆无人机并行配送问题，是该问题可行且有价值的发展方向。

考虑需求实时不确定性产生情形下的车辆无人机并行配送问题可以用车辆无人机并行在线配送问题描述。与一般车辆无人机并行配送问题相比，应急配送需求序贯出现，服务器只能实时获知其相关信息，因此具有在线性。与一般车辆在线配送问题相比，无人机配送范围有限、一单一送，且需考虑无人机与车辆之间协调问题。因此，提出车辆无人机并行在线配送问题。

对于车辆无人机并行配送问题，Chung 等[1]将目前该问题所涉及算法进行了归纳，发现多以车辆为主无人机为辅构建配送网络，并设计相应的离线算法。Murry和Chu[2]将车辆无人机并行配送问题定义为PDSTSP（parallel drone scheduling traveling salesman problem）问题，并设计了车辆优先配送需求的启发式算法。Dell’Amico 等[3]以总时间最小化为目标，提出了以分支定界算法为主的迭代启发式算法。Nguyen 等[4]研究了以最小化总运营成本为目标的车辆无人机并行配送路径优化问题。Saleu等[5]采用迭代两步启发式算法求解，通过双准则最短路径问题解码及动态规划实现。总体而言，此问题相关研究大多建立在所有信息已知的情形下，与现实场景中应急需求信息未知不符。除此之外，研究大多构建以车辆为主的配送网络，现实场景中应急需求未知且紧迫，优先考虑无人机配送能明显减少单个需求点的等待配送时间，因此考虑动态因素并设计无人机优先的在线算法具有现实意义。

对于车辆无人机并行配送问题涉及未知需求方面，任璇等[6]进行了文献归纳总结。Ulmer 和Thomas[7]研究了需求在一天中任意时间释放的“当日达”问题，采用了动态规划进行解决。王新玉和赵志明[8]指出即时重优化也是常见的求解策略，通过基于最坏情形考虑的竞争分析法能有效、可靠度量动态问题的求解策略性能，且动态问题的解决方案不应该是静态输出，而是根据新到达的服务需求与系统当前状态决定执行哪些调度操作。在线算法正是基于此思想进行策略设计，在线分析法则是围绕所设计在线策略进行系统评估的方法。设计相应的在线算法并通过在线分析法进行算法优劣性衡量能够有效解决需求信息未知的现实问题。

在Sleator和Tarjian[9]正式提出在线问题及在线分析法后，在线配送问题开始受到关注。车辆与无人机并行在线算法的研究重点在于需求分配及路径规划，这一方面可通过在线理论进行分析处理。Ausiello等[10]最早使用在线理论分析TSP（traveling salesman problem）问题，证明得出一般网络上Eventually Replan算法竞争比为2。马卫民和王刊良[11]证明局内封闭式车辆调度问题车辆数为1 时重新计划策略的竞争比为3.5。戴敏等[12]证明局内开放式多车辆调度问题重新计划策略的竞争比为3.5。Jaillet 和Lu[13]研究具有实时服务可选择性的在线旅行商问题，并证明所提出策略在正半轴竞争比为2.5。马军平等[14]提出具有服务时长和服务可选择性的车辆调度问题，并设计了相应的在线算法。吴腾宇等[15]运用在线分析法衡量了非对称网络下JPⅠ-rd（judge the path increment with release date）等算法的性能。与现有的车辆在线调度问题研究不同，车辆无人机并行在线配送问题还需考虑无人机不同于车辆的特性，如装载量、速度、服务范围等。

综上所述，将车辆与无人机并行配送应用于应急配送领域是有效且可行的。通过与现有研究比较可知（见表1），车辆与无人机并行配送领域的算法研究有一定基础，但针对需求不确定性考虑较少，与现实场景结合不够紧密，设计相应的在线算法具有现实意义，且如何设计相应的在线算法，衡量算法的性能及适用性，目前尚未有相关的研究。

表1 车辆无人机并行配送问题研究对比Table 1 Research comparison of truck-drone parallel delivery problem

基于此，本文研究在需求实时产生的情况下，如何分配需求并规划路径使得最长配送时间尽可能少的车辆无人机并行在线配送问题。该问题可通过在线分析法有效解决。首先给出问题描述和基本定义，然后通过竞争分析得出所研究的在线问题下界及所设计在线均衡策略竞争比，从而衡量在线均衡策略的性能；通过建立离线问题模型，设计离线算法，运用MATLAB 将CPLEX 最优解与离线算法结果进行比较，为在线均衡算法内容作支撑；通过对在线均衡算法的仿真分析，验证在线均衡算法的有效性。

1 符号说明及问题描述

1.1 符号说明

V：网络顶点集合，V={x0,x1,…,xk} ；

E：网络边集合，E={e0,e1,…,ek} ；

d(u,v)：顶点u,v间边的权，其中u,v∈V；

G：配送网络，G=(V,E)，以配送站作为原点，原点唯一令其为顶点o∈V，网络满足u,v,w∈V,d(u,v)+d(v,w)≥d(w,u)；

ri：两元数组，ri=(ti,xi)，代表在ti时刻于xi处产生需求，其中ti表示服务请求的发布时间，xi表示服务请求的发布位置；

R：需求组成的序列集合，R={r1,r2,…,rm} ，其中需求按释放时间先后排列；

I：需求序号集合，I={1 ,2,…,n} ；

J：配送网络顶点序号集合，J={0 ,1,…,n} ，其中0为配送站；

S：无人机的最远飞行半径；

k：无人机飞行速度，其中k>1；

δ：一个任意小的正数；

L*(t,o,R)：在时刻t由原点o开始完成R中的所有服务需求并回到原点o所花费的最短时间；

Rd：按最优调度L*(t,X,R)分配给无人机的需求序列集合；

Rv：按最优调度L*(t,X,R)分配给车辆的需求序列集合；

Rsv：车辆需求序列中待服务需求集合，Rsv⊆Rv；

tid：无人机配送需求ri所花费时间；

tij：车辆从需求ri位置到需求rj位置所花费时间；

Pv(t)：在t时刻车辆的位置；

Td：无人机配送总时间；

Tv：车辆配送总时间；

T：总服务时间，其中T=max{Td,Tv} ；

xij：车辆从需求ri到需求rj则等于1，否则等于0；

yi：无人机配送第i个需求则等于1，否则等于0。

1.2 问题描述

假设所有需求ri随机分布在网络图G上，且均为同一类型物资，需求量均为1，实时产生、序贯而出、不能拒绝。配送站使用无人机及车辆并行配送，其中无人机与车辆数目均为1，初始时刻无人机与车辆均处于配送站，服务过程中经过需求点即该需求点配送完成，配送完成后需返回配送站。无人机运载量为1，最远飞行半径为S，以k(k>1) 个单位速度移动；车辆运载量为∞，最远里程为∞，以为1的单位速度移动。由于运载量限制，无人机需于配送站取货，而车辆无需。

对于d(o,xm)≤S的需求点，可使用无人机或车辆进行配送；对于d(o,xm)>S的需求点，只能由车辆进行配送。令Td为无人机配送总时间，Tv为车辆配送总时间。总服务时间由无人机或车辆最晚返回配送站的时间决定，求如何安排配送方式及规划路线使总服务时间最小化。

如图1所示，在t时刻同时新增两个需求点，此时原本由无人机配送的需求改为由车辆进行配送，由此车辆及无人机的路径改变。

图1 问题描述示意图Fig.1 Schematic diagram of problem description

对于该研究问题，可用竞争分析法衡量所设计在线算法的优劣性。竞争分析是衡量动态问题求解策略性能的方法之一，是在线对手与离线对手之间的博弈过程。在这个博弈过程中，离线对手释放需求序列，其释放的需求会尽可能利于离线对手而不利于在线对手。从而，离线对手从0 时刻便知晓全部需求信息，而在线对手未知。对于同样的输入序列θ，令在线对手采用策略β服务输入序列θ所得解为Conline(θ)，离线对手采用最优策略服务输入序列θ所得解为COPT(θ)。对于任意的θ，都存在常数ρ与γ使得Conline(θ)≤ρ×COPT(θ)+γ成立，则策略β的竞争比为ρ。若不存在小于竞争比ρ的在线策略，称ρ为该问题下界。当ρ越趋近于1 时，策略性能越好。

2 车辆无人机并行配送在线问题下界

定理1对于车辆无人机并行配送在线问题，其下界为1.5。

证明以直线为例，不失一般性。在直线的正半轴上，需求ri的位置xi，即该点到原点的距离；在直线的负半轴上，需求ri的位置xi取绝对值，即该点到原点的距离。假设无人机、车辆的服务序列中存在最远需求点(ti,|s|)、(ti,|y|)，车辆最远配送需求点与配送站距离大于无人机最远配送需求点。于-δ时刻释放需求r1=(-δ,s)。需求r1在无人机与车辆配送范围内，在线对手可采用无人机或车辆进行配送。在线对手于t时刻开始服务需求r1，下面对t的取值分情况讨论。

情形1当ts/k。同理，若y时刻在线车位于ϵ处，则需求r2=(y,-y)。在线对手在获知需求r2后，由于 |y|>|s|，超出无人机配送范围，只能由车辆进行配送。对于离线对手，若需求r2=(y,y)，无人机不参与配送，从0时刻开始车辆沿正半轴运动。若需求r2=(y,-y)，则0时刻开始车辆沿负半轴运动，无人机沿正半轴运动。Conline≥max{3y+ϵ,( 3s)/k-δ} =3y+ϵ;COPT=2y,ρ=Conline/COPT ≥( 3 y+ϵ )/( 2y )≥( 3y )/( 2y)。对于情形1，ρ≥1.5。

情形2当t≥s/k时，则离线对手不再释放新需求。离线对手从0 时刻开始无人机服务需求r1。此时COPT=2s/k，Conline≥3s/k-δ；ρ=Conline/COPT≥(3s/k-δ)(2s/k)。

对于情形2，取δ→0，ρ≥1.5。

因此，直线上策略的竞争比下界为1.5。证毕。

定理1表明对于车辆无人机并行配送调度问题，考虑最坏情形下任意的在线策略目标值与离线策略最优目标值的比值下界为1.5。

3 车辆无人机并行配送在线策略

3.1 在线均衡策略设计

假设现有一个明确的离线算法，可根据当前任意输入得到对应的较优解。

在线均衡策略：当新需求释放时，进行即时重优化，按离线算法将此时已获知的全部需求重新分配给车辆与无人机服务，形成各自新的服务序列，其中已服务需求不再服务，车辆按当前位置规划最优路径，并依次服务待服务需求。

3.2 在线均衡策略性能分析

根据1.1 节中的符号定义，显然Rd∪Rv=R,Rd∩Rv=∅。现假设最后一个服务请求为rm(tm,xm)。通过竞争分析，考虑需求产生的最坏情形，可证明在相同情形下在线均衡策略所得结果与离线对手最优结果之比的上界。

引理1对于d(o,xm)≤S，即新需求可由车辆或无人机进行服务，该不等式成立COPT≥max{L*( 0 ,o,R),tm+d(o,xm)/k}；对于d(o,xm)>S，即新需求只能由车辆服务，此时COPT≥max{L*( 0 ,o,R),tm+d(o,xm)}。

证明 情形1当d(o,xm)≤S，即新服务需求加入无人机或车辆需求序列中。

由于在需求尚未释放前不能对其进行服务，因此对于最后一个服务请求为rm(tm,xm)，可有COPT(R)≥tm+T(o,xm)，其中T(o,xm)表示返程时间。当由无人机进行服务时，由于无人机飞行速度为k，则有T(o,xm)=d(o,xm)/k。当由车辆进行服务时，由于车辆行驶速度为1，那么T(o,xm)=d(o,xm)/1=d(o,xm)。由于存在所有需求仅由无人机配送的可能性，因此COPT≥max{L*( 0 ,o,R)，tm+d(o,xm)k} 。

情形2当d(o,xm)>S，即新服务需求加入车辆需求序列中。同理，由于车辆行驶速度为1，存在T(o,xm)=d(o,xm)/1=d(o,xm)。因此，COPT≥max{L*( 0 ,o,R),tm+d(o,xm)}。

综上，引理1得证。证毕。

引理2当新需求rm(tm,xm)释放时，可有L*( 0 ,o,R)≥L*(tm,o,Rsv)，0

证明当配送需求序列相同且出发点相同时，出发时间越晚，所获得的已知信息将会越多，从而所得到的规划路线越优。因此，当0

由于新需求rm(tm,xm)释放时，采用离线算法重新规划，tm时刻车辆新服务序列Rv与离线算法所得车辆服务序列相等，Rsv表示车辆需求序列中待服务需求集，易知Rsv⊆Rv⊆R。需求点相同的情况下，所服务需求数量越少所花费时间越短，因此L*(tm,o,R)≥L*(tm,o,Rv)≥L*(tm,o,Rvs)。引理2得证。证毕。

引理3在无新需求释放情况下，该不等式成立

证明假设车辆存在待服务需求，车辆新服务序列为Rv={rv1,rv2,…,rvn}，其中需求点rvi=(tvi，xiv),tvi

定理2在线均衡策略竞争比为2.5。

证明对于产生的任何一个新需求，只有由无人机配送或车辆配送两种策略选择，因此考虑以下两种情形：

情形1由离线算法，新需求由无人机配送。令U={u1,u2,…,un} 为tm时刻无人机n个待服务需求各自的配送时长，n≥0，有该不等式成立：d(o,xm)/k。

情形1.1假设车辆不存在待服务需求，则有Tv≤tm+d(Pv(tm),o) ，即可得该不等式成立：Conline(R)≤易知tm+根据引理1，可得COPT≥tm+d(o,xm)/k。此时假设W={w1,w2,…,wn} 为离线对手无人机服务序列各需求配送时长。由于采用离线算法，对于相同的输入序列与算法，离线对手与在线对手此时结果相同，因此集合U⊆W。COPT=

情形1.2假设车辆存在待服务需求，在tm时刻，车辆从当前位置出发服务新服务序列中待服务需求集，则Tv≤tm+L*(tm,Pv(tm),Rvs)≤tm+L*(tm+Pv(tm),o,Rsv)+Pv(tm)。 由 引 理3，L*(tm+Pv(tm),o,Rvs)+Pv(tm)≤由引理因此，Tv≤tm+COPT(R)+( 1/2)COPT(R)≤( 5/2)COPT(R)。又

情形2由离线算法，新需求由车辆配送，即车辆存在待服务需求。由情形1.2 知，Tv≤tm+L*(tm+同理，令U={u1,u2,…,un}为tm时刻无人机新服务序列中n个待服务需求配送时长，n≥0，有2COPT(R)。Conline(R)=max{Td,Tv} ≤( 5/2)COPT(R)。

综上所述，该策略竞争比为2.5。证毕。

针对3.1 节中在线均衡算法所调用的离线算法，可通过研究其对应的离线问题得到，由此产生第4 章内容。

4 车辆无人机并行配送离线策略分析

4.1 离线模型建立

相对于车辆无人机并行在线配送问题，对应的离线问题与其区别仅在于离线问题从初始时刻便已知所有需求点的所有信息，其余问题描述一致。基于该问题，可建立如下模型：

目标函数（1）表示总服务时间由无人机或车辆最晚返回配送站的时间决定；约束（2）表示无人机所耗费时间为无人机服务序列中各需求所耗费时间之和；约束（3）表示车辆所耗费时间为车辆服务序列中各段路程所耗费时间之和；约束（4）表示无人机与车辆所服务需求点之和与总服务需求数相等，即Rd∪Rv=R；约束（5）、（6）表示各需求只能由无人机或车辆进行服务，即Rd∩Rv=∅，且为节点平衡约束，表示各需求只服务一次；约束（7）表示如果车辆从0 点出发则必然会回到0点；约束（8）避免车辆路径形成子环；约束（9）表示模型中决策变量的取值范围。

4.2 离线算法提出

对于该问题是否能求出最优解，需考虑其时间、空间复杂度。该规划模型属于匹配模型与TSP 模型结合。由于TSP 问题属于NP 难问题，其又包含于车货匹配问题中，因此该问题也属于NP难问题，无法在有效时间内求出最优解，可采用启发式算法进行求解。

针对该问题，结合均衡算法、插入法思想提出无人机优先均衡算法。令Rex为d(o,xm)>S的需求集合，=Td-Tv,Tmseitnus为差值集合且初始为空集，其余参数见1.1节。以下为无人机优先均衡算法伪代码。

其中1～8行求出初始解，9～22行通过迭代选择得出最终解。

4.3 离线算法性能分析

无人机优先均衡算法的时间复杂度为O(n3)。假设n是需求点数量，该算法的时间复杂度主要由初始解生成与迭代选择两部分决定。在初始解生成中，所涉及以配送时长最短为目标的遗传算法时间复杂度为O(n3)，j∈I循环的时间复杂度为O(n)，其余代码时间复杂度为常量，因此整个初始解生成部分时间复杂度为O(n)+O(n3)。在迭代选择过程中，主要对rj∈Rd进行循环，其时间复杂度为O(m⋅n3)，其中m为Rd集合中需求点数，m≤n，因此迭代选择部分时间复杂度为O(m⋅n3)。综上所述，无人机优先均衡算法的时间复杂度为O(n3)+O(m⋅n3)=O(n3)。

除此之外，对于同样的输入，通过比较无人机优先均衡算法所求解与CPLEX最优解可有效验证离线算法的性能。针对离线模型，通过MATLAB 2018a 调用CPLEX 及YALMⅠP 工具箱进行求解。引入变量T3，由目标函数minT=max{Td,Tv} ，令Td≤T3、Tv≤T3，将4.1节中的模型转化为线性规划模型。

仿真初始设置为：车辆行驶速度为1，无人机飞行速度为2，无人机飞行半径为8，由于问题重点在于无人机飞行范围内的需求分配，为达到更好的展示效果，令需求一半在无人机飞行半径内随机产生，一半无限制。

所设计离线算法与CPLEX运行结果对比见表2，其中最优值保留三位小数。由表2可知，所设计离线算法结果与CPLEX最优值相比，随着需求点数量的增加，计算时间明显小于CPLEX 的计算时间，且结果偏差在合理范围内。由此说明了离线算法的有效性。

表2 离线算法与CPLEX对比结果Table 2 Comparison results of offline algorithm and CPLEX

5 在线算法仿真分析

对于随机生成的需求点坐标及释放时间，通过计算在线算法所得结果与离线最优下界值之比，进行在线算法关于输入参数的仿真分析。与4.3节中需求于0时刻一同释放不同，此时离线解同样受需求释放的限制，计算较为复杂，与其下界值相比不影响在线算法性能判断。离线最优下界取值方法见3.2节中引理1。

初始设置为需求点个数为10，无人机与车辆速度之比为1.5，需求点坐标最大值与无人机飞行半径之比为2，释放时间上限为50 min，每次独立测试50 次所得结果分别取平均值，得以下结果，如表3 所示。由于理论分析是基于最坏情形分析之下所得，而实际场景下不一定是最坏情形，因此结果中所得实际比值明显小于理论分析所得竞争比。

表3 仿真分析结果Table 3 Simulation analysis results

将需求点个数设为20，其余参数与本节初始设置相同，得在线结果示意图（如图2）、离线结果示意图（如图3）、结果比较表（见表4）。其中需求1代表配送站，各需求点序号按释放先后排列，离线结果示意图建立在所有需求信息在0时刻已知情形下。

图2 在线结果示意图Fig.2 Schematic diagram of online results

图3 离线结果示意图Fig.3 Schematic diagram of offline results

表4 结果比较表Table 4 Results comparison table

分析运行结果可知：

（1）随着需求点数量增加，在线均衡策略仍旧适用，但在线均衡策略结果与离线结果差距增加。需求个数不变情形下，释放时间上限提高，需求释放时间间隔增加，在线均衡策略结果与离线结果差距减小。因此，所提出的在线均衡策略更适用于需求点数量较少、释放时间间隔较长的情形。

（2）在现实场景中，对于车辆与无人机并行在线配送问题，无人机方面有以下建议。在无人机选用方面，选用服务范围更广、相对车辆速度更快的无人机能减小在线结果与离线下界比值，即使得在线均衡策略表现更优。在无人机配送方面，当出现接近无人机飞行限制范围的需求时，使用车辆进行服务，从而使无人机能更好地服务近距离需求，在更短时间内满足更多应急需要。

6 结语

本文研究了在应急配送背景下，基于需求实时产生的无人机与车辆并行配送在线优化问题。综合考虑了现实场景中需求实时产生，无人机服务半径有限、载重量有限、速度快等问题特征以及并行配送的服务模式，通过竞争分析法证明了该问题下界为1.5，并基于重规划思想设计了在线均衡算法，通过最坏情形分析法证明了在线算法的竞争比为2.5。由于所设计的在线算法调用了离线算法，因此对离线问题进行了描述、建模并设计了相应算法，通过与CPLEX 结果比较得出所设计的离线算法速度快，偏差低。最后，通过调整不同的输入参数，得出不同参数改变下在线算法依旧有效。通过所设计的在线均衡算法，可对车辆与无人机平行应急物资配送实时优化领域作理论补充。未来的研究方向可从混合在线配送进行考虑，混合在线配送指在部分信息未知情形下采用两种以上配送模式进行配送服务。