为了更好地推进城市无人机物流配送，需要解决选址-分配问题(LAP)。LAP最早由Curry, Skeith[3]于1969年提出。现阶段关于无人机的选址-分配研究，刘正元，王清华[4]提出无人机应急物流任务分配模型，为战场应急物资配送提供指导。陈刚，付江月[5]研究在军民融合战略背景下，基于需求点和配送中心类型建立无人机配送中心选址分配模型，并通过算例分析对模型进行验证，以期为特殊情况下无人机配送布局提供支持与帮助。Chauhan D等[6]以需求覆盖范围最大化为目标，考虑无人机能耗与飞行限制的影响，建立解决无人机最大覆盖设施位置问题的模型，并通过真实案例进行分析，从而明确无人机设施的选址点。刘光才，马寅松[7]研究了城市无人机配送中心选址及任务分配问题，构建了多约束条件下的模型，设计了改进模拟退火遗传算法，达到预期效果。

综上可知，当前关于无人机选址-分配问题的研究多针对军事作战领域，关于城市无人机物流配送这一特定场景下的LAP研究较少，没有综合考虑到城市、企业和客户三个视角。因此，本文考虑城市物流“最后一公里”配送需求，建立城市物流无人机选址-分配模型，并设计遗传-粒子群算法求解出优化方案。

1 数学模型建立

1.1 问题描述

在存在禁飞区或障碍区的城市区域内，已知每个备选配送中心的位置、建设成本和每个需求点的坐标、需求量等信息，根据区域范围内所有客户需求选取位置最合适的多个配送中心，将多个配送任务分配给不同配送中心的多架无人机执行，每架无人机装载规定重量的货物，从配送中心出发，分别飞往各个需求点，并且在完成配送任务后空载返回配送中心。当选择的配送中心与需求点之间存在禁飞区域或障碍区域，则该需求点的配送不选择此配送中心(图1)。

1.2 模型假设

为便于深入研究，本模型的主要假设如下：

①每个需求点的位置和需求量已知且恒定，在一定时间内无波动；

②每个需求点由一个配送中心(一架无人机)配送，每个配送中心可以覆盖多个需求点；

③物流无人机在配送过程中保持匀速，且忽略无人机起飞和降落过程；

④忽略自然天气对无人机配送过程的影响；

⑤在进行任务分配时，每架无人机单次只能为一个需求点服务，在完成需求点配送任务之后空载按原路返回配送中心。

1.3 目标函数构建

本模型以总成本最小为目标，包括建设成本C1、配送成本C2、耗电成本C3以及碳排放环境成本C4四个部分：

minC=C1+C2+C3+C4(1)

①配送中心建设成本。Xj=1或0表示是否在j点建设配送中心，固定建设成本为f。

C1=∑j∈JXj⋅f" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">C1=∑j∈JXj⋅f$?{}_1={\displaystyle \sum _{?\in ?}?}{}_{?}\cdot ?$(2)

②配送成本。每架参与配送的无人机，在一次可行的任务分配方案中，飞行距离djik" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">kji${}_{??}^{?}$与单位损耗成本λij的乘积为配送成本。Yijk" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">kij${}_{??}^{?}$=1或0,表示是否用无人机k来完成j配送中心对i客户的配送；Zijk" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">kij${}_{??}^{?}$=1或0,表示是否配送路径上不存在障碍。

C2=∑i∈Ι∑j∈J∑k∈Κdjik⋅λij⋅Yijk⋅Ζijk" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">C2=∑i∈I∑j∈J∑k∈Kdkji⋅λij⋅Ykij⋅Zkij$?{}_2={\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}?}}}{}_{??}^{?}\cdot ?{}_{??}\cdot ?{}_{??}^{?}\cdot ?{}_{??}^{?}$(3)

③耗电成本。耗电成本通过无人机的能耗E与单位电价p的乘积来表示。

C3=E·p (4)

与无人机的自重相比，每个包裹的重量都不容忽视。能耗[8]与自重φ和实时载荷Wijk" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">kij${}_{??}^{?}$相关，可表示为：

