海岛无人机配送中继站选址-路径优化

陆 玲 玲， 胡 志 华

(上海海事大学 物流研究中心，上海 201306 )

0 引 言

海岛应急物流作为海岛应急管理的关键一环，在面临道路中断、天气恶劣等挑战时，如何快速、安全地将应急生活物资精准运往需求点，在提高救灾效率与安全性的同时，更好地控制系统总成本，是海岛应急物流的核心命题．

作为物流行业迈向自动化、智能化发展的典型代表之一，无人机将成为解决海岛应急物流配送安全和效率问题的一大利器．当海岛出现突发地质灾害等情况时，传统的轮渡运送方式一方面缺乏物资转运的灵活性，另一方面，配送人员的人身安全也无法得到保障．此时，若利用无人机生存能力强、机动性能好等优势，在短时间内将应急物资从码头运往海岛上的无人机配送中继站，再由卡车将物资送往需求点，既能提高抗灾救灾效率，又能降低因为人员疲劳或单调场景作业造成的安全隐患．

“十四五”期间，将进一步扩大无人机物流配送试点范围，服务乡村振兴战略．此前，国内外学者对于无人机在物流领域的应用已有了较为深入的研究．无人机在飞行过程中产生能耗和电池维护成本，但是投递小型包裹依然具有经济可行性[1]．垂停是无人机设计的关键技术问题，用于包裹配送的无人机同样需要解决和利用悬停控制能力[2]．翁丹宁[3]剖析了无人机进入商业领域物流配送的主要影响因素．杨代勇[4]提出构建一个完整的新型物流配送法律体系应从统一行业标准体系、强化监督管理机制、完善相关法律法规3个方面入手．目前已有文献研究了无人机与卡车合作进行交付的配送模式[5]，这种合作模式在最后1 km 的物流配送过程中得到了进一步应用[6]．

利用无人机将码头物资运往海岛灾区的重要前提是确定灾区对接点，在海岛中选取一定数量的无人机配送中继站负责将物资送往需求点，再由终端卡车从中继站出发，对该区域所有需求点进行遍历，最终回到无人机配送中继站，从而形成一个两级海岛应急物流网络．von Boventer[7]最早提出这种将网络中设施选址和路径优化问题综合考虑的选址-路径问题(location-routing problem，LRP)，对问题中设施点的选址和运送成本的关系进行了研究．按照节点类型，LRP可分为单层选址-路径问题、双层选址-路径问题和多层选址-路径问题．双层选址-路径问题[8]通过决策物流网络中备选点的位置和数量来规划两个层级之间的卡车配送路径．以物流系统总成本最小为目标函数，建立两阶段随机规划模型[9]；加入生产计划与时间窗约束，利用启发式算法求解[10]．此外，建立LRP混合整数规划模型，应用于生物质资源的供应领域[11]．

国内对于LRP的研究开始相对较晚，汪寿阳等[12]对LRP的主要研究进展作出综述，分析了求解该问题相关算法的主要特点．此后，李冰等[13]、马艳芳等[14]、刘建仁[15]研究了生鲜产品冷链物流背景下的选址-路径问题；吴迪等[16]、王诺等[17]讨论了海运物流体系在构建与优化中所面临的选址-路径问题．此外，LRP在逆向物流[18]和应急物流[19]领域的研究也在逐步深入．

在现有海岛应急物流研究中，林婉妮等[20]给出了如何优化海空协同的群岛救援调度方案．陈立家等[21]运用遗传算法，以舟山港港区船舶溢油事故风险应急联防设备选址为例，求解了加权距离最小化的优化选址模型．汪爱娇等[22]以宁波-舟山海域应急基地选址为例，运用贪婪算法对海上危险化学品应急基地的选址进行了优化．佟士祺等[23]针对群岛海运物流网络的规划布局问题，采用主成分分析法对群岛内岛屿进行计算分析．

