孟姗姗 ,郭秀萍,2

(1.西南交通大学 经济管理学院,成都 610031；2.北京邮电大学 经济管理学院,北京 100876)

近年来,无人机以成本低、速度快、飞行路径接近直线等优势在物流领域得到迅速发展[1-2],亚马逊、谷歌、京东等多家企业都在尝试使用无人机提供更高效的服务。但因其续航里程和载荷能力有限,卡车-无人机联合配送问题得到广泛关注,Wang等[3-4]的研究也证明,卡车-无人机联合配送在最坏情况下的效率仍优于卡车单独配送。

Murray等[5]和Agatz等[6]首先通过对经典旅行商问题的扩展,并假设无人机每次飞行只携带一个包裹,提出了飞行助手旅行商问题(Flying Sidekick Traveling Salesman Problem,FSTSP)、带无人机的旅行商问题(Traveling Salesman Problem with Drone,TSP-D)。文献[7-9]中对FSTSP 进行了扩展,考虑多卡车-无人机协同配送,设计了求解大规模问题的启发式方法；Marinelli等[10]将TSPD 扩展到在卡车路径任意位置发射和回收无人机,并使用贪婪算法求解。但上述研究均假设无人机一次飞行只服务一个客户点,而一次多点配送可以充分发挥无人机优势,针对此问题,Pedro等[11]提出了一种基于迭代的贪婪算法,优化无人机多点配送路径。文献[12-13]中考虑每辆卡车配备多架无人机,无人机一次服务多个客户,设计了灵活的启发式方法。上述研究不考虑重量对无人机电池能耗和速度的影响,虽然文献[14-15]中验证了无人机电池能耗与重量的近似线性关系,并应用于无人机单独配送问题；Jeong等[16]考虑无人机能源消耗和限制飞行区域的FSTSP,提出两阶段构造和搜索方法等,但均未考虑卡车-无人机联合、同时取送货的情况。因此,本文提出“最大重量判断法”构造初始可行解,以及基于节点特性的改进模拟退火算法(SA)进一步优化总成本。

综上所述,本文针对实际配送中客户点同时取送货的双重需求,考虑不同载荷对电池能源消耗和路径选择的影响下,无人机一次可携带多个包裹时的卡车-无人机联合路径优化问题,提出卡车-无人机联合取送货模式,并设计两阶段优化方法。仿真结果表明,本文提出的模式和方法能有效降低总成本,且算法效率较高。

1 问题描述

卡车单独取送货模式如图1 所示,卡车在载重约束下,携带一定量包裹从配送中心出发,依次完成同时取送货任务后返回配送中心。随着物流量的不断增大,卡车单独取送货面临交通和成本压力,难以高效完成任务。为此,本文提出一种卡车-无人机联合取送货模式,以缩短卡车行驶距离,降低总成本,如图2所示,每辆卡车携带一架无人机和包裹从配送中心出发,按照预定路线,在客户点取送包裹,无人机可以携带一些小包裹,从卡车上起飞,同时完成一些取送任务,无人机只能在配送中心或客户点起飞或与卡车汇合,在返回卡车后进行电池更换,并可以再次发射,在完成所有取送任务后,一起返回配送中心。其中,需求(取货量或配送量)超出无人机载重的客户点称为“超重点”,必须由卡车服务；剩余客户点称为“无人机可服务点”。

同时,由于无人机轻量、速度快,质量对电池能耗,即续航里程影响较大,如图3所示,设无人机最大承载量为3 kg,无人机先服务客户3时负荷减少(左图),而先服务客户2时负荷增加,消耗更多能量,甚至超出承载力(右图)。由于考虑路径方向性和无人机载重变化,增大了解空间和搜索难度。

Dorling等[15]验证了无人机在悬停、水平飞行和改变高度时,平均功率消耗大致相等。因此,考虑无人机恒定功率下,电池能耗与无人机重量正相关,本文扩展了Liu等[17]的能耗模型,引入参数α表示单位距离单位重量能耗率,用ws表示无人机自身重量,wdi为无人机d离开点i时的载重,dij为i～j的距离,则无人机d经过弧(i,j)的能量消耗表示为:Fdij=α(ws+wdi)dij；用P表示无人机功率,则无人机d从点i～j的飞行时间和速度分别为:

用Cdf表示无人机每瓦时能量消耗成本,则无人机d经过弧(i,j)的能耗成本为

综上所述,本文假设:每辆卡车有相同的载重限制；无人机有电池能量和容量约束,电池能耗随无人机重量线性变化；每个客户由卡车或无人机一次服务完成,且取货与送货同时进行；无人机只能在客户点或配送中心与卡车同步汇合,考虑无人机能耗和安全性,卡车到达汇合点的时间不晚于无人机；一架无人机一次可取送多件包裹；无人机在卡车上更换电池后可继续取送货,且每次发射时电池满电；卡车速度恒定,无人机速度随载重变化；每段里程用欧式距离测量；不考虑客户点时间窗限制。

2 模型构建

模型中使用的符号:

N——所有节点集合,配送中心表示为o(出发点)和e(返回点),o∈N,e∈N

A——所有弧的集合,(i,j)∈A,i,j∈N,i≠j

C——客户点集合,C=N{o,e}={1,2,…,n}

No,Ne——分别为路径的起点和终点集合,

fdk——无人机d子路径k的节点集合,fdk={dk0,dk1,…,dkp},k∈KD

K,D——分别为使用的卡车和无人机集合,K={t|t=1,2,…,m},D={d|d=1,2,…,m}

Cvt——卡车每公里的里程成本

Ct,Cd——分别为卡车、无人机的单位使用成本

Q——卡车最大承载量

W,F——分别为无人机最大承载量和电池最大能量值(单位:Wh)

wti——为卡车t在点i停留期间,各状态(如发射前、回收后等)载重的最大值

ttij,tdij——分别为卡车t及其无人机在弧(i,j)∈A(i≠j)的旅行时长

tti,tdi——分别为卡车t及其无人机到达点i的时间

ts——单位客户点的服务时间,即客户点装卸包裹时间

xtij——当卡车t经过弧(i,j)∈A(i≠j)时为1,否则为0

ydij——当无人机d经过弧(i,j)∈A(i≠j)时为1,否则为0

zti——当卡车t服务客户i时为1,否则为0

zdi——当无人机d服务客户i时为1,否则为0

bdij——当无人机d从点i发射,在点j返回时为1,否则为0

sdi——当无人机d从点i发射时为1,否则为0

ldi——当无人机d在点i返回时为1,否则为0

htd——当卡车t配备无人机d时为1,否则为0

uti,udi——分别表示点i在卡车t路径、无人机d子路径中的访问顺序,uti≥0,udi≥0

M——足够大的正整数

建立如下数学模型:

目标函数

式(3)表示最小化总成本,其中,m为卡车或无人机使用量,由优化结果确定；式(4)表示每辆卡车从配送中心出发并返回配送中心；式(5)保证每对无人机发射点和回收点流量守恒；式(6)为卡车线路节点的进出平衡约束；式(7)保证每个无人机服务点流量守恒；式(8)保证每个客户被卡车或无人机服务,且仅一次；式(9)表示每条无人机子路径至少服务一个客户；式(10)、(11)保证发射点和回收点为卡车经过点,且在该点分别有无人机离开和返回；式(12)、(13)对式(10)、(11)进行补充,以明确变量间约束关系；式(14)确保无人机的每次发射和返回在所属同一卡车路径上；式(15)、(16)表示每个节点至多发射或回收一次无人机；式(17)表示卡车经过点i、j,无人机从点i发射后,没有在点j返回,则不能在点j发射,以保证无人机子路径间的不交叉性；式(18)、(19)确保无人机发射回收顺序与卡车、无人机访问顺序一致；式(20)表示不允许卡车和无人机并行经过同一段弧；式(21)保证每辆卡车在各节点满足承载量约束；式(22)保证每条无人机子路径各节点上的载重不超出无人机最大承载量；式(23)为每架无人机每次飞行的能耗限制；式(24)、(25)分别为卡车和无人机到达每个节点的时间约束；式(26)保证卡车到达汇合点的时间不晚于无人机。

