求解大规模旅行推销员问题的分层销毁和修复方法
原文中文,约500字,阅读约需2分钟。发表于: 。对于庞大规模的旅行推销员问题(TSP),现有算法在计算效率和解决方案质量方面面临巨大挑战。为了解决这个问题,我们提出了一种分层销毁和修复(HDR)方法,通过一系列精心设计的销毁和修复操作来改进初始解。一个关键创新概念是分层搜索框架,它递归地修复部分边缘,并将输入实例压缩成小规模的 TSP,在某种等价保证下。这个巧妙的搜索框架能够在合理的时间内提供极具竞争力的解决方案。基于 19...
本文介绍了一种名为分层销毁和修复(HDR)的方法,用于解决旅行推销员问题(TSP)。该方法通过销毁和修复操作改进初始解,并采用分层搜索框架压缩输入实例。通过对19个大规模实例的比较,结果显示HDR在计算效率和解决方案质量方面与现有最先进的TSP算法竞争力强。在两个大型实例中,HDR打破了LKH及其变体的世界纪录,并且HDR与LKH完全独立。消融研究证明了分层搜索框架的重要性和有效性。