从上述文献的研究成果可以看出，无人机设备在物流配送中的应用已经有了一定的研究深度．然而，目前尚未有文献将无人机设备引入海岛应急物流救援中．与传统的LRP不同，本文以海岛应急配送为研究背景，考虑应急物资流向的单向性，采用无人机在码头与区域配送中继站往返运输的形式．在海岛应急配送的第一级网络中引入无人机，因其具有运输成本低、机动性强等优势，缩短了第二级卡车的配送距离，更好地控制了系统总成本．具体做法是对海岛需求点进行聚类分析，求解不同聚类方案下系统运输总成本，最终给出使得系统总成本最低的无人机配送中继站数量及选址方案，并规划各配送区域的终端卡车配送最优路径．

1 问题描述

当前，海岛应急物流通常采用轮渡将物资运送到对岸海岛(图1(a))，再由配送卡车对需求点进行服务．然而，由于多数需求点位于海岛中部，道路交通遭到灾害破坏而被阻断，配送卡车很难按时完成繁重的配送任务．为进一步提高海岛应急物流配送的科学性，保证物资供应端与接收端的配送畅通性，做到安全性好、配送量足、针对性强、覆盖面广，本文将无人机配送引入海岛应急物流选址-路径问题中，如图1(b)所示．将一批物资从供应端码头(D)运往海岛的无人机配送中继站(T)，再由中继站(T)派出卡车将物资分发到每个需求点(Q)，由此形成一个包括3类节点和2个层级相邻节点之间的配送路径的两级物流网络．其中，D、T和Q的坐标已知，T的最大建造数量给定，且容量不限，能够承担区域内所有需求点的物资需求．无人机在满足续航里程的基础上，可以多次往返D和T节点，每个T派出1台配送卡车对该区域所有需求点进行1次服务，完成配送任务后返回中继站．考虑无人机配送中继站的选址以及D-T、T-Q的配送路径，使得各配送区域的卡车完成所有配送任务所行驶的总里程最短．

(a)传统海岛送货模式

2 数学模型

在构建无人机-卡车海岛配送模型时，需要分两个阶段完成．第一步先给出不同的无人机配送中继站的选址和需求点分配方案，接着求解各方案下各配送区域终端卡车的最优行驶路径，并计算无人机和卡车完成所有配送任务的总成本，最终优化目标是选取使得系统成本最小的方案．模型相关符号定义如下：

(1)集合

F，无人机起点D集合，通过f索引；

T，备选中继站T集合，通过p、q索引；

C，终端需求点Q集合，通过m、n索引；

K，终端卡车集合，通过k索引．

(2)参数

dmn，网络中节点m与节点n的距离；

tmax，无人机配送中继站最大建造数量；

e，无人机最长续航里程；

cd，无人机单位距离运输成本；

ct，卡车单位距离运输成本．

(3)决策变量

wp∈{0，1}，其中wp=1表示节点p被选为中继站；否则，wp=0．

xmnk∈{0，1}，其中xmnk=1表示卡车k从节点m到节点n；否则，xmnk=0．

ynk∈{0，1}，其中ynk=1表示节点n由卡车k配送；否则，ynk=0．

zpm∈{0，1}，其中zpm=1表示节点m由节点p提供服务；否则，zpm=0．

2.1 模型假设

(1)D、T和Q的地理位置已知，各节点之间的距离已知，且保持不变．

(2)无人机和卡车均按照两点间的直线距离行驶．

(3)无人机每次只为一个中继站服务．

(4)无人机只能在D和T处起降．

(5)不考虑越级配送，即无人机只能将物资送到T；卡车只能由T出发，将物资送到区域内多个Q．

(6)不考虑无人机和卡车的容量限制．

2.2 双层规划模型

(1)上层模型U：无人机配送中继站选址模型

在可选范围内确定中继站的数量和选址，完成应急物资由一级网络节点向二级网络节点转运．合理的中继站选址不仅能实现对附近需求点的全覆盖，还可以使得无人机配送资源的效率最大化，成为使得系统总成本最小化的选址基础．本层模型以配送系统总成本(包括从物资供应端码头到无人机配送中继站的无人机运输成本和终端卡车配送成本)最小为目标．其目标函数如式(1)所示，A(xmnk)表示终端卡车完成配送任务后的总成本，c表示配送系统总成本．

(1)

约束(2)为每个需求点只由一个无人机配送中继站提供服务；式(3)为每一个中继站与无人机出发点的直线距离需在无人机续航里程之内；式(4)为无人机配送中继站选址的数量约束．

(2)

dfp≤e；∀f∈F，p∈T

