1. 引言

多目标优化问题(Multi-objective optimization problems, MOPs)是一类特殊的优化问题，旨在同时优化多个相互冲突的目标函数。在多个领域均有广泛应用。例如，在工程学、生物学和经济学领域[1]-[4]。如果一个多目标优化问题考虑多个不同的场景，则被定义为多场景优化问题(Multi-scenario optimization problem, MSOP)，这是近年来出现的一个概念。MSOP与多任务优化问题(Multi-task optimization problem, MTOP)类似，都涉及同时优化多个任务。然而，区别在于MTOP为每个任务提供一组独特的解决方案，而MSOP旨在找到一组共同的解决方案，以满足不同场景的目标。带容量约束的车辆路径问题(CVRP) [5]是一个经典的多目标组合优化问题，旨在通过规划最优车辆路径来最小化总行驶距离或成本，同时满足客户需求和车辆容量约束。多场景带容量车辆路径问题(MSCVRP)是CVRP的扩展，考虑了不同现实场景中的配送情况。尽管每个场景可能不会同时发生，但它们在长时间内具有不同的发生概率。因此，有必要找到一组在所有场景中都可行的折中解，以便多个场景尽可能实现最优函数值。例如，由于良好天气和恶劣天气之间的配送条件(例如，驾驶速度、交通拥堵、成本条件)的差异，良好天气和恶劣天气可以被定义为两个不同的配送场景。对于MSOP，能够在所有场景中处理每个场景并实现折中最优性的解集被标记为公共折中最优解(Public compromise optimal solution, PCOS) [6] [7]。

解决MSCVRP的关键点可以总结如下：

1) 哪些解可以被定义为PCOS。在所有场景中表现出良好收敛性和多样性的解可以被定义为PCOS，在一个场景中表现良好但在另一个场景中表现不佳的解不被视为PCOS。

2) 如何获得PCOS。并行进化算法通常用于同时优化多个场景，每个场景涉及多个复杂问题，不同场景之间的知识迁移有助于找到PCOS。

3) 如何确保PCOS的最优性。对于同一个场景，算子选择策略的合理性直接影响PCOS的质量。不同交叉算子的设计目标和适用场景各不相同，对解的搜索能力和局部优化能力有显著影响。

为了解决上述关键问题，本文提出了一种基于并行进化框架的多场景带容量车辆路径优化算法(Multi-scenario capacitated vehicle routing optimization algorithm based on parallel evolution framework, PEF-MSOA)，该算法用于并行优化多个场景。在PEF-MSOA的一次迭代中，设计了一种高效的知识转移策略，以在不同场景间选择出PCOS。此外，构建了一种自适应选择交叉算子策略，以提高PCOS的质量。通过PEF-MSOA，实现了不同场景之间的信息交换，提高了优化效果和效率，能用于有效地解决MSCVRP。本文的贡献可以总结如下：

1) 建立了多场景带容量车辆路径问题的数学模型，其中良好天气和恶劣天气被定义为两个场景。分别为每个场景设计了成本和碳排放的多目标函数模型。

2) 构建了一种基于并行进化框架的多场景带容量车辆路径优化算法(PEF-MSOA)。设计了一种高效的知识转移策略，以选择在所有场景中具有良好优化性能的PCOS。

3) 使用三种交叉算子设计了一种基于距离的自适应选择交叉算子策略，可以显著提高PCOS的质量。此外，设计了一种存档更新过程，以动态更新和存储PCOS，在控制存档大小的同时确保PCOS的最优性。

本文的其余部分组织结构如下。在第二章中，我们简要讨论了相关概念与理论基础。第三章详细介绍了MSCVRP模型的构建。第四章详细介绍了提出的PEF-MSOA。第五章列出了PEF-MSOA的实验结果。第六章对本文所做工作进行了总结。

2. 相关概念与理论基础

在本章中，首先介绍了多场景优化问题(MSOP)的数学表达式。然后，讨论了当前MSOP的研究方法。最后，介绍了knee点的定义。