3 方法设计

由于问题的NP-hard性质,本文提出一种两阶段求解方法,获得近似最优解。第1阶段,运用“最大重量判断法”构造初始可行解,为卡车指派取送任务并确定卡车使用量；第2 阶段,对模拟退火算法(SA)进行改进,以优化卡车-无人机路径,实现成本最小化。

针对卡车-无人机同时取送货问题特点,在优化无人机路径时,不仅要满足无人机承载量、电池能耗以及路径间不交叉等约束,还需考虑卡车在其各路径节点的载重情况,求解空间较小。为此,本文提出“最大重量判断法”构造初始解,以扩大第2阶段解空间,提高求解速度和质量。其次,在卡车、无人机、同时取送货等多重实际约束下,求解易陷入局部最优,因此,在第2阶段,使用模拟退火算法(SA),以一定概率接受次优解。同时,为使SA 适合问题特性,结合节点类型,设计了3类11种邻域搜索算子,生成候选解；为节约总成本,在搜索中允许在同一节点(包括仓库)发射和回收无人机,并使用区域设定法和禁忌列表等加速策略,增加搜索可行性,减少搜索重复性,提高求解效率。

首先,针对每辆卡车t,定义如下概念:

(1)卡车点i。卡车t路径中不参与无人机发射和回收的节点(i∈tp)。

(2)无人机点i。卡车t无人机服务的客户节点(i∈dt)。

(3)组合点i。卡车t路径中参与无人机发射或回收的节点,包括发射点(发射但不回收无人机,i∈spt)、回收点(回收但不发射无人机,i∈lpt)和混合点(同时发射和回收无人机,i∈slt=sst∪sdt,i∈sst表示卡车在i点发射无人机,并在原地收集；i∈sdt表示卡车在i点回收无人机后,原地再次发射)。(1)和(3)合称为卡车路径点。

3.1 编码

采取自然数编码,卡车路径中,用0 表示卡车ID,总节点数(1+n)表示终点配送中心ID,顾客集为{1,2,…,n},如图4所示,从左向右,第1个0后的数字为第1辆卡车依次访问的客户点ID；无人机路径中,起始数字表示卡车序号(1,2,…,m),其后跟随的数字为该卡车(卡车1)对应的无人机路径,包含组合点,如13-3-10-11为一个“无人机子路径”,表示无人机从点13发射,服务客户3、10后,在点11返回。虚竖线“┇”为无人机子路径分隔符,以辅助说明。

3.2 第1阶段:构造初始解

由于需要考虑车辆载重及各节点载荷变化,简单的贪婪算法或随机生成初始解的方式[1,17]需要进行多次载重可行性判断,增加搜索时间,故提出“最大重量判断法”(简称MW 法)进行初始解构造,其优势在于保证后续卡车路径的可行性,扩大第2阶段解空间,提高后续搜索的收敛速度和质量。

初始解的构造包括卡车单独取送货路径构造和无人机路径添加两部分。首先,采用MW 法构造由卡车完成全部取送货任务的完整路径,为卡车分配任务,确定卡车使用量(步骤1～3)；然后,基于节点特征,将部分卡车服务客户转化为无人机服务客户,形成初始解(步骤4)。

MW 法基本思路:使用最大重量对客户分组,将组内同时取送货旅行商问题(TSP-SPD)转化为一般旅行商问题(TSP)。对于每个客户i,定义μi=pi-di表示客户i的净需求(其中,di和pi分别为客户i的配送量和取货量)；定义表示车辆经过客户i后的载重累积增量。假设卡车服务一组客户V⊆C,从配送中心出发时的载重量为wv,则

是满足卡车载重约束的充要条件[18]。cumi最大值即该组客户中正μi之和,表示为:,则最大重量为wv+uv。MW 法构造初始解的基本步骤如下:

步骤1计算所有客户点的净需求量μi,总配送量及正净需求和uc,进行最大重量判断,如果wc+uc≤Q,则一辆卡车即可满足全部需求,初始卡车路径的构建为传统TSP,使用模拟退火算法(SA)优化,优化方式如图5所示,然后转步骤4；否则,转步骤2。