(3)

(4)

变量取值约束为

wp，zpm∈{0，1}

(2)下层模型L：终端卡车路径优化模型

在上层模型U所描述的无人机配送中继站选址及需求点划分的基础上，为了最大化配送效率，无人机将物资卸载到各区域的T后按原路返航，继而由各区域派出1辆配送卡车装载物资对需求点进行服务．下层模型L需要对各区域终端卡车的配送路径进行决策，使得所有卡车在完成配送任务后配送总成本最小．目标函数如式(5)所示．

(5)

约束(6)保证每个需求点只被服务一次；式(7)规定了卡车不能在两个无人机配送中继站之间行驶；式(8)表示当卡车k经过需求点n时，卡车k将对需求点n进行一次配送服务；式(9)、(11)规定了每一个需求点只能由一辆卡车进行一次服务；式(10)为平衡约束，保证卡车在需求点进出各一次；式(12)表示需求点m由无人机配送中继站p服务．

(6)

(7)

(8)

(9)

(10)

(11)

(12)

变量取值约束为

xmnk，zpm，ynk∈{0，1}

利用上述双层模型上下层协同优化的特点对普陀山无人机配送中继站选址及终端卡车路径优化问题进行构建．显然，上层模型U和下层模型L均为NP难问题，随着问题规模的扩大，很难在短时间内求出满意解．因此，本文开发了一种两阶段算法用于求解上述模型．

3 算法设计

海岛无人机配送中继站选址-路径优化问题结合了选址问题和旅行商问题两个NP难问题，不宜采用精确算法求解．针对双层规划的主要算法有禁忌搜索算法、遗传算法、灵敏度分析等．然而，仅选用单一的启发式智能算法难以同时求解包含两个子问题的选址-路径优化问题．据此，本文对K-means算法和模拟退火算法重新进行设计，分阶段求解，再根据求解结果对问题的整体加以优化．具体思路是：在上层模型U通过引入K-means算法，随机选取一个满足中继站取值范围的数值作为聚类中心个数，将一个区域内距离相对较小的需求点划分为一类，由此确定区域内的集合覆盖模型，得到无人机配送中继站的选址以及服务需求点区域的划分方案；在此基础上，采用改进的模拟退火算法求解下层模型L，对每个区域的卡车配送路径进行优化，求得各区域卡车完成配送任务后的配送成本，并计算包含无人机和卡车总运输成本在内的系统总成本．重复上述步骤，完成对中继站数量、中继站选址、需求点分配方案以及卡车配送路径的优化，最终得到使系统总成本最优的选址和配送方案．算法流程如图2所示．

图2 两阶段算法流程图Fig.2 Flow chart of the two-stage algorithm

3.1 K-means算法

由于本文所要分析的数据集规模较大，选取的需求点地理位置均为其经纬度信息，需求点分布不均且跨度较广，因此选用K-means算法将需求点进行归类，把一定范围内距离较小的需求点划分为同一配送区域．将海岛需求点聚类用于确定无人机配送中继站的位置和数量，以服务于分销区域的需求点．K-means算法作为一种典型的聚类算法，在最大化聚类内相似性的同时最小化了聚类间的相似性．在需求点聚类中应用K-means算法时，需求点被分成k0个聚类，目标函数是使得需求点与聚类中心的距离之和最小．K-means算法能够在较短时间内处理规模较大的数据集合．在应用该算法的过程中，首先需要确定k0值，随机选取k0个初始聚类中心，然后根据迭代法原理进行求解，得到无人机配送中继站的选址以及服务需求点区域的划分情况．

在算法1中，步骤3的Nj表示第j个聚类中心所包含的样本个数．

算法1K-means算法

输入 初始聚类中心个数k0、节点总数t

输出 聚类结果，即无人机配送中继站选址及服务需求点区域划分

步骤1任选k0个初始聚类中心；

步骤2将t-k0个需求点分配给距离最近的th，得到聚类集Sh，h=1，2，…，k0；

步骤4若t′j≠th(h=1，2，…，k0)，转步骤2；否则，聚类结束．

3.2 改进的模拟退火算法