2.1. 多场景优化问题

多场景优化问题(MSOP)专注于寻找一组在不同场景下均具有优良性能的PCOS，广义上，MSOP可定义为包含I个独立场景的M目标优化问题。与传统单场景优化不同，其解需在全部I个场景中进行评估。每个场景均具有独特的参数、约束条件及对应的帕累托最优解集。MSOP的最终目标是通过考虑各场景的需求，找到在所有场景中表现良好的解。其核心挑战在于协调不同场景之间的差异，并确保选出的解在每个场景中表现良好。这需要评估解在多个场景中的表现，并基于这些评估进行选择和优化。不失一般性地，对于含有I个场景、每个场景中包含M个目标函数和Y个不等式约束的多场景优化问题，数学模型可描述如下：

$\begin{array}{l}\min :F^{\left(1\right)}\left(x\right)=\left\{f_1^{\left(1\right)}\left(x\right),\cdots f_m^{\left(1\right)}\left(x\right),\cdots f_M^{\left(1\right)}\left(x\right)\right\}\\ \cdots \\ \min :F^{\left(i\right)}\left(x\right)=\left\{f_1^{\left(i\right)}\left(x\right),\cdots f_m^{\left(i\right)}\left(x\right),\cdots f_M^{\left(i\right)}\left(x\right)\right\}\\ \cdots \\ \min :F^{\left(I\right)}\left(x\right)=\left\{f_1^{\left(I\right)}\left(x\right),\cdots f_m^{\left(I\right)}\left(x\right),\cdots f_M^{\left(I\right)}\left(x\right)\right\}\end{array}$ (1)

$s.t.g_y^{\left(i\right)}\left(x\right)\le 0,y=1,2,\cdots Y,i=1,2,\cdots I.$

$x\in \Omega$

其中，$f_m^{\left(i\right)}\left(x\right)$ 表示第i个场景的第m个目标函数，$g_y^{\left(i\right)}\le 0$ 表示第i个场景的第y个不等式约束。

2.2. 现有MSOP研究方法

目前，解决MSOP的主要方法分为两种：第一种方法是基于聚合思想的算法，常见的包括平均聚合方法[8]和最差情形聚合方法[9]。其核心思想是将各场景目标函数的平均值或最大值作为聚合函数，将MSOP转化为单一场景下优化问题，然后通过已有的多目标进化优化算法来进行求解。然而，当场景间差异较大时，该方法可能导致局部最优解，而非MSOP的全局最优解，导致求解出来的最终解质量不高。第二种方法是场景导向法，主要通过独立优化各场景的解集(定义为该场景的非支配解)，并采用预定的决策策略进行整合[10] [11]。但该方法违背了多目标优化与多准则决策问题的基本原则，且存在计算时间过长和复杂度高的问题。

2.3. Knee点

在种群中表现出良好优化性能(收敛性与多样性)的解通常被定义为knee点。在每一代的进化过程中，选择knee点进入下一代种群，相较于非knee点，能更有效地提升算法的收敛性。以双目标最小化问题为例，如图1所示，极值线H由两个目标的极值解计算得出，其中一个解在第一个目标函数$f_1$ 上取得最大值，另一个解在第二个目标函数$f_2$ 上取得最大值。对于每个解，计算其到极值线H的距离，若某解在其邻域内到H的距离最大，则被识别为knee点。本文采用KNEA [12]选出各场景的knee点。

Figure 1. An illustration for determining knee solutions in KnEA for a bi-objective optimization problem

图1. 用于确定双目标优化问题中knee点的KnEA算法示意图

3. MSCVRP建模

车辆配送条件因环境不同而有所差异。例如，由于良好天气与恶劣天气在交通拥堵和成本条件上的差异，距离权重因子和成本权重因子也会有所不同。本文将良好天气和恶劣天气定义为MSCVRP下的两个独立场景，其中良好天气为场景1，恶劣天气为场景2。每个场景包含两个目标函数：成本$f_1^{\left(I\right)}$ 和碳排放$f_2^{\left(I\right)}$ 。两个场景同时优化，构成了多场景带容量车辆路径优化问题。MSCVRP模型构建如下：

