2022年SEVC SCI2区，用于实用型动态取送货问题的变邻域搜索方法，深度解析+性能实测-编程实验室

1.摘要

针对制造业中工厂间大量货物动态运输的实际需求，本文提出了一种更贴近真实场景的动态取送货问题（DPDP）模型，综合考虑了码头、时间窗、容量限制以及后进先出装载等复杂约束，传统优化算法难以直接求解。为此，本文提出了一种新的多策略变邻域搜索算法（VNSME），该算法在新订单到达时启动新的优化周期，并以上一周期的最优解为基础，通过穷举与最便宜插入启发式构造初始解，结合四种局部搜索策略和高效扰动机制进行优化。

2.数学模型

本文研究了一种考虑码头约束的动态取送货问题（DPDP），在实际物流场景中，每个工厂拥有有限数量的装卸码头，当码头被占满时，后到车辆必须按到达顺序排队等待，从而可能引发订单延误。该问题同时受到时间窗、车辆容量、LIFO装载规则以及码头资源限制等多重约束。优化目标是在调度所有订单的同时，最小化订单总拖期：
f 1 = ∑ i = 1 N max ⁡ ( 0 , a i d − t i l ) f_1=\sum_{i=1}^N\max\left(0,a_i^d-t_i^l\right)f1=i=1∑Nmax(0,aid−til)

最小化车辆平均行驶距离：
f 2 = 1 K ∑ k = 1 K ∑ i = 1 l k − 1 D n i k , n i + 1 k f_2=\frac{1}{K}\sum_{k=1}^K\sum_{i=1}^{l_k-1}D_{n_i^k,n_{i+1}^k}f2=K1k=1∑Ki=1∑lk−1Dnik,ni+1k

综合优化目标:
min ⁡ f = λ f 1 + f 2 \min f=\lambda f_1+f_2minf=λf1+f2

3.VNSME算法

VNSME 采用滚动时域思想：当新订单在当前阶段动态产生时，算法首先从档案中恢复上一阶段的最优解，生成当前阶段的初始可行解；随后通过多种改进的局部搜索策略对解进行强化；再利用扰动操作跳出局部最优，并结合局部搜索不断迭代更新，最终将当前阶段的最优解存入档案，供下一阶段使用。

初始化阶段

在初始化阶段，算法不进行完全重优化，而是采用一种高效的混合机制（穷举 + 最便宜插入 CI）。对于路径节点数较少的车辆，穷举所有可行插入方式，选择使综合目标函数最小的方案；对于路径较长的车辆，采用最便宜插入启发式快速插入新订单；在所有车辆中选择目标函数值最小的方案更新解。

局部搜索

为提升算法在大量同源订单场景下的搜索效率，本文引入了取送节点组（PDG）与块取送节点组（BPDG）两个核心概念，并在此基础上设计了四种改进的局部搜索算子，构成 VNSME 的核心搜索机制。

PDG（Pickup and Delivery Nodes Group）：若若干相邻订单具有相同的取货地址和送货地址，则其取货节点构成取货节点组（PG），送货节点构成送货节点组（DG），二者共同组成一个 PDG。若不存在相同地址订单，则 PDG 退化为单一取送节点对。

BPDG（Block PDG）：在一条可行路径中，从 PG 到 DG 的整段路径定义为一个 BPDG，即以 PDG 为核心的连续节点块。

四种改进局部搜索策略：

Couple-Exchange*: 以 PDG 为单位，交换两个 PDG 中的取货节点组与送货节点组
位置，可跨车辆操作，时间复杂度O ( n 2 ) O(n^2)O(n2)。
Block-Exchange*:以 BPDG 为单位，交换两个不相交的 BPDG 块，操作范围更
大，时间复杂度O ( n 2 ) O(n^2)O(n2)。
Block-Relocate*:将一个 BPDG 从原路径移除并插入到任意可行位置 (同车或异
车),时间复杂度O ( n 2 ) O(n^2)O(n2)。
Multi-Relocate*:在 block-relocate* 基础上，缓存多个可改进解的 PDG,依次执
行多次重定位，以进一步提升解质量，时间复杂度O ( n 3 ) O(n^3)O(n3)。

扰动算子

本文提出了一种 2-opt-L* 扰动算子，该算子是在2-opt-L改进版本，具有更强的破坏性与跳出能力。扰动生成的新解仅在其综合目标函数值满足时被接受：
f n e w < δ ⋅ f ( x l s ) f_{\mathrm{new}}<\delta\cdot f(x_{ls})fnew<δ⋅f(xls)

其中，x l s x_{ls}xls为当前局部搜索得到的最优解，δ \deltaδ为扰动强度参数。

4.参考文献

[1] Cai J, Zhu Q, Lin Q. Variable neighborhood search for a new practical dynamic pickup and delivery problem[J]. Swarm and Evolutionary Computation, 2022, 75: 101182.