步骤2初始化客户总配送量w=0,正净需求和u=0,卡车路径列表rt=[0],从配送中心出发,依次寻找最近的客户点i,并更新w,如果μi＞0,更新u,如果w+u≤Q,则在rt列表中添加客户点i；否则,在rt列表中添加0,初始化w、u和rt,启动另一条卡车路径。重复上述操作,至所有客户被添加,形成初始卡车路径。

步骤3使用模拟退火算法求解有最大重量约束的TSP(TSP-MW),优化步骤2的初始解,每次搜索以最大重量wv+uv≤Q(设该卡车服务一组客户V)为判断条件,若超出,则返回上一步继续搜索,搜索方式如图6、7所示,为同卡车、不同卡车路径节点2-opt交换。

步骤4针对每条卡车路线,通过将部分卡车路径点调整为无人机点,生成无人机路径,在满足无人机载重和能耗约束下,采取如下操作:

操作1将卡车点转为无人机点,如图8中的点6,构造无人机子路径2→6→4,无人机从点2出发,服务客户6后返回点4,卡车直接从2→4,同时计算成本节约量,如果节约量为正,则执行此操作,如下操作亦然。

操作2将发射点转为无人机点,如图9所示,如果点4的取送任务可由无人机完成,则将客户4调整为无人机点,点4左侧相邻点5为新发射点,无人机子路径为5→4→9→,卡车直接从5→2。

操作3将回收点转为无人机点,如图10 所示,如果无人机在完成客户5的取送任务后可以继续服务客户2,则将客户2调整为无人机点,点2右侧相邻点4为回收点,无人机子路径为→5→2→4,卡车直接从7→4。

操作4将混合点转为无人机点,如图11 所示,将两个子路径合并,形成路径→7→9→3→,卡车直接从6→2。

按照卡车访问顺序进行循环,每次循环,针对卡车访问点类型,进行判断和替换操作,直至不存在正成本节约,输出初始解。其中,无人机子路径载重判断依据为

设该无人机一次飞行服务一组客户d。

3.3 第2阶段:优化初始解

为提升解的搜索效率和质量,对模拟退火算法(SA)进行改进,针对每辆卡车优化初始解。

(1)多种邻域搜索操作。传统模拟退火算法对解空间的搜索能力较弱,使得算法整体运行时间过长。为此,参考Liu等[17]的研究,设计了同路插入、异路插入和两点交换3类方法对解邻域进行搜索,取最优结果为候选解,每次搜索均需进行无人机载重及能耗判断,若超出则返回上一步继续搜索。考虑问题的复杂性和无人机约束条件,针对节点类型采取不同策略,提高搜索效率。

同路插入。针对同一卡车,在不改变客户服务方式下,从该线路服务的客户中随机选择一个贪婪插入成本最小的可行位置。包括卡车点同路插入、无人机点同路插入和混合点同路插入3种。

图12为将卡车点贪婪插入所在卡车路径,此时被插入节点原来位置清空,后续节点位置前移；图13为将无人机点插入同卡车的无人机路径,可以插入该点所在无人机子路径,也可以插入其他无人机子路径,选择插入成本最小的位置,插入方法同上；组合点(此处不考虑混合点的情况)插入所在卡车路径,需要考虑路径方向的一致性,如果卡车路径中,发射点插入位置在原回收点之后,或回收点插入位置在原发射点之前,则对应无人机子路径倒向。如图14所示,回收点9 的插入位置在原发射点3 之前,该无人机子路径变为9→7→3。

异路插入。针对同一卡车,在改变客户服务方式下,从该线路服务的客户中随机选择一个贪婪插入成本最小的可行位置,同样包含3种方式。如图15所示,为将卡车点插入同卡车的无人机路径中,成为无人机点,或为该卡车点建立新的无人机子路径,贪婪插入原无人机路径中,取成本较小的方式。将无人机点插入所属卡车路径的情况如图16所示,若选择点为该无人机子路径唯一服务点,则删除该无人机子路径。图17为将发射点转化为无人机点,即将插入成本最小的卡车路径点添加到原无人机子路径端点(如点2),成为新发射点,卡车路径中,原发射点位置清空,新发射点位置不变。针对回收点的操作同上；如果将混合点插入无人机路径,则与3.2节图11的操作相同,将在该混合点交汇的两个无人机子路径合并为一条子路径,并在对应卡车路径中删除该点。