$TD={\displaystyle \sum _{k\in K}{\displaystyle \sum _{i\in V}{\displaystyle \sum _{j\in V}{W}_{Iij}{d}_{ij}{x}_{ijk}}}}$ (2)

$f_{fuel}=TD.c$ (3)

$f_{labor}={\displaystyle \sum _{k\in K}{L}_I{u}_k}$ (4)

$T_{pjk}=q_{ijk}+v_{ijk1}+v_{ijk2}$ (5)

$f_{penalty}={\displaystyle \sum _{k\in K}{\displaystyle \sum _{i\in V}{\displaystyle \sum _{j\in V}{P}_e{T}_{pjk}{x}_{ijk}}}}$ (6)

$C_{ijk}=p_0+\left(p-p_0\right)r_{ijk}$ (7)

$$ $r_{ijk}=\frac{Q_{ijk}}{Q}$ (8)

$f_{carbon}={\displaystyle \sum _{k\in K}{\displaystyle \sum _{i\in V}{\displaystyle \sum _{j\in V}{C}_{ijk}{x}_{ijk}{W}_{fij}{d}_{ij}}}}$ (9)

$f_1^{\left(I\right)}=f_{fuel}+f_{labor}+f_{penalty}$ (10)

$f_2^{\left(I\right)}=f_{carbon}$ (11)

${\displaystyle \sum _{k\in K}{\displaystyle \sum _{j\in V}{x}_{ijk}=1}},\forall i\in C$ (12)

${\displaystyle \sum _{j\in V}{v}_{0jk}={\displaystyle \sum _{i\in V}{v}_{i0k}}}=1,\forall k\in K$ (13)

$$ ${\displaystyle \sum _{i\in V}{x}_{ihk}-{\displaystyle \sum _{j\in V}{x}_{hjk}=0,\forall h\in C,k\in K}}$ (14)

${\displaystyle \sum _{i\in V,i\ne j}{x}_{ijk}-{\displaystyle \sum _{i\in V,i\ne j}{x}_{jik}=0,\forall j\in V,k\in K}}$ (15)

$x_{ijk}\in \left\{0,1\right\},\forall \left(i,j\right)\in A,k\in K$ (16)

${\displaystyle \sum _{i\in C}{\displaystyle \sum _{j\in V}{q}_i{x}_{ijk}\le Q,\forall k\in K}}$ (17)

其中，等式(2)表示车辆在第I个场景下车辆行驶总距离。等式(3)表示在第I个场景下车辆的燃油消耗成本。等式(4)表示第I个场景下配送的劳动成本。等式(5)表示路径中容量约束违反的总和。其中，$v_{ijk1}$ 表示从节点i到节点j是否违反载重约束，$v_{ijk1}$ 表示若$v_{ijk1}=1$ ，则从i到j的容量约束违反总和。等式(6)表示不同场景下容量约束违反惩罚成本。等式(7)表示第k辆车的单位距离碳排放量。等式(8)表示车辆载重的变化率系数。等式(9)表示两个场景中的总碳排放量，准确反映了碳排放与载重和行驶距离的正比关系。等式(10)表示第I个场景下的第一个目标函数总成本。等式(11)表示第I个场景下的第二个目标函数总碳排放量。等式(12)~等式(17)为车辆路径问题的标准约束，本文不再赘述。

通过上述对目标函数与约束模型的构建，准确描述了在良好天气与恶劣天气下的基于成本与碳排放目标函数的多场景带容量车辆路径问题。

4. 基于并行进化框架的多场景带容量车辆路径优化算法

