非支配排序粒子群遗传算法解决车辆位置路由问题

Non-dominated sorted particle swarm genetic algorithm to solve vehicle location routing problems

摘要

提出一种混合全局局部搜索的非支配排序粒子群遗传算法，该算法能够有效解决车辆位置路由问题。全局搜索使用粒子群和遗传算法以提高收敛速度，使用第三代非支配排序遗传算法挑选种群下一代个体以保留种群多样性。局部搜索策略针对优质和次优个体进行优化，以提高得到更优解的概率，对种群中后1/12个体打乱用户顺序，提高种群质量。使用开放标准数据集将本文算法与基准算法对比，结果表明本文算法在种群质量、多样性上均更优，能够为车辆位置路由问题提供有效的解决方案。

Abstract

A non-dominated sorted particle swarm genetic algorithm with hybrid global-local search is proposed， by which the vehicle location routing problem can be effectively solved. Both particle swarm optimization and genetic algorithm operators are utilized in the global search to improve convergence speed. The non-dominated sorting genetic algorithm III is employed so that population diversity is maintained. The local search strategy is applied separately to superior and inferior individuals， by which the probability of obtaining better solutions is increased. Additionally， the user orders of the last 1/12 individuals in the population are shuffled so that the overall population quality is enhanced. The proposed algorithm is compared with benchmark algorithms by using the open standard dataset， and it is demonstrated that population quality and diversity are better provided， and an effective solution to the vehicle location routing problem can be supplied.

Graphical abstract

关键词

计算机应用 / 车辆位置路由问题 / 第三代非支配排序遗传算法 / 粒子群算法 / 遗传算法

Key words

computer application / vehicle location routing problem / non­dominated sorting genetic algorithm III / particle swarm optimization algorithm / genetic algorithm

0 引　言

车辆位置路由问题（Location­routing problem， LRP）是车辆任务调度领域的经典问题，可以拆分为位置分配问题（Location­allocation problem， LAP）和车辆路径问题（Vehicles routing problem， VRP）^［1］。Laporte等^［2］在1986年描述了经典的LRP，该问题需要从潜在设施位置中选择最优位置，并规划从仓库出发对用户服务的车辆路线。

针对LRP，Barreto等^［3］对LAP和VRP分开进行解决。然而，Salhi等^［4］指出，同时考虑LAP和VRP通常会得到更优解。Perl等^［5］在此基础上同时分析LAP和VRP，使用启发式算法来解决LRP。元启发式算法是解决LRP的途径之一。Huang等^［6］使用蚁群优化算法解决无人机配送服务的VRP。Ma等^［7］使用遗传算法解决自动驾驶汽车的LRP。胡圣邦等^［8］考虑安全目标和时间目标双重属性，使用改进的蚁群算法选择运输路线。杜玟谛等^［9］构建车辆路径优化模型，利用改进蚁群算法进行模型求解。

进化多目标优化（Evolutionary multi­objective­optimization， EMO）也是解决 LRP的有效途径之一。目前，多目标优化在方法和应用领域均取得了大量的成果，如第二代强度Pareto进化算法（Strength Pareto evolutionary algorithm 2，SPEA2）^［10］、第二代非支配排序遗传算法（Non­dominated sorting genetic algorithm II，NSGA­II）^［11］和第三代非支配排序遗传算法（Non­dominated sorting genetic algorithm III，NSGA-III）^［12］。Rabbani等^［13］首先将NSGA­II应用于双目标的LRP中。杨红波等^［14］提出了齿轮副宏观参数多目标优化方法，利用NSGA­II解决多个优化目标的冲突。Hernandez等^［15］将NSGA­III应用于求解多目标优化问题，并取得了不错的效果。该类算法通过参考点将目标空间分解为子空间进行并行搜索，该类算法典型代表有TC­SEA^［16］、I­DBEA^［17］和RVEA^［18］。

