Combining a Parallel Branch-and-Bound Algorithm with a Strong Heuristic to Solve the Sequential Ordering Problem
Combining a Parallel Branch-and-Bound Algorithm with a Strong Heuristic to Solve the Sequential Ordering Problem
复制标题
将并行分支定界算法与强启发式相结合来解决顺序排序问题
DOI：
10.1145/3605731.3608929
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Muyan-Ozcelik, Pinar
中科院分区：
文献类型：
--
作者：
Shobaki, Ghassan;Gonggiatgul, Taspon;Normington, Jacob;Muyan-Ozcelik, Pinar
本文描述了如何将并行分支定界（B&B）算法与强启发式算法相结合来解决NP-hard优化问题——顺序排序问题（SOP）。并行B&B算法与lin - kernighan - helsgan启发式算法并行运行，后者被认为是求解SOP的最强启发式算法之一。每个算法找到的最佳解与其他算法共享，每个算法都从另一个算法找到的更好解中获益。有了B&B找到的更好的解决方案，LKH可以找到更好的解决方案。有了LKH找到的更好的解，B&B将有一个更紧的上界，使它能够在较浅的树节点上进行修剪，从而更快地完成搜索。该组合算法在SOPLIB和TSPLIB基准上进行了实验评估。结果表明，该组合算法的性能明显优于单独的B&B算法或LKH启发式算法。两个基准套件在速度和解决方案质量方面都有了显著的改进。例如，在中等难度的SOPLIB实例上，该算法相对于LKH提供了10.17的几何平均加速。在硬SOPLIB实例上，相对于B&B，它可将成本提高22%，相对于LKH，可将成本提高90%
In this paper, we describe how to combine a parallel branch-and-bound (B&B) algorithm and a strong heuristic to solve the Sequential Ordering Problem (SOP), which is an NP-hard optimization problem. A parallel B&B algorithm is run in parallel with the Lin-Kernighan-Helsgaun heuristic algorithm, which is known to be one of the strongest heuristic algorithms for solving the SOP. The best solutions found by each algorithm are shared with the other algorithm, and each algorithm benefits from the better solutions found by the other. With the better solutions found by B&B, LKH can find even better solutions. With the better solutions found by LKH, B&B will have a tighter upper bound that enables it to prune at shallower tree nodes and thus complete it search faster. The combined algorithm is evaluated experimentally on the SOPLIB and TSPLIB benchmarks. The results show that the combined algorithm gives significantly better performance than any of the B&B algorithm or the LKH heuristic individually. Significant improvements in both speed and solution quality are seen on both benchmark suites. For example, the proposed algorithm delivers a geometric-mean speedup of 10.17 relative to LKH on the medium-difficulty SOPLIB instances. On the hard SOPLIB instances, it improves the cost by up to 22% relative to B&B and up to 90% relative to LKH
登录
查看更多内容
影响因子：
4.8
作者：
L. Escudero;M. Guignard;K. Malik
通讯作者：
L. Escudero;M. Guignard;K. Malik
影响因子：
1.6
作者：
A. Bruin;G. Kindervater;Harry W. J. M. Trienekens
通讯作者：
Harry W. J. M. Trienekens
DOI：
10.1287/opre.42.6.1042
发表时间：
1994-12
期刊：
Oper. Res.
影响因子：
--
作者：
B. Gendron;T. Crainic
通讯作者：
B. Gendron;T. Crainic
DOI：
--
发表时间：
2017-12
期刊：
--
影响因子：
--
作者：
Jan Gmys
通讯作者：
Jan Gmys
解决顺序排序问题的增强型蚁群系统
DOI：
--
发表时间：
2011
期刊：
OR
影响因子：
--
作者：
L. Gambardella;R. Montemanni;D. Weyland
通讯作者：
D. Weyland