下层模型L研究从无人机配送中继站到终端需求点的卡车配送路径优化问题，模拟退火算法是一种流行的迭代元启发式算法，广泛用于解决离散和连续优化问题．不同于梯度下降法，模拟退火算法能够依赖其原理以一定的概率有效地跳出局部最优值，增加了寻找全局最优解的可能性．因此，本文选用模拟退火算法求解终端卡车配送路径优化问题．

(1)编码与初始解的产生

由于海岛无人机配送中继站选址-优化包含多个子问题，考虑到本文所提出的两阶段算法采取的是自上而下的求解步骤，因此，对于第一阶段的选址和第二阶段的路径优化，本文以统一的形式对配送网络进行编码．在上层确定好无人机配送中继站集合{1，2，…，k0}以及区域分配方案后，在求解下层卡车配送路径优化时，将t-k0个需求点进行编号，一组解空间中，首位代表中继站的编号，从第二位编号往后代表卡车依次经过的需求点．

(2)产生新解

对于传统的模拟退火算法，在产生新路径时运用的是路径交换法，主要做法是从所有需求点中随机抽取两个节点，将这两个节点在原有路径中的位置进行交换，其他节点位置保持不变，从而产生一条新路径．本文在使用路径交换法的基础上，增加了采用路径倒置产生新解的方式．以图3(a)中继站1的解空间为例，若随机抽取6和10两个城市，那么这两个城市之间的路径需要倒置排列以获得新解，如图3(b)所示．

(a)原始解

改进的模拟退火算法求解步骤如算法2所示．

算法2改进的模拟退火算法

输入 网络中所有节点的距离矩阵D、无人机中继站选址及分配结果S

输出 各无人机中继站卡车配送最优路径Xbest及距离E(Xnew)

步骤1将无人机配送中继站和需求点进行编号，随机产生一个初始解X0，令Xbest=X0，计算目标函数E(X0)．

步骤2设置初始温度T(0)=T0，迭代次数i=1，衰减函数T(i+1)=αT(i)，链长Lmax．

WhileT(i)>Tend

forL=1 toLmax

产生新解Xnew，得到目标函数的增量ΔE=E(Xnew)-E(Xbest)

若ΔE<0，Xbest=Xnew

否则

若c=random[0，1]

Xbest=Xnew

否则，Xbest不变

end

i=i+1

end

步骤3输出当前最优值，计算结束．

4 普陀山海岛配送实例分析

本文以浙江省舟山市普陀山海岛物流配送为例，验证两阶段算法的可行性．通过对政府官网和国内各大旅游网站的调研，选取了304个需求点，包含普陀山海岛内的景点、民宿、小区等物资需求量较大的节点．无人机从朱家尖客运中心出发，将应急物资送往无人机配送中继站，再由各中继站派出卡车对需求点进行服务．

4.1 数据预处理

将需求点名称存入Excel文件后，通过调用百度地图应用程序编程接口，批量获取304个需求点的经纬度信息．部分需求点地理坐标如表1所示．在获取需求点经纬度坐标的基础上，计算任意两个需求点的地表距离，生成需求点的距离矩阵．

表1 部分需求点地理坐标Tab.1 Geographical coordinates of some demand points

本文以普陀山海岛304个需求点和1个无人机出发点(朱家尖客运中心)的地理坐标为输入数据，假设无人机的单位运输成本为10元/km，卡车的单位运输成本为30元/km．

4.2 无人机配送中继站选址及区域划分

将需求点的地理坐标作为K-means算法的输入数据，对304个分布在普陀山海岛的需求点进行聚类分析．为选取符合实际配送能力且成本相对较低的选址分配方案，在给定最大无人机配送中继站数量的情况下，上层算法通过设置不同的聚类中心数量，并提供各种数量下的最优需求点区域划分方案，由下层算法计算出该方案的系统总成本，在最大迭代次数之内选取使得系统总成本最低的配送方案．无人机配送中继站数量的优化过程如图4所示，可以看出，当聚类中心数量为38时，即开设38个无人机配送中继站时，系统总成本可以达到既定范围内的最低值．

图4 聚类中心数量优化过程Fig.4 Optimization processes of the number of cluster centers

海岛需求点的聚类结果如图5所示，部分中继站的名称及地理位置信息如表2所示．图5包含由38种不同颜色所构成的需求点集合，同一颜色的需求点被划分至一个配送区域，由该区域的无人机配送中继站负责配送物资．