虽然已有很多方法用于求解LRP，但很少有学者将两种元启发式算法和EMO算法结合来解决LRP。考虑到粒子群算法（Particle swarm optimization， PSO）能够提高收敛效率，遗传算法（Genetic algorithm， GA）能够避免陷入局部最优^［19］，而NSGA-III能够找到收敛良好且多样化的解^［20］，本文将PSO、GA和NSGA-III三者结合，提出混合全局局部搜索的非支配排序粒子群遗传算法（Hybrid global­local search non­dominated sorting particle swarm optimization­genetic algorithm， HSNS-PSOGA）。针对种群多样性和收敛性差的问题，全局搜索策略主要采用PSO，选择机制为NSGA-III；针对种群多样性差和解的分布不均匀问题，对优质个体和次优个体分别进行反转、交换和插入操作，同时对种群中后1/12个体打乱用户顺序。实验结果表明，本文提出的HSNS-PSOGA在大多数情况下优于基准算法。

1 车辆位置路由问题分析

1.1　问题描述

针对本文研究的LRP，描述如下：给定候选仓库位置，每个仓库可以派遣车辆服务用户，其中车辆容量有限，车辆数目无限，另外已知用户位置和需求。要求从候选仓库中选择一定数量的仓库，该问题被称为LAP；确定从仓库出发的车辆数目及行驶路线，该问题被称为VRP。LRP中，减少车辆使用数量，可能需要将车辆分配给较远的用户，从而增加路由距离；而减小路由距离，可能会使车辆行驶成本较高的路径。因此，LRP是一个多目标优化问题，需要最优化的3个目标是车辆数量，车辆路由距离和车辆路由成本。

令I为候选仓库集合，J为用户顶点集合，V为顶点集合且V=I∪J，K为车辆序列，u_k =1表示第k辆车被使用，x_i，j，k =1表示第k辆车的行驶路由覆盖点i到j的边，d_i.j 为顶点i到j的路由距离，c_i，j 为顶点i到j的路由代价。3个目标函数的数学化描述为：

f_{\mathrm{1}}\left(x\right)=\sum _{k\in K}{u}_k（1）

f_{\mathrm{2}}\left(x\right)=\sum _{i\in I,j\in V,k\in K}{d}_{i,j}{x}_{i,j,k}（2）

f_{\mathrm{3}}\left(x\right)=\sum _{i\in I,j\in V,k\in K}{c}_{i,j}{x}_{i,j,k}（3）

式中：f₁（x）为最小化车辆使用数量目标函数；f₂（x）为最小化车辆派送路线的总距离目标函数；f₃（x）为最小化车辆派送路线产生的总代价成本目标函数。

3个优化目标存在竞争关系且重要性相当，因此需要根据染色体计算个体在3个目标上的取值，再考虑Pareto支配关系来判断解的优劣。

令K_a 为被分配任务的车辆序列，z_j，k =1表示第k辆车被分配服务用户j，q_i 为用户顶点需求，q为车辆的货物负载量。

本文研究的车辆LRP有以下4个约束条件：式（4）确保每个用户只被一辆车服务，式（5）确保一辆车服务用户的总需求不超过其负载能力，式（6）确保每辆车最多执行一次派送，式（7）确保每条完整路由的起点和终点为同一仓库。

\sum _{k\in K_a}{z}_{j,k}=\mathrm{1},\forall j\in J（4）

\sum _{j\in J}{q}_j{z}_{j,k}\le q,\forall k\in K_a（5）

\sum _{i\in I}\sum _{j\in J}{x}_{i,j,k}=\mathrm{1},\forall k\in K_a（6）