两点交换。针对同一卡车,从该路线服务的客户中随机选择两个进行交换,采用5种方式,同时,在生成随机数时排除无人机点与“超重点”间交换,减少解的不可行性。图18为两卡车点交换,图19为卡车点与无人机点间交换,图20为无人机点间交换的两种情况,即同无人机子路径内、不同子路径间无人机点交换。图21、22所示为交换点中存在组合点的情况,此时,对应无人机路径中的组合点也需要交换,存在组合点与卡车路径点间同路交换和与无人机点异路交换两种。

(2)设计加速策略,提高优化效率。为避免不必要的搜索,针对问题特征设计了加速策略:区域设定法,即在不失解最优性前提下,提前排除部分不可行解,针对性缩小搜索空间,提高算法效率。包括3个方面:①在卡车点异路插入-创建新无人机子路径、组合点异路插入中,新发射点的选取范围,首先排除原发射点、混合点和被插入点(约束式(15)～(16)),新回收点的选取亦然,且两者形成的组合应满足与卡车相同的访问顺序(约束式(18)～(19))；②由于无人机载重约束,在异路插入、涉及无人机点的交换中,被插入点/被交换点的选择范围应限定在被优化路线中无人机可服务点集合内；③交换操作中,随机选取被交换点时,首先排除无人机点与超重点的所有交换方式。此外,由于问题存在多重约束,为进一步提高搜索效率,使用禁忌列表节约计算时间:在SA 内循环中(每一温度下)使用禁忌列表存储已经进行的操作,以避免重复性邻域搜索和判断,并在每次内循环结束后进行禁忌列表初始化。

以创建新无人机子路径的区域设定为例进行理论分析。设卡车t的路径节点数为c(含首尾仓库),无人机子路径数量为b(即原发射点与混合点之和),一次搜索中,如果不使用区域设定法,可形成(c-12)种发射-回收组合,否则至多可形成(c-b-1)2种组合(未考虑与卡车行驶方向的一致性),两者之差为:y=-b2+2b(c-1)。因为0≤b≤c-1,所以y在该区间单调递增,即当c一定时,随着无人机发射次数b和迭代次数的增加,计算量持续增加,在考虑方向性时,两者差距更大,同时,无效搜索的增加,会降低解的质量。

4 算例分析

以网站http://www.bernabe.dorronsoro.es/vrp/上CVRP 标准算例库中的A-n32-k5、A-n44-k7、A-n55-k9、A-n69-k9 以及A-n80-k10 等5 个算例为基础,对数据集进行改进,分别命名为:M-n32、M-n44、M-n55、M-n69 和M-n80。改进方法为:设定“超重点”比例为10%(ξ=[n×10%]),将其配送或取货量设定到(3,10),剩余客户的配送量为原来的0.1,调整至(0,2.5),并为其中90%的客户在(0,2.5)范围内随机添加取货量,单位均为kg。同时,将各节点坐标乘以0.1,单位为km,以适应无人机载重和续航要求。

相关参数设置:无人机自身质量取2 kg,最大承载量取3 kg,最大载荷下的续航距离取10 km,电池单位能耗率α=3 Wh,则电池可提供的能量为150 Wh,电池功率取450 W；卡车最大承载量取90 kg,里程成本为每km 1.5元,设卡车与无人机单位里程成本比β=25[17],则无人机的单位能耗成本为4元/k Wh；卡车和无人机的单位固定费用分别取30元和3元；卡车行驶速度取40 km/h,单位客户点服务时间为3 min。

本文两阶段算法均由Python 编程实现；运行环境为Windows 10操作系统,处理器为Intel(R)Core(TM)i7-10750 H CPU @2.60 GHz。

4.1 优化结果分析

