考虑跨区域条件下与非机动车协同配送的无人机起降点选址研究

Research on Unmanned Aerial Vehicles Landing Site Selection for Collaborative Delivery with Non-Motorized Vehicle under Cross-Regional Conditions

摘要: 外卖服务行业发展迅速，无人机凭借其无接触、可靠高效的特点受到广泛关注。但递送全程使用无人机成本高昂；传统的骑手递送模式在遇到江水等特殊地形时不可达或只能通过轮渡等方式通过，效率低下；商铺服务覆盖范围也因此削减。针对这一问题，提出非机动车–无人机协同配送模式，以经济成本最小为主要目标构建无人机起降点选址规划模型。引入关切系数，设计遗传算法，求得在寻非机动车最短路条件下的方案。最后通过算例表明服务覆盖面积提高了66.93%，成本较传统方式降低了26%，供无人机企业和政府决策者审度参考。

Abstract: The express logistics industry is experiencing rapid growth, with increasing interest in non-contact, reliable and efficient unmanned aerial vehicles (UAVs). But the high costs associated with full UAV deployment, low efficiency with traditional method in using food delivery riders which transit only by ferry when it need to cross the special terrain like rivers and decrease of store service scope pose challenges. To address these issues, a non-moterizd vehcle-UAV collaborative model is proposed. With minimal economic cost, an optimizing UAV landing site selection is constructed while design-ing a genetic algorithm and introducing concern coefficients. Then a scheme considering the short-est path for motorized vehicles is gained. By implementing it in a case model, service coverage is enhanced by 66.93% while achieving a 26% cost reduction compared to traditional methods. These findings provide valuable insights for UAV companies and government decision-makers.

1. 引言

如今，随着信息化全球化世界模式发展，全球同时仍然面临着突发公共事件带来的风险。无人机在物资运输压力剧增、无接触配送需求爆发的背景下 [1] ，可以稳定高效的满足用户需求。

在常态化运营的时期，非机动车被禁止通过隧道和桥梁，只能通过低效的轮渡等方式实现跨区域递送，甚至会无法满足一些非机动车不可达的区域订单需求。而无人机可以实现区域的互通。

在无人机独立完成配送任务方面：刘光才等 [2] 考虑经济成本和时间可靠性，设计了一种模拟改进模拟退火遗传算法，实现无人机起降点的布局规划；张洪海等 [3] 考虑不同等级的无人机起降点，设计人类学习优化算法对其进行布局求解。

在无人机协同配送方面：刘迎军 [4] 提出无人机和卡车协同的两种形式——相对独立完成任务和组合形成“移动仓库”的配送协同模式；张杰等 [5] 在疫情背景下，提出车辆运输商品到站点，站点用无人机配送用户需求的“车辆–无人机”协同模式；姜新岐 [6] 对车辆搭载多无人机的配送场景进行规划求解；林驿等 [7] 针对农村地区提出城乡客运班车 + 无人机的快递配送模式。

目前，国内将无人机协同非机动车用于配送的起降点选址问题研究较少。

本文从满足跨区域物流订单需求出发，考虑无人机与非机动车的协同配合下的地面路网限制，从经济成本方面入手，构建无人机起降点选址模型，并设计遗传算法对模型进行求解，得到满足条件的优化布局方案。本文创新点有① 主要考虑跨区域的物流订单需求；② 提出无人机与非机动车的协同配送模式；③ 将实际路网作为主要因素纳入无人机起降点的布局考虑；④ 考虑结点产生需求的权重；⑤ 考虑研究时间内不同时段的权重。

2. 问题建模

2.1. 问题描述

本文旨在完成跨区域无人机起降点布局规划，实现快递物流的全面覆盖。已知城市区域跨区跨地形物流需求分布，包括需求的订单数量，以及需求的请求点和响应点，两区域的无人机起降备选点。在无人机起降前后都由骑手取送件，完成订单和需求点和相应点的交互。骑手会在路网中选择无人机起降点与目标结点之间的最短路。通过无人机在两区域起降点间的运行，配合骑手，实现两区域快递订单的可达。为满足两区域间的物流需求，考虑降低成本提高效率的目标，无人机中转和骑手寻路的特征，从备选无人机起降点中确定最优的选址方案。本文技术路线如图1。

Figure 1. Technical roadmap

图1. 技术路线图

2.2. 假设

无人机的容量为每机每次满足一个订单需求，且忽略货物的体积和重量；

无人机之间不会相互影响；

起降点之间的空域均直线可达；