图2为PEF-MSOA算法的总体流程框架图，由于本文建立的MSCVRP中每个场景包含两个优化目标函数，故以下描述基于求解包含I个场景，每个场景中包含两个目标函数的最小化多场景优化问题。在初始化阶段，对于每个情景$S_i$ ，$i\in \left\{1,2,\cdots I\right\}$ ，随机生成并评估一个包含N个解的种群$P_i$ ，并评估种群$P_i$ 中的每一个解在当前场景中的目标函数值。将$P_i$ 分成三个子种群$P_{i-j}$ ，$j\in \left\{1,2,3\right\}$ ，每个子种群使用不同的交叉算子。在进化迭代过程的每一轮迭代中，首先，使用KnEA算法找到子种群$P_{i-j}$ 的knee点$K_{i-j}$ 与约束极值线$H_{i-j}$ ，每个场景的knee点与极值线由各子种群合并构成。其次，在基于knee点的跨场景知识迁移策略步骤中，评估每个场景的knee点是否可以被其他情景作为可接受解。迁移策略的评估基于每个情景中构造的约束极值线，如果来自其他情景的knee点位于约束极值线以下，则该knee点被认为是相应情景的可接受解$T_i$ 。被所有情景接受的knee点定义为公共折中最优解(PCOS)。随后，在基于距离的自适应选择交叉算子策略步骤中，在每一轮的迭代中动态更新算子优化种群比例矩阵$M_i$ ，以确定下一代进化过程中分配给每个算子的子种群数量。同时，使用环境选择动态更新档案Ar中的PCOS，以确保它们的最优性，同时控制存档数量为N。最后，对于每个情景，其可接受解$T_i$ 参与其种群$P_i$ 的后代生成过程，以促进不同情景之间的有效信息传递，帮助其他场景快速找到决策空间中最优区域，加速求解过程。当达到迭代终止条件时，此时档案中的解即为最终的公共折中最优解。图2为PEF-MSOA算法的总体流程框架图，详细的算法策略步骤流程描述如后文所述。

Figure 2. The flowchart of multi-scenario optimization algorithm based on parallel evolution framework

图2. 基于并行进化框架的多场景优化算法流程图

4.1. 基于Knee点的跨场景知识迁移策略

PCOS应在所有场景中表现出良好的收敛性与多样性，并整合来自各场景的有价值信息。因此，设计了一种基于knee点的跨场景迁移策略。首先，对于场景​$S_i$ ，其约束极值线$H_i$ 可被定义为$a_{i}x+b_{i}y+c_i=0$ ，用于判断其他场景的knee点是否可以作为该场景的可接受解。参数a、b、c的值由每个场景中knee点中的极值解确定。以双目标最小化问题为例，一个极值解在目标一$f_1^{\left(I\right)}$ 上取得最大值，另一个极值解在目标二$f_2^{\left(I\right)}$ 上取得最大值。设解$A\left(x_A,y_A\right)$ 为某一个场景的knee点集合中的一个knee点，其到$H_i$ 的距离可通过公式(18)和(19)进行计算。若$d\left(A,H_i\right)>0$ ，表示解A位于$H_i$ 的下方，则A被定义为场景$S_i$ ​的可接受解$T_i$ ；否则，解不能被定义为场景$S_i$ 的可接受解。基于knee点的跨场景迁移策略实现了knee点的跨场景迁移与每个场景可接受解的识别。被所有场景接受的knee点被定义为PCOS。图3展示了两场景间的迁移策略示意图。尽管迁移策略能够得到所有的PCOS，但其最优性仍需提升，需设计措施以进一步提高PCOS的质量。

$d\left(A,H_i\right)=\frac{\left|a_i{x}_A+b_i{y}_A+c_i\right|}{\sqrt{a_i{}^2+b_i{}^2}},a_i{x}_A+b_i{y}_A+c_i<0$ (18)

$d\left(A,H_i\right)=-\frac{\left|a_i{x}_A+b_i{y}_A+c_i\right|}{\sqrt{a_i{}^2+b_i{}^2}},a_i{x}_A+b_i{y}_A+c_i\ge 0$ (19)

Figure 3. Schematic of the transfer strategy of knee points between two scenarios