首先以算例M-n44为例,对第1、2阶段的优化结果进行比较。所需卡车量为1,初始解如图23所示,卡车里程为47.11 km,总成本为105.93元；最优解如图24所示,卡车里程为33.99 km,总成本为87.16元,分别减少27.85%和17.72%,总运行时间为22.14 s,证明了方法的有效性。

进一步,分别通过不同规模算例对设计的方法进行检测。第1 阶段,初始温度分别取100、100、100、110和110 ℃,终止温度均为1 ℃,退火系数取0.98,迭代次数均为20；第2 阶段,初始温度均取100 ℃,终止温度均为1 ℃,退火系数取0.95,迭代次数均为10。每个算例运算10 次,取最优,结果如表1所示。

表1中:Tr/Dr表示卡车(无人机)使用量；R1、R2分别为第1、2阶段的卡车里程；C1、C2为第1、2阶段的总成本；Δ1、Δ2为两个阶段卡车里程和总成本改进率,T为平均运行时间,所有运算均在1 min内完成。Tntl、Tnrs分别为不使用禁忌列表和区域设定法时的平均运算时间,本文方法的平均优化结果分别为:88.67、94.73、131.16、137.59 和159.93,不使用禁忌列表时的优化结果与其基本一致,而未使用区域设定法时,平均优化结果分别为:89.23、96.76、133.58、143.07 和163.37。可以看出,两种方法均可以提高运算速度,同时,区域设定法对总成本也有一定优化,且加速效果更明显。

表1 两阶段优化结果对比

同时,与卡车单独取送货方式比较,图25所示为总成本对比,经两阶段优化,总成本相比卡车单独取送货分别减少17.00%、26.70%、18.29%、25.37%和19.74%；图26所示为总时间对比,优化后的时间分别减少17.09%、16.01%、7.91%、20.04% 和11.99%。由于卡车承载力有限,多卡车-无人机同时取送货下,随着客户规模的增大,卡车使用量阶段性增加,故时间呈波动变化,即当卡车使用量增加时,总时间因任务的多卡车分担而减少。多卡车模式下,总时间由耗时最长的路线决定,故同一卡车使用量下,总时间先减少后增加。图27所示为卡车里程对比,由于无人机的参与,联合模式下卡车里程减少近40%,且随着客户点的增加而增幅较缓。

4.2 不同联合取送货模式比较

首先,与无人机具有单位容量(一次服务一个客户)时卡车-无人机联合取送货模式(简称“无人机单位容量模式”)比较,以算例M-n69为例,图28所示为无人机单位容量模式,总成本为140.97元,卡车里程为47.11 km,无人机服务的客户量为31；图29所示为本文模式,总成本为130.32元,卡车里程降至40.22 km,无人机服务客户量达41。显然,本文模式能够有效发挥无人机运力,节省总成本。

进一步,与无人机不参与取货时,卡车-无人机联合配送模式比较。以算例M-n32为例,将取货量pick分别设定为10和20。遵循同时取送、每个客户只访问一次的原则,针对不同取货量,分别运算10次取最优,最优路径如表2所示。

由表2可见:当pick=10时,无人机不取货模式的总成本为86.85元,总时间为134.71 min,卡车里程为35.05 km,无人机服务量为15；本文模式的总成本为83.41元,总时间为125.00 min,卡车里程为32.56 km,无人机服务量为16。当pick=20时,无人机不取货模式的总成本为102.57元,总时间为148.57 min,卡车里程为46.06 km,无人机配送量为6；本文模式的总成本为84.84元,总时间为131.61 min,卡车里程为33.27 km,无人机服务量为15,在成本、时间和卡车里程上分别减少17.29%、11.42%和27.77%。可见,无人机不取货模式对取货量敏感,无人机参与取送程度不同,直接影响总成本,本文提出的同时取送货模式,能够更有效地利用无人机,实现成本和时间节约。

表2 两种模式卡车-无人机最优路径

4.3 灵敏度分析

为识别关键参数的影响,参照文献[7,17]和前面的算例分析,选取超重点比例(ξ)、无人机最大容量(W)、无人机电池最大能量(F)和卡车-无人机单位里程成本比(β)4 个参数,每个参数设置6个级别,基于算例M-n32、M-n69,共生成48种场景进行测算,每个场景运行10次的平均结果如图30所示。由图30可以看出,较大规模算例对参数更敏感。