起降点内无人机数量充足，无须考虑无人机充电及返航问题；

所有的备选点可以服务到所有的需求；

非机动车地面配送与无人机中转为无缝衔接；

骑手在各个结点处数量充足；

骑手走最短路。

2.3. 模型构建

无人机物流配送在顾客、无人机企业、政府决策者等方面的注重点均不同，本文均衡各方要求，引入关切系数，构建以经济总成本最小化为目标的起降点选址模型。

2.3.1. 重要符合说明

将本文所使用符号进行分类整理，并进行含义说明，见表1。

Table 1. Symbol explanation

表1. 符号说明

2.3.2. 目标函数

$\min C={\omega }_1{C}_g+{\omega }_2{C}_y$ (1)

$C_g=c_g{\displaystyle \underset{i\in I}{\sum }{x}_i}+c_g{\displaystyle \underset{j\in J}{\sum }{x}_j}$ (2)

$C_y=n{c}_y{\displaystyle \underset{t\in T}{\sum }{\displaystyle \underset{l\in A_1}{\sum }{\displaystyle \underset{r\in A_2}{\sum }{\displaystyle \underset{i\in I}{\sum }{\displaystyle \underset{j\in J}{\sum }{\alpha }_t{\beta }_{lr}{x}_i{x}_j{y}_{ijlr}di{s}_{ijlr}}}}}}$ (3)

目标函数中，总成本C分为建设成本 $C_g$ 与运营成本 $C_y$ ，前面分别引入关切系数。建设成本 $C_g$ 表达为单位建设成本 $c_g$ 与建设个数的乘积；运营成本 $C_y$ 表达为单位运营成本 $c_y$ 与每单运距dis的乘积，其中引入结点产生需求或响应需求的权重系数β，研究时间内不同时段的权重系数α。

2.3.3. 约束条件

1) 每单只经过两区域各一个备选点

${\displaystyle \underset{l\in A_1}{\sum }{\displaystyle \underset{r\in A_2}{\sum }{y}_{lr}}}=1$ (4)

2) 方案中两区域各至少一个建设点

${\displaystyle \underset{i\in I}{\sum }{\displaystyle \underset{j\in J}{\sum }{x}_i}{x}_j}\ne 0$ (5)

3) 权重参数和为1

${\displaystyle \underset{t\in T}{\sum }{\alpha }_t}=1$ (6)

${\displaystyle \underset{l\in A_1}{\sum }{\displaystyle \underset{r\in A_2}{\sum }{\beta }_{lr}}}=1$ (7)

3. 算法设计

本文通过设计遗传算法 [8] 求解，计算得到基于跨区域需求的无人机起降点布局。

3.1. 编码解码

本文采用二进制0-1符号编码的方法进行染色体编码。每个染色体个体都指代了一种建设备选方案，其中染色体的奇数列基因为区域一的建设方案，偶数列基因为区域二的建设方案。染色体中的基因的列序号与实际中的起降备选点形成一一对应的双射映射。基因的“1”指代在本方案中，将对应编号的备选点建成起降点，“0”指代在本方案中，对应编号不进行无人机起降点的设置。

解码过程如图2，黑色表示“1”，白色表示“0”，图中的染色体表示该方案为区域一建设序号为①的起降点，同时区域二建设序号为④的起降点。

Figure 2. Decoding illustration

图2. 解码示意图

3.2. 建立适应度函数

本文所建立的规划模型为考虑经济成本的最小化目标，适应度设为

$C_s=\left(C_{\max }-C\right)+0.001$ (8)

式中：成本C为最小化目标，值越小，适应度越高； $C_{\max }$ 为种群中最高的成本；0.001是为了保证方案不被完全淘汰而引入的参数。

3.3. 基本步骤

Step1：依照目标区域，为所有的交通结点进行编号和以距离为固定道路阻抗标注，并让所有的建设备选点都以直线相互联通；

Step2：以结点对的形式输入所有订单需求；

Step3：选择具体方案，只将该建设方案下的路线视为通路，导入该方案的路网图，运用Dijkstra方法为所有订单计算最短路；

Step4：计算该方案的花费，并保留；

Step5：以同样的订单需求条件，计算种群中其他建设方案的花费；

Step6：计算整个种群的适应度；

Step7：交叉变异；

Step8：以适应度占总适应度的比值为选择概率，生成与亲代规模相同的子代种群；

Step9：当种群迭代预设值时，算法终止，输出目前的最佳方案。

遗传算法流程见图3，输入参数生成初始种群。

Figure 3. Genetic algorithm ıllustration

