 |
Breakout local search for the traveling salesman problem with job-times
1 : LERIA
Université d’Angers
2 : HUST
我们提出了一种有效的启发式算法来解决 具有工作时间的旅行商问题，该算法是 许多应用程序的相关模型。
我们的算法基于一般的突破局部搜索方法。 我们用于 TSPJ 的 BLS 算法采用专用的禁忌搜索 \cite{glover1998tabu} 程序，探索两个互补的邻域，并通过邻域缩减技术进行强化。当判断搜索停滞时，以给定的扰动长度触发扰动阶段；BLS 混合了两种类型的扰动：知情扰动（由与移动频率相关的历史搜索信息引导）和随机扰动，它们以相等的概率运行。
BLS 在 310 个实例中发现了 291 个破纪录的结果（新的上限），同时与其他 16 个实例的最知名结果相匹配。