E=∑i∈Ι∑j∈J∑k∈Κ(φ+Wijk)⋅dij⋅Ρ370⋅η⋅γ⋅(Ρ-e)" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">E=∑i∈I∑j∈J∑k∈K(φ+Wkij)⋅dij⋅P370⋅η⋅γ⋅(P−e)$?={\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}}}}\frac{(?+?{}_{??}^{?})\cdot ?{}_{??}\cdot ?}{370\cdot ?\cdot ?\cdot (?-?)}$(5)

其中，η是电机的转换效率，γ是升阻比，e是无人机电池的能量损失，P为无人机最大飞行功率。

④碳排放环境成本。二氧化碳排放环境成本是指减少二氧化碳排放所产生的环境损失所需的费用。无人机在配送流程中只需要考虑上游企业发电所产生的碳排放，碳排放量的计算与电网排放因子θ有关。因此，电动无人机的二氧化碳排放环境成本可表示为：

C4=E·θ·α(6)

其中，α表示单位碳排放环境成本。

1.4 约束条件说明

①启用的配送中心数量约束。

启用的配送中心个数不大于备选配送中心的数量A。

∑j∈JXj≤A" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">∑j∈JXj≤A${\displaystyle \sum _{?\in ?}?}{}_{?}\le ?$(7)

②配送中心最大配送能力约束。

一个配送中心最多能为m个客户点服务。

∑i∈ΙXji≤m,∀j∈J" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">∑i∈IXji≤m,∀j∈J${\displaystyle \sum _{?\in ?}?}{}_{??}\le ?,\forall ?\in ?$(8)

③配送点可执行任务约束。

在一次可行的配送任务中，需要满足j地建设有配送中心，且用k无人机完成j地对i客户的配送。

Yijk" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">kij${}_{??}^{?}$≤Xj(9)

④无人机起降点位置约束。

无人机从配送中心出发完成配送任务后只能返回该配送中心，不能从一个配送中心出发后回到另一个配送中心。

∑i∈Ι∑k∈ΚXjik=∑i∈Ι∑k∈ΚXijk=1" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">∑i∈I∑k∈KXkji=∑i∈I∑k∈KXkij=1${\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}}}?{}_{??}^{?}={\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}}}?{}_{??}^{?}=1$(10)

∑j∈JXjj=0" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">∑j∈JXjj=0${\displaystyle \sum _{?\in ?}}?{}_{??}=0$(11)

⑤无人机最远里程约束。

分配给每架无人机的配送任务必须满足一次往返飞行距离不大于无人机的单次最远飞行里程限制Dmax。

∑i∈Ι∑j∈J2⋅Yijdij≤Dmax" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">∑i∈I∑j∈J2⋅Yijdij≤Dmax${\displaystyle \sum _{?\in ?}{\displaystyle \sum _{?\in ?}2}}\cdot ?{}_{??}?{}_{??}\le ?{}_{\max }$(12)

⑥无人机最大载重约束。

无人机每次配送任务的载重不大于最大载重限制Wmax。

Wijk" role="presentation" style="margin: 0px; padding: 0px; border: 0px; outline: 0px; background: transparent; display: inline; line-height: normal; text-indent: 0px; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative; font-size: inherit !important;">kij${}_{??}^{?}$≤Wmax(13)

2 算法设计

2.1 算法描述

在求解多配送中心选址-分配这类问题时，多采用智能化启发式算法。遗传算法和粒子群算法都是优化领域的经典算法，各自具有不同的优点和适用场景。

粒子群算法具有较强的局部搜索能力，且收敛速度快，但容易导致种群丧失多样性，容易陷入局部最优。而遗传算法具有较强的全局搜索能力，通过随机概率进行选择、杂交、变异，这种概率性特点增加了种群多样性，扩大了搜索空间。将这两种算法结合使用，可以取长补短，提高了算法的鲁棒性和适应性，发挥更强大的优势。

2.2 设计思路

①编码。

遗传算法的编码方法直接影响到了交叉算子、变异算子等遗传算子的运算，因此很大程度上决定了遗传进化的效率[9]。本文采用符号编码，设计m+n个基因表示配送中心选址和任务分配的结果，前m个基因作为客户需求点的编码，m+1至n为配送中心编码。