图30(a)所示为超重点比例对成本的影响。可出看出,随着超重点比例的增加,无人机可取送包裹量减少,总成本增加,更接近卡车单独取送货模式。无人机最大容量变化对成本的影响如图30(b)所示。随着无人机载荷能力的提高,成本下降,特别是当容量为紧约束时(W≤4 kg),成本下降幅度最大。无人机电池能量对成本的影响如图30(c)所示。随着电池能量的增加,成本呈先快后慢的下降趋势。图30(d)说明,无人机的飞行成本直接影响总成本,当无人机能耗成本较高时,无人机使用率下降,成本增加,卡车-无人机联合取送货模式的成本优势基于无人机低成本特点。综上可知,在超重点较少,无人机容量和电池能量较大,且里程成本较低时,性能最好,无人机优势更明显,总成本较低。

4.4 “最大重量判断法”对算法效率影响

以算例M-n80为例对本文提出的“最大重量判断法”算法效率进行测试。随机初始解的平均优化结果为179.88 元,平均运行时间60.65 s；而使用MW 法的平均优化结果为159.93 元,平均运行时间40.64 s,结果更优。

在图31中,左图为采用MW 法进行卡车单独取送货初始解构造,右图为随机初始解。由图31可以看出,本文提出的MW 法在迭代开始阶段便将卡车里程优化到一个近似最优的位置,而随机初始解虽收敛较快,但距离MW 法仍有差距。图32所示为第2阶段两条路径里程成本优化结果,MW 法避免了第2阶段卡车载重的多次判断,增大了无人机路径解空间,加快收敛速度,结果更优。而随机初始解,在第2阶段的每次搜索中,均需考虑卡车承载力限制,解搜索空间较小,优化效果不明显。可见,本文提出的MW 法能有效提升解收敛效率和效果。

同时,不使用MW 法构造初始解时,第2阶段的每次搜索需要进行卡车各节点载重判断,基于动态规划思想,构造判断函数。如图33所示,针对每条卡车路线,建立状态集合state1、state2,每个节点内由于取送货及发射或回收无人机,卡车载重存在多个中间状态,取最大载重存入state1(不考虑到达该点时的初始载重),最终载重存入state2,则卡车载重的判断条件为:max(state1)≤Q。其中,state2用于节点间载重状态转移,前一点的最终载重为后一点的初始载重,用于计算state1。

设卡车路线t的总配送量为wt,总取货量为pt,mj和vj分别为路线t无人机子路径j的总配送和总取货量,tj={j|j=1,2,…,p}为路线t所有无人机子路径的集合；第i阶段(节点)的最终载重状态变量为xi,fi(xi)和f′i(xi)分别为第i阶段的卡车最终载重和最大载重,t(i),i=1,2,…,e为路线t第i阶段对应的节点。如果t(i)为组合点,则mk、vk分别为t(i)所在无人机子路径的总配送和总取货量；如果t(i)同时为两个无人机子路径的汇合点,mk和vk对应于其中前一无人机子路径的总配送和总取货量,则初始最终载重状态为

对应的初始最大载重为:f′1(x1)=f1(x1),则最终载重状态转移方程为(1＜i≤e)

5 结语

本文基于无人机轻量、成本低、受地面交通状况影响少的特点,针对正逆向物流优化问题,考虑同时取送、无人机电池能耗随载重变化、无人机一次飞行可取送多个包裹等因素,提出卡车-无人机联合取送货模式,构建两阶段求解方法:提出“最大重量判断法”构造初始可行解,为卡车指派取送货任务并确定卡车使用数量；采用基于节点特征的改进模拟退火算法进一步优化卡车-无人机路径,最小化总成本。仿真结果验证了两阶段算法的有效性,提出的卡车-无人机联合取送货模式较其他模式可有效减少总成本,“最大重量判断法”显著提高了算法收敛速度和效果,对实际情况中卡车-无人机联合取送货问题的解决有指导和借鉴意义。未来的研究将考虑取送货的时间窗因素,进一步优化总时间。