当前位置：首页 > news >正文

2025年IEEE TITS，基于片段式知识迁移的多任务容量受限车辆路径问题，深度解析+性能实测

news 2026/8/4 23:44:54

1.摘要

本文提出了一种基于片段知识迁移的遗传算法（FKT-GA），旨在解决多任务容量受限车辆路径问题（CVRP）。研究指出目标任务中不同区域的客户分布可能与多个相关源任务存在相似性，因此 FKT-GA 摒弃了传统的单任务迁移模式，转而提取并融合来自多个源任务的优良路径片段。算法通过对旋转、平移和缩放具有不变性的分布特征来识别相关任务，并将源任务解映射至目标空间进行片段采样，进而构建高质量的初始解。配合针对性开发的变异与交叉算子以维持种群多样性，实验证明该方法在解的最优性上显著优于现有主流算法，有效提升了多任务环境下的物流路径规划效率。

2.多任务容量受限车辆路径问题

CVRP 目标是在满足车辆容量限制的前提下，规划最优路径以最小化总运输成本：

x ∗ = arg ⁡ min ⁡ f ( x ) = ∑ i = 1 n v dis ⁡ ( r i ) x^*=\arg\min f(x)=\sum_{i=1}^{n_v}\operatorname{dis}(r_i)x∗=argminf(x)=i=1∑nvdis(ri)

当存在多个具有相关性的CVRP 实例时，构成多任务优化问题：

{ x 1 ∗ , … , x K ∗ } = { arg ⁡ min ⁡ f 1 ( x ) , … , arg ⁡ min ⁡ f K ( x ) } \{x_1^*,\ldots,x_K^*\}=\{\arg\min f_1(x),\ldots,\arg\min f_K(x)\}{x1∗,…,xK∗}={argminf1(x),…,argminfK(x)}
其中，K KK为任务总数。模型假设不同区域的任务之间存在相似的客户分布或可迁移的模式，算法通过利用这些相关性来同时提升所有任务的求解效率。

3.提出的算法

流程图展示算法通过融合跨任务的搜索经验，利用分布特征匹配来实现精准的路径片段迁移，从而协同优化多个CVRP 任务。

基于多样性的初始化

初始化通过随机节约算法(RCW)平衡种群的搜索宽度与收敛速度，RCW并非像传统CW算法贪婪地合并具有最大节约值s i j = d 0 i + d 0 j − d i j s_{ij}=d_{0i}+d_{0j}-d_{ij}sij=d0i+d0j−dij的路径，而是根据节约值的大小利用p i j = s i j / ∑ s p_{ij}=s_{ij}/\sum spij=sij/∑s

计算各合并方案的概率，并采用轮盘赌选择法来引入随机性。

多源任务选择

多源任务选择通过几何变换对齐不同任务的客户分布，挖掘旋转、平移及缩放不变的本质特征。

算法首先利用主成分分析确定各任务分布的主轴，并计算目标任务T k T_kTk与源任务T i T_iTi间的夹角θ \thetaθ，以此构建旋转矩阵M MM：
M = [ cos ⁡ θ − sin ⁡ θ sin ⁡ θ cos ⁡ θ ] M = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}M=[cosθsinθ−sinθcosθ]
通过配送中心坐标差值定义平移向量v = c 0 k − c 0 i v = c_0^k - c_0^iv=c0k−c0i，并根据客户到配送中心的平均距离之比计算缩放因子α \alphaα，源任务中的客户坐标c j i c_j^icji被投影至目标空间：
c j a = α M c j i + v c_j^a = \alpha M c_j^i + vcja=αMcji+v
在空间对齐后，利用 Wasserstein 距离衡量变量变换后分布的相似度。算法最终选取距离最小的n s n_sns个任务作为知识迁移的来源。

新解生成

片段式知识迁移 (FKT)以概率p r prpr执行迁移，首先从n s n_sns个已对齐空间的源任务中各选一个随机解，评估解中各路径与目标任务客户分布的相似度。相似度由路径内客户c i s c_i^scis与其在目标任务中最近邻客户c i t c_i^tcit的平均距离d dd衡量：

d = ∑ i = 1 m ∣ ∣ c i s − c i t ∣ ∣ m d=\frac{\sum_{i=1}^m||c_i^s-c_i^t||}md=m∑i=1m∣∣cis−cit∣∣

基于距离倒数计算路径选择概率p i = ( 1 / d i ) / ∑ ( 1 / d j ) p_i=(1/d_i)/\sum(1/d_j)pi=(1/di)/∑(1/dj)，优先提取相似度高的路径。

4.结果展示

5.参考文献

Liu X F, Dai Y T, Fang Y, et al. Fragment-based knowledge transfer for multi-task capacitated vehicle routing[J]. IEEE Transactions on Intelligent Transportation Systems, 2025.