②种群规模。

种群大小代表算法中可以并行搜索的解的数量，过小的种群可能会导致陷入局部最优解；而过大的种群则会增加计算的复杂性，降低算法效率。

③适应度函数。

适应度函数是衡量粒子优劣的标准，以目标函数作为本文算法的适应度函数，总成本越小即目标函数越小。

④选择。

本文选用轮盘赌法选择粒子，计算每个粒子的适应度值，令fi为粒子i的适应度值，∑fi为群体的适应度值总和，那么粒子i产生后代的能力表示为fi/∑fi。

⑤交叉。

本文选用多点交叉方式，通过将父代染色体中的多个位置交换基因创建新的后代染色体。假设两条父代染色体分别是[2 6 1 7 10]和[4 5 8 3 9],交叉点位置为1和4,那么产生的后代染色体为[4 6 1 3 10]和[2 5 8 7 9]。

⑥变异。

本文采用均匀变异算子作为变异方法，对一条染色体以相同的概率随机改变基因值，设置变异概率的大小，若基因位置对应的随机数小于变异概率则发生变异，该基因变异为基因取值范围内的任意整数。

⑦迭代结束。

设置最大的迭代次数，当迭代次数达到最大值时，算法停止，返回当前最优解。

3 算例分析

3.1 仿真环境与参数设置

基于Python语言模拟某城市配送场景，在20km×20km区域范围内随机生成36个客户需求点、12个备选配送中心的坐标位置以及客户需求量。其中，“·”代表客户需求点的位置和编号，黑体数字为客户需求量，“○”表示备选配送中心的位置和编号(图2)。

为了使城市无人机规划过程尽量贴近实际配送场景，通过查阅文献和走访现代物流企业，设置模型的参数如表1所示。

3.2 结果分析

设置粒子群N=60,迭代次数MAXGEN=100,交叉概率Pc=0.8,变异概率Pm=0.05。分配方案如表2所示。

当从12个备选无人机配送中心中选择编号为2、4、7、8、9这5个配送中心时，适应度函数值最优，总飞行里程为313.90km,建设成本C1=10万元，配送成本C2=188.34元，耗电成本为C3=242.48元，碳排放环境成本C4=58.45元。

3.3 敏感性分析

3.3.1 空域约束

保持其他参数不变，改变空域环境中障碍区域的位置和数量，生成的选址-分配结果如图3所示。

当障碍区域数量增多时，选择2、4、8、9、11号配送中心成本最低，总飞行里程为338.2399km,配送中心建设成本C1=10万元，配送成本C2=202.94元，耗电成本C3=261.62元，碳排放环境成本C4=62.99元。

当障碍区域数量减少为0时，选择2、4、7、8、9号配送中心成本最低，总飞行里程为310.3855km,配送中心建设成本C1=10万元，配送成本C2=186.23元，耗电成本C3=240.08元，碳排放环境成本C4=57.81元。

结合图2和图3分析，城市无人机的配送中心选址-分配结果会受到空域环境中障碍数量和位置的影响。当障碍区域数量较多时，配送中心需要承担距离较远的配送需求，导致总成本上涨。

3.3.2 配送中心能力约束

保持其他参数不变，改变配送中心能力约束，生成选址-分配结果，如图4所示。

当配送中心的最大配送能力为6时(图4(a)),需要启用至少6个配送中心，此时的配送成本更小，但总成本因配送中心的启用数量增加而显著提升；当配送中心的最大配送能力为9时(图4(b)),配送中心的选址数量仅为4个，此时的配送成本更大，但总成本更小。

4 结语

本文针对单客户配送场景，以建设成本、配送成本、与载重相关的耗电成本以及碳排放环境成本之和最小为目标函数，以城市障碍区域、配送中心能力限制、无人机最大载重与最大续航里程等为约束条件，建立城市物流无人机配送中心选址-分配数学模型，设计遗传-粒子群算法求解，最后基于Python程序设计验证了本文模型与算法的有效性。