\sum _{i\in I}\sum _{j\in J}{x}_{i,j,k}=\sum _{i\mathrm{\text{'}}\in I}\sum _{j\mathrm{\text{'}}\in J}{x}_{i\mathrm{\text{'}},j\mathrm{\text{'}},k}=\mathrm{1},\forall k\in K_a,i=i\mathrm{\text{'}}（7）

约束条件在1.2节染色体编码与解码中体现。

1.2　染色体编码与解码

针对染色体无法对应可行解的问题，本文使用以下编码方式：假设用户个数为|J|，仓库个数为|I|，令解向量的长度为|J|+|I|-1，解向量的每一维取值均为1到|J|+|I|-1的整数。其中，仓库从0开始编号，用户从|I|开始编号，染色体第一维度默认为0。

这种编码方式的含义为：相邻两个仓库之间的用户由前一个仓库服务。若车辆服务用户的总需求超出车辆容量，为了满足式（5）对应约束，由当前仓库派遣新的车辆。由于每个仓库车辆数量没有限制，可以保证仓库每次派遣车辆不同，满足式（6）对应约束。

如图1所示，假设共有3个仓库、8个用户，则仓库编号为0~2，用户编号为3~10，编号为0的仓库（0号仓库）服务第3、8号用户，1号仓库服务第7、4、9号用户，2号仓库服务第5、6、10号用户。图1所示编码方案对应的解决方案如图2所示。

图2中，由于第7、4号用户总需求超出了车辆容量，则派遣新的车辆进行服务。

解向量每一维取值不重复出现（详细方法见2.1节染色体归一化），保证每个用户只被一个仓库服务，满足式（4）对应约束条件。确定仓库服务的用户后，根据车辆容量和用户需求进行派遣，对应式（5）（6）。相邻两个仓库之间的用户由前一个仓库服务，对应式（7）。

2 算法描述

PSO算法能够提高收敛效率，而GA有助于避免陷入局部最优^［19］。为了平衡种群多样性和收敛性，本文算法流程见算法1。

算法 1 HSNS-PSOGA

Input：优化问题MOP，最大迭代次数max_gen，种群规模N

Output：结果集EP

1：初始化参考点init_refpointsND（）；

2：初始化粒子位置与速度init_population（）；

3：while（gen<max_gen） do

4：Global Search（）；

5：Local Search（）；

6：gen=gen+1；

7：end while

首先初始化参考点和种群，接着进行全局搜索：全局搜索中使用PSO算法，同时结合GA的交叉变异算子对个体进行优化，之后使用NSGA-III选择个体，产生子代群体P_t+1。随后进行局部搜索，对P_t+1中的优质、次优个体进一步改进，再更新后1/12个体。

2.1　全局搜索策略

针对种群收敛性差的问题，全局搜索策略采用PSO算法^［21］，首先初始化父代种群P_t，之后对种群中第i个粒子使用粒子群变化算子：

{\mathit{v}}_i\left(t+\mathrm{1}\right)=\omega {\mathit{v}}_i\left(t\right)+c_{\mathrm{1}}{r}_{\mathrm{1}}\left({\mathit{x}}_{\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}{\mathrm{t}}_i}-{\mathit{x}}_i\left(t\right)\right)+

c_{\mathrm{2}}{r}_{\mathrm{2}}\left({\mathit{x}}_{\mathrm{g}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}-{\mathit{x}}_i\left(t\right)\right)（8）

{\mathit{x}}_i\left(t+\mathrm{1}\right)={\mathit{x}}_i\left(t\right)+\mathit{v}\left(t+\mathrm{1}\right)（9）

式中：{\mathit{v}}_i粒子i的速度；{\mathit{x}}_{\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}{\mathrm{t}}_i}为粒子i的历史最优解；{\mathit{x}}_{\mathrm{g}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}为整个种群的全局最优解；ω为动态惯性权重；c₁和c₂为加速因子；r₁和r₂为［0，1］的随机数； x_i 为粒子i的位置；t为迭代轮数。

为了确保每个用户只被一辆车服务（满足式（4）约束），需要保证解向量每一维取值为唯一整数。因此，需要对更新后的粒子坐标进行处理，下面给出了染色体归一化过程：

假设粒子坐标 X =（x₁，x₂，…，x_n ），其中n=|J|+|I|-1。

（1）设元组集合V=｛（x_i，i）|1≤i≤n｝，每个元组包含维度值x_i 和维度i。