图3. 遗传算法示意图

4. 算例分析

4.1. 实验环境描述及参数标定

为验证建模与算法求解的有效性，使用PyCharm，ArcMap，TransCAD进行仿真实验，模拟上海南浦大桥3km范围内，沟通浦西浦东两岸的订单配送场景。假设浦东、浦西两区域共有227个订单需求响应点，其中共20个无人机起降备选点，道路378条，无人机空域线路100条。

在ArcMap中导入OSM地图，以南浦大桥为中心，3 km为半径，圈出圆形区域，作为底图。

将该底图导入TransCAD，画出路网，具体分布如图。

图4中黑色圆点和其旁边黑色数字为订单需求结点及其对应编号，红色圆点为无人机起降备选点，紫色实线为道路网和红色虚线为无人机线路网。

Figure 4. Distribution map of alternative landing sites

图4. 备选起降点分布图

基于当代物流订单配送流程和实验数据分析，参考文献参数设计，模型具体参数设计如表2。

Table 2. Parameter values

表2. 参数取值

此外，α，β两权重参数运用random()函数随机生成。

遗传算法的相关参数设置为：初始种群规模100；最大迭代次数50；变异概率0.005；交叉概率0.8。

4.2. 有效性验证

基于上述参数设置值，通过遗传算法进行求解得到的选址结果如图。红色实线为该方案建成无人机线路网。

左右两个区域从20个无人机起降备选点中选择([18, 16], [58, 52]) 4个点作为起降点，适应度最优，对应的日均经济成本为3789.0188元。

Figure 5. Solution result diagram

图5. 求解结果图

Figure 6. Iterative convergence illustration

图6. 迭代收敛示意图

如图5所示，红色圆点为最终起降点选址方案。起降点均匀分布两个区域。如图6所示，在模型在迭代次数在12次左右时目标函数收敛。

假设全部订单从南陆线由轮渡方式通过，非机动车可通行区域仍选择最短路，标定单位距离成本为3.5元，每单另有等待过河时间成本和轮渡船票成本共7元，计算预期成本为4774.4458元。对比用轮渡跨区域的方式进行订单的递送，无人机与非机动车协同配送模式成本降低了26%。

对于无法进行两区域互通的区域，如图7，以南浦大桥最近的店铺服务面积记，覆盖区域由原本的红色区域拓展出了绿色区域，覆盖范围提升了66.93%。

Figure 7. Coverage area illustration

图7. 覆盖面积示意图

至此实现了两区域的互通，物流订单的可达，满足了区域中产生的所有需求，并可以找到一个良好的经济适用建设方案。

4.3. 敏感性分析

在利用该算法对模型进行求解时，备选点的选取和经济成本及模型的收敛速度都会收到权重的影响。因此，进行如表3所示两组对照实验。

Table 3. Weight adjustment table

表3. 权重调整表

经过求解，组1选择起降点为([21, 18, 17, 16, 15], [9, 58, 49, 53, 51, 50]) 11个点，经济成本为5456.7150元；组2选择起降点为([20], [49]) 2个点，经济成本为1234.3548元。

观察求解结果图8(a)知，当更加关切运输成本时，预期经济成本会增加，建设起降点的数量会增加，建设点会分布于需求响应点密集的中心地带，两岸数量大致相同；观察求解结果图8(b)知，当更加关切建设成本时，预期经济成本会减少，建设起降点的数量会在满足连通性的要求下减少，建设点仍会分布于需求响应点密集的地带。

(a) (b)

Figure 8. Weight adjustment result diagram

图8. 调整权重结果图

5. 结论

5.1. 研究总结

本文针对跨区域物流订单的不可达问题，提出使用无人机，形成“非机动车–无人机–非机动车”的配送方法，满足跨区域物流订单需求。并进一步针对此模式下的快递物流无人机起降点进行布局规划，主要考虑经济成本，引入关切系数，设计遗传算法求解。基于上海市南浦大桥3 km范围内真实地理信息数据，构建227个需求响应结点的仿真实验。

结果表明，此算法可以有效的解决所构建模型问题。服务覆盖面积提高了66.93%，成本较传统方式降低了26%。本模型及算法可以用于跨区域物流无人机布局规划问题，所得结果受参数取值的影响。

5.2. 未来展望

在未来的实际规划中，可以在本文参数设置的基础上，替换当地实际物流订单数据。随着无人机相关技术的发展，无人机协同配送将更加成熟，后续将考虑实时变化订单信息，骑手任务分配等运营层面进一步对跨地区物流订单配送进行研究。