求解PDPTW问题的快速LNS算法

来源期刊：控制工程2007年第5期

论文作者：石磊 谷寒雨 席裕庚

文章页码：558 - 561

关键词：带时间窗装卸货问题;NP-hard问题;大规模领域搜索;邻域搜索;

摘    要：提出了一种解决有时间窗口的装卸货问题(PDPTW)的快速大规模领域搜索(LNS)算法。该算法基于大规模邻域搜索理论和随机扰动思想,在第一阶段主要以减少车辆为目标,第二阶段对第一阶段得到的解优化总路程长度。该算法能在较短时间内显著提高初始解的质量,克服了单纯以车辆数目或以总路程长度为目标的算法所得到解的局限性。通过标准算例的测试和同禁忌搜索的比较表明,该算法在求解PDPTW问题时,在计算时间和优化整体目标上更具优势。