（2）对集合V中元组按照x_i 升序排列，得到V\text{'}=\{(x_{i_{\mathrm{1}}},i_{\mathrm{1}}),(x_{i_{\mathrm{2}}},i_{\mathrm{2}}),\dots ,(x_{i_n},i_n)\}，其中x_{i_{\mathrm{1}}}\le x_{i_{\mathrm{2}}}\le \dots \le x_{i_n}。

（3）令D=｛（i_j，j）|1≤j≤n｝，其中j表示排序后的序号。

（4）将第j小的维度i_j 赋值为j，即x_{i_j}=j。

根据染色体计算粒子在3个目标函数上的取值，若存在粒子i的解Pareto支配{\mathit{x}}_{\mathrm{p}\mathrm{b}\mathrm{e}\mathrm{s}{\mathrm{t}}_i}或 x_gbest，则进行更新。

对种群中个体使用PSO算法之后，使用GA的交叉和变异算子对临时子代种群E_t 进行交叉变异操作，形成子代种群Q_t。对于交叉操作，生成随机数p，获取染色体A在位置p的值a，即A［p］=a，在染色体B中找到值为a的位置q，并获取A在位置q的值b，即A［q］=b，将A和B各自的a、b交换。对于变异操作，生成随机下标p、q，交换染色体C在p、q位置的元素。交叉和变异操作见图3。

为了解决种群多样性差的问题，使用NSGA-III对父子代合并后的2N个体进行选择，具体选择过程见算法2的4~16行。NSGA-III通过精英策略，能够保证种群中优质父代被保留；其基于均匀分布的参考点选择个体，能够保证解的多样性。全局搜索算法流程见算法2。

算法 2 GLOBAL SEARCH

Input：结构化参考点序列B，父代种群P_t

Output：子代种群P_t+1

1:对P_t使用PSO算法变化算子产生E_t

2:对E_t使用GA变化算子产生Q_t

3:将Q_t中每个新个体与原个体对比，如果新个体Pareto支配原个体，替换原个体

4:R_t=P_t∪Q_t

5:对R_t进行非支配排序生成多个非支配层：F₁,F₂,…

6:S_t=\mathrm{\varnothing }, i=1

7:repeat

8:S_t=S_t∪F_i, i=i+1

9:until | S_t |≥ N

10:if | S_t | = N then

11: P_t+1 = S_t

12:else P_{t+\mathrm{1}}={\Sigma }_{j=\mathrm{1}}^{l-\mathrm{1}}{F}_j

13:对S_t的所有解在各个目标函数维度上自适应归一化

14:根据自适应归一化后的S_t，将每个个体与在超平面上距离最近的参考点相关联

15:根据参考点相关联的个体数量，挑选K=N-|P_t+1|个个体加入P_t+1中

16:选择关联个体数量最少的参考点，从参考点相关联个体集合中选择属于F₁支配层个体，与当前全局最优个体对比，挑选更优解作为新的全局最优解

17:end if

2.2　局部搜索策略

本文对优势个体进行局部搜索，以提高获得更优解的概率；对种群中次优个体进行局部搜索，以减少Pareto支配解的个数，提高整个种群的质量并加快收敛；对后1/12个体打乱用户顺序，以增加种群多样性。局部搜索算法流程见算法3。

算法 3 LOCAL SEARCH

Input：经过全局搜索得到的子代种群P_t+1

Output：局部搜索过后的子代种群P_t+1

1:随机选择参考平面B中的一个参考点作为λ值

2:计算P_t+1中每个个体的聚合函数值

3:i=1

4:repeat

5:以无放回锦标赛方式选择一个个体x，使用三种局部搜索变化算子得到新个体x′，i=i+1

6:判断新个体x′是否能够Pareto支配任意一个P_t+1中的个体，如果是则替换该个体进入P_t+1，否则放弃该新个体

7:对P_t+1中的所有Pareto支配解{\Sigma }_{j=\mathrm{2}}^l{P}_{t+\mathrm{1}}进行局部搜索，使用3种变化算子得到新个体x′′

8:如果x′′属于非支配Pareto解，x′′替换x进入P_t+1，否则放弃该新个体

9:until i=T_local

10:对P_t+1中后1/12的个体进行用户顺序的打乱

11:如果新解Pareto支配原解，替换

文献［22］表明，在局部搜索中，基于聚合函数选择优质个体比基于Pareto排序更有效，本文使用目标函数的加权和作为聚合函数，公式为：

f^{\mathrm{*}}\left(x\right)={\lambda }_{\mathrm{1}}{f}_{\mathrm{1}}^i\left(x\right)+{\lambda }_{\mathrm{2}}{f}_{\mathrm{2}}^i\left(x\right)+{\lambda }_{\mathrm{3}}{f}_{\mathrm{3}}^i\left(x\right),

{\lambda }_{\mathrm{1}}+{\lambda }_{\mathrm{2}}+{\lambda }_{\mathrm{3}}=\mathrm{1}（10）

式中：λ₁、λ₂、λ₃为参考平面上随机点在3个维度的取值；f_{\mathrm{1}}^i\left(x\right)、f_{\mathrm{2}}^i\left(x\right)、f_{\mathrm{3}}^i\left(x\right)为个体i对应的3个目标函数值。

以式（10）作为衡量标准，并使用无放回的锦标赛方法^［23］选择优质个体进行局部搜索。每次随机选择两个个体进行比较，选择f^*（x）值更小的个体进入优质种群。对优质种群采用反转、交换和插入3种变异操作：反转是指反转个体向量中的一段；交换是对个体向量中的两位编码进行位置交换；插入是从个体向量中截取一段插入首位。上述过程重复N×P次，其中P为对N个个体进行局部搜索的概率。如果新解x′能够Pareto支配种群中的任一个体x″，则用x′代替x″。通过对优质个体进行局部搜索，能够以一定概率寻找到更加优质的个体，解决种群收敛性差的问题。

除对优质个体进行局部搜索外，本文还对除 F₁ 层中的次优个体（P_t+1/F₁）进行局部搜索，以提高种群整体解的质量。对每个次优个体y，通过反转、交换和插入操作得到y′。若P_t+1/F₁中没有个体Pareto支配y′，则以y′替换y。对次优个体进行的局部搜索由于引入了GA的变化算子，既能在一定程度上增加种群的多样性，又可提高次优个体的质量。

对次优个体局部搜索后，对种群后1/12个体进行用户顺序打乱，具体做法为：保持仓库编号不变，将两个仓库编号之间的用户编号随机打乱顺序；若更新后的解Pareto支配原解，则进行替换。这种做法考虑到仓库选取和其服务的用户已经最优，但车辆的行驶路线可能因为服务的用户顺序没有达到最优。通过打乱后1/12个体的用户顺序，提高了种群多样性。

3 实验结果与分析

为证明HSNS-PSOGA的有效性，设置了对比实验，对比算法分别为NSGA-II^［11］、NSGA-II+PSO^［24］、NSGA-III^［12］、NSGA-III+PSO^［25］。NSGA-II和NSGA-III是多目标优化领域的经典算法，NSGA-II+PSO和NSGA-III+PSO是将EMO算法和元启发式算法相结合的改进算法。同时，本文设计了消融实验，以证明对优质、次优个体局部搜索，使用PSO算法和对后1/12个体打乱用户顺序的合理性。另外，本文对用户顺序打乱比例进行了实验分析。实验在所有测试问题上均独立运行30次。

3.1　数据集

在本次实验中，使用的数据集来源于KBAM、KBSN、KPAM、KPSN、YLBAM、YLBSN、YLPAM、YLPSN八组数据集。每组数据集的每组数据均提供了用户的位置坐标、用户需求、待选择仓库的位置坐标、车辆容量，另外有距离矩阵提供路由距离成本。本次实验从KBSN数据集中的30组数据中随机选择10组数据进行测试，这10组数据中，每个实例的用户个数取值为8~100，仓库个数取值为2~10。通过实例的名称能够得到用户和仓库的数量，如Bar_32_5_X_NGaskell67_32x5_1，包含32个用户和5个仓库。本文使用KBSN提供的10个实例并结合随机生成的道路路由成本进行实验。

3.2　性能指标

为了更好地说明HSNS-PSOGA的有效性，本文的对比指标除车辆使用数量、车辆路由距离成本、车辆路由代价3个目标函数之外，还设计了SM1（Spacing metrics 1）、SM2（Spacing metrics 2）和DM（Diversification metrics）指标。

SM1能够衡量解的分布均匀性，其值越小代表均匀性越好，其计算公式如下：

\mathrm{S}\mathrm{M}\mathrm{1}=\sqrt[]{\frac{\mathrm{1}}{N-\mathrm{1}}\times {\displaystyle \sum _{i=\mathrm{1}}^N}{\left(\mathrm{d}\mathrm{i}{\mathrm{s}}_i-\overline{\mathrm{d}\mathrm{i}\mathrm{s}}\right)}^{\mathrm{2}}}（11）

式中：dis _i 为第i个解与Pareto最优解集中最接近它的解之间的欧氏距离；\overline{\mathrm{d}\mathrm{i}\mathrm{s}}为所有dis _i 求和取平均；N为种群中个体总数。

SM2能够有效表示Pareto最优解在目标空间中的分布情况，取值越小越好，其计算公式见式（12）。

\mathrm{S}\mathrm{M}\mathrm{2}=\sqrt[]{\frac{\mathrm{1}}{N-\mathrm{1}}\times \sum {\left(d_i-\overline{d}\right)}^{\mathrm{2}}}（12）

\begin{array}{l}{d}_i=\underset{j}{\mathrm{m}\mathrm{i}\mathrm{n}}(|f_{\mathrm{1}}^i\left(x\right)-f_{\mathrm{1}}^j\left(x\right)|+\\ |f_{\mathrm{2}}^i\left(x\right)-f_{\mathrm{2}}^j\left(x\right)|+|f_{\mathrm{3}}^i\left(x\right)-f_{\mathrm{3}}^j\left(x\right)|)i\end{array}（13）

式中：i，j=\mathrm{1,2},\dots ,N；\overline{d}为所有d_i 的平均值；f_{\mathrm{1}}^i、f_{\mathrm{2}}^i、f_{\mathrm{3}}^i为第i个个体的3个目标函数值；f_{\mathrm{1}}^j、f_{\mathrm{2}}^j、f_{\mathrm{3}}^j为第j个个体的3个目标函数值。

DM为Pareto最优解集中个体分布多样性，取值越大越好，其计算公式如下：

\mathrm{D}\mathrm{M}=\sqrt[]{{\displaystyle \sum _{i=\mathrm{1}}^N}\mathrm{m}\mathrm{a}\mathrm{x}\left(||x_t^i-y_t^i||\right)}（14）

式中：\mathrm{m}\mathrm{a}\mathrm{x}\left(||x_t^i-y_t^i||\right)为Pareto最优解x_t^i和y_t^i最大的欧氏距离，t为Pareto最优解不再发生变化时的迭代轮数。

3.3　对比实验

本文设置了对比实验，将HSNS-PSOGA与NSGA-II、NSGA-II+PSO、NSGA-III、NSGA-III+PSO进行对比，实验结果如表1所示。

通过对比可以看出，HSNS-PSOGA取得了更好的效果。在10个实例中的3个目标函数表现方面，本文算法多数情况优于NSGA-II、NSGA-II+PSO、NSGA-III、NSGA-III+PSO：SM1和SM2在第1、2、5、9个数据集上的表现更好；针对DM指标，本文算法在7个实例中的表现更优，说明HSNS-PSOGA分布多样性较好，这在一定程度上也说明HSNS-PSOGA能够尽可能避免局部最优。

在目标数为M、个体数为N、迭代次数为T的情况下，NSGA-II和NSGA-III的计算复杂度为O（TMN²），PSO的计算复杂度为O（TMN），NSGA-II+PSO、NSGA-III+PSO的计算复杂度为O（TMN²）=O（TMN²）+O（TMN）。全局搜索中，GA计算复杂度为O（TMN），局部搜索计算复杂度为O（TMN²），因此HSNS-PSOGA计算复杂度为O（TMN²）。通过对比可以看出，本文提出的HSNS-PSOGA在不增加计算复杂度的同时能够取得更优的结果。

3.4　消融实验

如图2所示，为验证HSNS-PSOGA的可行

性，本文设计了消融实验，分别将本文算法与本文算法-PSO、本文算法-GA、本文算法-聚合函数选择优质个体局部搜索、本文算法-次优个体局部搜索以及本文算法-对种群中后1/12个体进行局部搜索进行了对比。

由消融实验结果可知，本文算法-PSO的收敛迭代次数更少，表明通过PSO能够提高收敛速率。本文算法-GA的DM值更小，说明解的多样性差，证明通过GA能够增加多样性，避免陷入局部最优。通过优质个体局部搜索能够减小SM1值，增加解的均匀性。通过次优个体局部搜索，SM2值有明显的减小，说明Pareto最优解在目标空间中的分布情况更好；DM的取值更大，说明解的多样性得到了提升，因此，通过次优个体局部搜索能够提升种群的质量。对种群中后1/12的个体打乱用户顺序后，DM值更大，说明多样性更好。

3.5　参数选择

在局部搜索策略中，选择对部分个体打乱用户顺序，本文设计打乱比例为1/6、1/12、1/24，以探究打乱比例对算法性能的影响。实验结果如表3。

由表3结果可知，比例选取为1/12时，整体效果最好，在3个目标函数上的取值更优，在第2、3、6、7、10个数据集上SM1指标更好，在第2、5、8、10个数据集上SM2指标更好，说明解的分布更均匀，在第2、4、5、8、10个数据集上DM指标更好，说明种群多样性更好。分析原因为：打乱比例选取为1/6时，种群中更新比例大，可能陷入局部最优；打乱比例选取为1/24时，更新比例较小，对算法优化效果有限，难以找到全局最优解。

4 结束语

本文提出的HSNS-PSOGA结合了EMO算法与元启发式算法，能够在一定程度上平衡收敛性和多样性，同时提高解的均匀性。实验结果显示，全局搜索使用PSO算法和GA，能够加快收敛同时避免陷入局部最优；使用NSGA-III选择机制，可以在一定程度上保证种群的多样性；局部搜索分别对优质和次优个体进行搜索，提高了获得更优解的概率并增加了Pareto最优解的多样性；对种群中后1/12的个体进行局部搜索，提升了解的均匀性。在公开数据集上进行验证，本文所提算法在大多数情况下更优。但本文所提算法在较大规模数据集上的表现优势并不明显，下一步的研究中将探索该问题。

参考文献

[1] Toth P, Vigo D. The vehicle routing problem: Society for industrial and applied mathematics[J]. Siam Monographs on Discrete Mathematics and Applications, 2001,8(3): 135-176.

[2] Laporte G, Nobert Y, Arpin D. An exact algorithm for solving a capacitated location-routing problem [J]. Annals of Operations Research, 1986, 6(9): 291-310.

[3] Barreto S, Ferreira C, Paixao J, et al. Using clustering analysis in a capacitated location-routing problem[J]. European Journal of Operational Research, 2007, 179(3): 968-977.

[4] Salhi S, Rand G K. The effect of ignoring routes when locating depots[J]. European Journal of Operational Research, 1989, 39(2): 150-156.

[5] Perl J, Daskin M S. A warehouse location-routing problem[J]. Transportation Research Part B: Methodological, 1985, 19(5): 381-396.

[6] Huang S H, Huang Y H, Blazquez C A, et al. Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm[J]. Advanced Engineering Informatics, 2022, 51: No.101536.

[7] Ma B, Hu D, Wu X. The location routing problem of the car-sharing system with autonomous electric vehicles[J]. KSCE Journal of Civil Engineering, 2021, 25(8): 3107-3120.

[8] 胡圣邦, 袁小芳, 郭琳. 改进蚁群算法的民爆物品运输路线优化[J]. 公路交通科技, 2023, 40(3): 247-253.

[9] Hu Sheng-bang, Yuan Xiao-fang, Guo Lin. Improvement of ant colony algorithm for the optimization of transportation routes of civil explosives[J]. Highway Transportation Science and Technology, 2023, 40(3): 247-253.

[10] 杜玟谛, 张虹. 基于改进蚁群算法的危险化学品运输路径优化[J]. 科技风, 2023(7): 153-156.

[11] Du Wen-di, Zhang Hong. Optimization of hazardous chemical transportation route based on improved ant colony algorithm[J]. Science and Technology Wind, 2023(7): 153-156.

[12] Deb K, Mohan M, Mishra S. Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of pareto optimal solutions[J]. Evolutionary Computation, 2005, 13(4): 501-525.

[13] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSAGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[14] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2013, 18(4): 577-601.

[15] Rabbani M, Farrokhi-Asl H, Asgarian B. Solving a bi-objective location routing problem by a NSGA-II combined with clustering approach: Application in waste collection problem[J]. Journal of Industrial Engineering International, 2017, 13(1): 13-27.

[16] 杨红波, 史文库, 陈志勇, 等. 基于NSGA-II的斜齿轮宏观参数多目标优化[J].吉林大学学报:工学版, 2023, 53(4): 1007-1018.

[17] Yang Hong-bo, Shi Wen-ku, Chen Zhi-yong, et al. Multi-objective optimization of macro-parameters of helical gears based on NSGA-II[J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(4): 1007-1018.

[18] Hernandez C, Lara J, Arjona M A, et al. Electromagnetic optimal design of a PMSG considering three objectives and using NSGA-III[J]. IEEE Transactions on Magnetics, 2022, 58(9): 1-4.

[19] Moen H J F, Hansen N B, Hovland H, et al. Many-objective optimization using taxi-cab surface evolutionary algorithm[C]∥The 7th International Conference on Evolutionary Multi-Criterion Optimization, Sheffield, UK, 2013: 128-142.

[20] Asafuddoula M, Ray T, Sarker R. A decomposition-based evolutionary algorithm for many objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 19(3): 445-460.

[21] Cheng R, Jin Y, Olhofer M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773-791.

[22] Shi L, Gong J, Zhai C. Application of a hybrid PSO-GA optimization algorithm in determining pyrolysis kinetics of biomass[J]. Fuel, 2022, 323: No.124344.

[23] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2013, 18(4): 577-601.

[24] Poli R, Kennedy J, Blackwell T. Particle swarm optimisation[J]. Journal of Xidian University, 1995, 42(1): 16-22.

[25] Ishibuchi H, Narukawa K. Some issues on the implementation of local search in evolutionary multiobjective optimization[C]∥Genetic and Evolutionary Computation Conference, Berlin, Heidelberg, 2004: 1246-1258.

[26] Yang J, Soh C K. Structural optimization by genetic algorithms with tournament selection[J]. Journal of Computing in Civil Engineering, 1997, 11(3): 195-200.

[27] Sasikumar A, Muthaiah R. Operational amplifier circuit sizing based on NSGA-II and particle swarm optimization[C]∥International Conference on Networks & Advances in Computational Technologies(NetACT), Thiruvanthapuram, India, 2017: 64-68.

[28] Masood A, Mei Y, Chen G, et al. A PSO-based reference point adaption method for genetic programming hyper-heuristic in many-objective job shop scheduling[C]∥Third Australasian Conference on Artificial Life and Computational Intelligence, Sydney,Australia, 2017: 326-338.

基金资助

国家自然科学基金项目(62072039)