图3. 两场景间knee点的迁移策略示意图

4.2. 基于距离的自适应选择交叉算子策略

为了提高PCOS的质量，设计了一种基于距离的自适应算子选择策略。对于场景​$S_i$ ，$i\in \left\{1,2,\cdots I\right\}$ ，其种群$P_i$ 被划分为三个子种群$P_{i-j}$ ，$j\in \left\{1,2,3\right\}$ 。初始化不同交叉算子优化子种群数量矩阵$M_i$ ，$M_i$ 决定每种交叉算子优化子种群数量。在这些子种群的进化过程中，顺序交叉算子(OX)、基于距离的交叉算子(CM1)和基于断裂的交叉算子(CM2)被应用于进化这些子种群，$P_{i-1}$ 使用OX作为交叉算子​，$P_{i-2}$ 使用CM1作为交叉算子，$P_{i-3}$ 使用CM2作为交叉算子。

OX从一个父代中选择一个基因片段，保留其顺序，并用另一个父代的基因按相对顺序填充剩余位置[13]。CM1在生成子代时考虑了父代解的距离信息和容量约束。它结合最优路径段以保留较短路径的特征，从而生成更好的子代解，其流程图如图4所示。CM2是用于解决车辆路径问题的交叉算子，它随机选择两条路径，并在随机断点处将每条路径拆分为头部(从配送中心开始)和尾部(返回配送中心)，其示意图如图5所示。基于knee点的跨场景迁移策略也应用于不同场景中具有相同索引的子种群之间，例如$P_{i-1}$ 和$P_{j-1}$ ，$i\ne j$ 。$S_i$ 的第j个子种群获得的可接受解和knee点分别定义为$T_{i-j}$ 和$K_{i-j}$ 。$T_{i-j}$ 和$K_{i-j}$ 到$H_i$ 的距离之和定义为$D_{i-j}$ ，用于更新交叉算子优化子种群数量矩阵$M_i$ ​。根据之前对knee点和约束极值线的定义，解离极值线越远，其收敛性越好。因此，$D_{i-j}$ 越大，相应算子的优化效果越好。$D_{i-j}$ 也可以通过公式(18)和(19)进行计算。自适应算子选择策略决定了下一代进化过程中分配给每个算子的子种群数量，引导搜索方向以提高PCOS的质量。每个场景的可接受解$T_i$ 定义为来自相应子种群的$T_{i-j}$ 集合，定义如下：

$T_i=\left[T_{i-1},T_{i-2},T_{i-3}\right]$ (20)

场景$S_i$ 的$D_{i-j}$ 之和定义如下：

$W_i=D_{i-1}+D_{i-2}+D_{i-3}$ (21)

交叉算子优化子种群数量矩阵$M_i$ 的定义如下：

$M_i=\left[\frac{D_{i-1}}{W_i}\frac{D_{i-2}}{W_i}\frac{D_{i-3}}{W_i}\right]$ (22)

Figure 4. The flowchart of CM1 operator

图4. CM1交叉算子流程图

Figure 5. The flowchart of CM5 operator

图5. CM2交叉算子流程图

5. 实验部分

在本节中，通过实验分别验证了PEF-MSOA中基于knee点的跨场景迁移策略和自适应选择交叉算子策略的有效性。使用HV [14]和Spacing [15]指标评估所获得解集的质量，并分析其在两个场景目标空间中的表现。

5.1. 测试问题

为了验证基于knee点的跨场景迁移策略的性能，设计了两种对比算法。使用场景间knee点进行迁移且仅采用OX作为交叉算子的算法定义为PEF-MSOA1，其得到的PCOS命名为PCOS1。在场景间迁移所有解的算法定义为PEF-MSOA2，其得到的PCOS命名为PCOS2。在场景间无解迁移的算法称为PEF-MSOA3，其得到的PCOS命名为PCOS3。所有算法均使用MSCVRP作为测试问题，本实验使用上海真实物流数据，所有场景均只有1个配送中心，其位置坐标为(40, 50)。在本文中，MSCVRP设置为两场景。在场景1中，客户数量为100，车辆数为24，车辆载重为100；场景2中，客户数量为59，车辆数为15，车辆载重为80；违反载货量约束惩罚系数均设为10。

