李想等：两级选址一路径问题的大规模邻域搜索模拟退火算法 ·959· T。=10000,终止温度：T=0.1,降温系数：a=0.96,内 前已知国际最优解和标准模拟退火算法进行对比.本 循环次数：M.=1500,最大不更新代数：Np=300. 文算法在中小规模(25~50个需求点)算例中求解效 大规模邻域搜索部分所含参数包括：相邻点移除概率： 果十分优秀，均能够找到与已知国际最优解相同的解， R。=0.14、最大节约点移除概率：R。=0.50、随机路径 在大规模(100个需求点)算例中，本文算法求解效果 移除概率：R=0.28、单点路径移除概率：R=0.37、 较好.具体求解结果如表1所示. 关闭、开放中转站概率：R。=0.21、不允许更改中转站 上述实验结果表明，在中小规模算例中，大规模邻 状态代数：g=50. 域搜索模拟退火算法能够找到最优解，在大规模算例 3.3实验结果对比分析 中，相对于标准模拟退火算法，SA-LNS求解质量较 将本文的大规模邻域搜索模拟退火算法分别与目 高，总体表现求解效果优秀 表1 Nguyen算例集求解结果 Table 1 Results for Nguyen 2E-LRP instances set 算例 BKS· SA SA-LNS 算例 BKS* SA SA-LNS 25-5-N 80.370 80.370 80,370 50-10-MN 135,519 137,562 135,519 25-5-Nb 64,562 64,562 64.562 50-10-MNh 110,613 110.763 110.613 25-5-MN 78.947 78.947 78.947 100-5-N 193.228 201.866 193,229 25-5-MNb 64,438 64,438 64,438 100-5-Nh 158.927 160,217 159.989 50-5-N 137,815 141,563 137,815 100-5-MN 204.682 211,470 205,862 50-5-Nb 110.094 112,409 110,094 100-5-MNh 165,744 174,740 166,173 50-5-MN 123.484 125,554 123.484 100-10-N 209,952 216.620 210.799 50-5-MNb 105,401 106,313 105.401 100-10-Nb 155,451 157.682 156,401 50-10-N 115,725 119,797 115,725 100-10-MN 201,275 207.795 202.084 50-10-Nb 87,315 88.903 87,315 100-10-MNh 170.625 172,276 170.625 注：◆表示目前国际已知最优解 在小规模问题中(25个需求点)，SA-LNS与SA 图4为SA和SA-LNS算法分别求解算例50-5- 均能够找到最优解：在中等规模问题中(50个需求 MN的迭代曲线对比图.从图中可以看出LNS-SA在 点)，SA不能够找到最优解，但是SA-LNS均能够找到 收敛速度上远优于SA,图中第一代的求解结果显示， 最优解：在大规模问题中(100个需求点)，SA-LNS与 LNS-SA经过一次迭代的优化效果要明显优于SA,并 SA均没能找到最优解，但是SA求解效果较差，SA- 且LNS-SA在第34代完成收敛，而SA在第83代完成 LNS优化效果明显. 收敛.此外LNS-SA在收敛效果也要优于SA,LNS-SA 将大规模邻域搜索嵌入到模拟退火算法中，构造 能够最终收敛到算例国际已知最优解，而A并不能 邻域解时在更大的解空间内进行搜索，从而进一步提 .91 高了算法求解效果，能够在较大规模问题中找到比较 —SA 好的解方案.大规模邻域搜索中的破坏过程包含6种 ---SA-LNS 破坏方法，其中前4种破坏方法是对路径进行优化，后 1.7 2种破坏方法是对设施节点选址进行优化.该方法能 1.6 够将选址与路径问题统一考虑，从而相对于标准模拟 退火算法，能够在选址-路径问题中取得更好的求解 1.5 在求解大规模问题中，标准模拟退火算法不能够很好 14f 地兼顾选址和路径问题，往往导致选择了较差的中转 站节点，这也是在中大规模问题中标准模拟退火算法 求解效果不佳的原因之一 20 50100150200250300350400 由于一级配送网络所含中转站节点总数较少，标 迭代次数 准算例集Nguyen最多只包含有10个中转站，因此采 图4SA与SA-LNS求解算例50-5-MN收敛曲线对比 用大规模邻域搜索能够有效的找到一级配送网络最优 Fig.4 Comparison of SA and SA-LNS convergence trend graphs for 解或者近似最优解 50-5-MN instance李 想等: 两级选址鄄鄄路径问题的大规模邻域搜索模拟退火算法 T0 = 10000,终止温度:Tf = 0郾 1,降温系数:琢 = 0郾 96,内 循环次数:Mit = 1500,最大不更新代数:Nnotimp = 300. 大规模邻域搜索部分所含参数包括:相邻点移除概率: Rp1 = 0郾 14、最大节约点移除概率:Rp2 = 0郾 50、随机路径 移除概率:Rp3 = 0郾 28、单点路径移除概率:Rp4 = 0郾 37、 关闭、开放中转站概率:Rp5 = 0郾 21、不允许更改中转站 状态代数:gmax = 50. 3郾 3 实验结果对比分析 将本文的大规模邻域搜索模拟退火算法分别与目 前已知国际最优解和标准模拟退火算法进行对比. 本 文算法在中小规模(25 ~ 50 个需求点)算例中求解效 果十分优秀,均能够找到与已知国际最优解相同的解, 在大规模(100 个需求点)算例中,本文算法求解效果 较好. 具体求解结果如表 1 所示. 上述实验结果表明,在中小规模算例中,大规模邻 域搜索模拟退火算法能够找到最优解,在大规模算例 中,相对于标准模拟退火算法,SA鄄鄄 LNS 求解质量较 高,总体表现求解效果优秀. 表 1 Nguyen 算例集求解结果 Table 1 Results for Nguyen 2E鄄鄄LRP instances set 算例 BKS * SA SA鄄鄄LNS 算例 BKS * SA SA鄄鄄LNS 25鄄鄄5鄄鄄N 80,370 80,370 80,370 50鄄鄄10鄄鄄MN 135,519 137,562 135,519 25鄄鄄5鄄鄄Nb 64,562 64,562 64,562 50鄄鄄10鄄鄄MNb 110,613 110,763 110,613 25鄄鄄5鄄鄄MN 78,947 78,947 78,947 100鄄鄄5鄄鄄N 193,228 201,866 193,229 25鄄鄄5鄄鄄MNb 64,438 64,438 64,438 100鄄鄄5鄄鄄Nb 158,927 160,217 159,989 50鄄鄄5鄄鄄N 137,815 141,563 137,815 100鄄鄄5鄄鄄MN 204,682 211,470 205,862 50鄄鄄5鄄鄄Nb 110,094 112,409 110,094 100鄄鄄5鄄鄄MNb 165,744 174,740 166,173 50鄄鄄5鄄鄄MN 123,484 125,554 123,484 100鄄鄄10鄄鄄N 209,952 216,620 210,799 50鄄鄄5鄄鄄MNb 105,401 106,313 105,401 100鄄鄄10鄄鄄Nb 155,451 157,682 156,401 50鄄鄄10鄄鄄N 115,725 119,797 115,725 100鄄鄄10鄄鄄MN 201,275 207,795 202,084 50鄄鄄10鄄鄄Nb 87,315 88,903 87,315 100鄄鄄10鄄鄄MNb 170,625 172,276 170,625 注:*表示目前国际已知最优解 在小规模问题中(25 个需求点),SA鄄鄄 LNS 与 SA 均能够找到最优解;在中等规模问题中(50 个需求 点),SA 不能够找到最优解,但是 SA鄄鄄LNS 均能够找到 最优解;在大规模问题中(100 个需求点),SA鄄鄄 LNS 与 SA 均没能找到最优解,但是 SA 求解效果较差,SA鄄鄄 LNS 优化效果明显. 将大规模邻域搜索嵌入到模拟退火算法中,构造 邻域解时在更大的解空间内进行搜索,从而进一步提 高了算法求解效果,能够在较大规模问题中找到比较 好的解方案. 大规模邻域搜索中的破坏过程包含 6 种 破坏方法,其中前 4 种破坏方法是对路径进行优化,后 2 种破坏方法是对设施节点选址进行优化. 该方法能 够将选址与路径问题统一考虑,从而相对于标准模拟 退火算法,能够在选址鄄鄄路径问题中取得更好的求解. 在求解大规模问题中,标准模拟退火算法不能够很好 地兼顾选址和路径问题,往往导致选择了较差的中转 站节点,这也是在中大规模问题中标准模拟退火算法 求解效果不佳的原因之一. 由于一级配送网络所含中转站节点总数较少,标 准算例集 Nguyen 最多只包含有 10 个中转站,因此采 用大规模邻域搜索能够有效的找到一级配送网络最优 解或者近似最优解. 图 4 为 SA 和 SA鄄鄄 LNS 算法分别求解算例 50鄄鄄5鄄鄄 图 4 SA 与 SA鄄鄄LNS 求解算例 50鄄鄄5鄄鄄MN 收敛曲线对比 Fig. 4 Comparison of SA and SA鄄鄄LNS convergence trend graphs for 50鄄鄄5鄄鄄MN instance MN 的迭代曲线对比图. 从图中可以看出 LNS鄄鄄 SA 在 收敛速度上远优于 SA,图中第一代的求解结果显示, LNS鄄鄄 SA 经过一次迭代的优化效果要明显优于 SA,并 且 LNS鄄鄄 SA 在第 34 代完成收敛,而 SA 在第 83 代完成 收敛. 此外 LNS鄄鄄SA 在收敛效果也要优于 SA,LNS鄄鄄SA 能够最终收敛到算例国际已知最优解,而 SA 并不能 ·959·