图5 38个聚类中心的聚类结果Fig.5 Clustering results of 38 cluster centers

表2 部分无人机配送中继站信息Tab.2 Some drone delivery relay station informations

38个中继站在普陀山海岛地图中的坐标点如图6所示．中继站呈南面密集、北面零散的分布态势．这是由于普陀山地势南面平缓，北面高峻，人口大多聚集在南面平地一带，因此需求点也集中于南面．所有无人机配送中继站的选址均在无人机续航里程范围之内，无人机从朱家尖客运中心将物资运往中继站，规定无人机每次仅向一个中继站运送物资，完成任务后返回朱家尖客运中心，装载下一配送区域的物资运往对应的无人机配送中继站，依此类推，每个中继站均与无人机进行一次对接，完成无人机和卡车的海岛两级配送任务．

图6 38个无人机配送中继站分布图Fig.6 Distribution diagram of 38 drone delivery relay stations

4.3 终端路径优化

在此基础上，划分以无人机配送中继站为聚类中心的38个配送区域，每个区域拥有1辆配送卡车，为包含38个中继站在内的共304个需求点提供服务．无人机将货物运往各中继站后，卡车装载货物从中继站出发，沿着最优路径依次为所在区域需求点进行物资配送，完成任务后返回中继站．

以所有卡车完成配送任务的卡车配送成本最低为目标函数，利用改进的模拟退火算法求解，算法的参数设置为α=0.99，T0=1 000，Tend=0.01，Lmax=300．

经计算，所有卡车完成配送任务所行驶的总里程为28.43 km，配送成本为853.0元．各区域终端最优配送路径、卡车配送里程以及卡车配送成本如表3所示．

表3 部分区域配送路径及卡车里程表Tab.3 Delivery routes and truck odometers in some regions

根据表3的配送情况，结合无人机从朱家尖客运中心飞往无人机配送中继站的路线，得到完整的无人机-卡车海岛两级物流配送网络，如图7所示．图6中相同颜色的中继站在图7中属于同一张两级配送网络图．

图7 普陀山海岛应急物流两级网络图Fig.7 Two-level network chart of emergency logistics in Putuoshan Island

4.4 优化方法对比

为验证本文所采取的无人机配送中继站选址与卡车路径一体优化的效果，对同一算例设计选址与路径两段优化的策略，先确定无人机配送中继站的数量、选址，在此基础上进行卡车路径优化，求得系统总成本．两种优化方法求解结果对比如表4所示(以304个需求点为例)，将无人机配送中继站的数量、选址以及卡车路径同时进行优化的效果优于两段优化．通过设置不同的最大中继站建造数量，可以看出，随着最大中继站建造数量的增加，一体优化方法的总成本改进效果更明显．

表4 两种优化结果对比Tab.4 Comparison of two optimization results

5 结 语

海岛无人机配送中继站的选址-路径优化问题是影响海岛应急配送效率的关键性问题，对物资配送成本和物资转运灵活度有直接影响．本文针对海岛应急物流中引入无人机配送的特征，以系统配送总成本最小为目标，建立了海岛无人机配送中继站的选址-路径优化的双层规划模型．为了求解模型，设计了K-means聚类算法与改进的模拟退火算法相结合的两阶段算法．以浙江省舟山市普陀山海岛为背景，研究从朱家尖客运中心将一批物资运往普陀山海岛304个需求点的两级配送路径，在这些需求点中选取38个无人机配送中继站并为各个中继站所负责的配送区域规划卡车最优路线，使得系统总成本达到最低，为1 013.1元．与两段优化方法相比，本文所采用的一体优化方法使得系统总成本降低10.3%．

本文以无人机和卡车配送系统总成本最小为建模目标，但没有考虑无人机和卡车的容量限制，因此，考虑包含客户需求量和运载工具容量限制是未来研究的主要方向之一．此外，利用5G网络超强的信息传送能力，移动网络海量的站点资源可以为无人机提供从点到线再到面的立体覆盖，从而实现无人机超视距控制，随时掌控无人机的位置和空闲状况、安全状况等，将是无人机应急物流领域一个跨时代的新应用场景．