5.2. 实验参数设置

种群规模N和存档Ar的大小均设置为100，交叉概率Pc = 0.9，变异概率Pm = 1/D，其中D为决策空间的维度。最大迭代次数设置为5000，对应50代。在KNEA算法中，帕累托前沿Fi中knee点的比例阈值T = 0.5，邻域宽度r以及帕累托前沿Fi中knee点的比例t随进化过程实时更新。实验在PLATEMO [16]平台上进行。

Figure 6. Optimized solutions of PEF-MSOA1 in objective space

图6. PEF-MSOA1在两场景目标空间中的优化解图

Figure 7. Optimized solutions for different transfer strategy in objective space

图7. 不同迁移策略在两场景目标空间中的优化解图

MSCVRP涉及两个场景。由于计算HV值时需要设置参考点，且不同场景的参考点不同，因此需要分别为每个场景设置参考点并计算HV值。最终，取两个场景HV值的平均值作为最终结果。对于Spacing指标，无需设置参考点，因此无需分别在两个场景中运行。每个算法在MSCVRP上独立运行20次。

Table 1. Comparison results of HV and Spacing value with three approaches under MSCVRP in two scenarios

表1. 两种场景下三种算法的HV与Spacing值对比结果

Figure 8. Optimized solutions for different operators in objective space

图8. 不同交叉算子在两场景目标空间中的优化解图

5.3. 实验结果分析

图6展示了PEF-MSOA1在两场景目标空间中的优化解，其中SC1和SC2分别表示场景S1和S2的解集，PCOS1在两个场景中的收敛性和多样性均优于SC1和SC2。表1中展示了三种算法获得的PCOS的HV和Spacing值，图7展示了不同迁移策略在两场景中获得的PCOS的目标空间图。从上述结果可以得出结论，PEF-MSOA1获得的PCOS质量最佳，而PEF-MSOA3获得的PCOS质量最差。这表明场景间的信息交换可以提高PCOS的质量，特别是使用knee点进行跨场景迁移时效果最好，验证了本文中所提出的基于knee点的跨场景迁移策略的有效性。

为验证本文中所提出自适应选择交叉算子策略的有效性，分别使用OX、CM1和CM2作为交叉算子进行实验，并对比其组合使用效果。图8展示了使用不同交叉算子获得的PCOS在两场景中的目标空间图。由图可知，CM1在目标$f_1^{\left(I\right)}$ 上表现更优，而CM2在目标$f_2^{\left(I\right)}$ 上表现更优，且两者均优于OX算子。其中使用基于距离的自适应选择交叉算子策略获得的PCOS几乎严格支配了使用单一交叉算子获得的PCOS，表明该策略能显著提升了PCOS的质量。

6. 总结

本文构建了一个多场景带容量车辆路径问题，即MSCVRP。为了有效解决MSCVRP，提出了一种基于并行进化框架的多场景带容量车辆路径优化算法。在PEF-MSOA的每一次迭代中，首先利用KnEA算法选出每个场景中具有良好收敛性和多样性的knee点。其次，设计了基于knee点的跨场景迁移策略，评估每个场景的knee点是否可以被其他场景定义为可接受解。被所有场景接受的knee点被定义为公共折中最优解(PCOS)。然后，为了提高PCOS的质量，设计了一种基于距离的自适应选择交叉算子策略，用于更新交叉算子优化子种群数量矩阵，以此确定下一代进化过程中分配给每个算子的子种群数量。同时，对于每个场景，将其可行解与子代种群结合，促进不同场景之间的有效信息传递。最后，使用环境选择确保PCOS的最优性并控制其规模。通过实验验证了本文所提出算法的优越性和新颖性，能够有效地解决MSCVRP。

参考文献