求解PDPTW问题的快速LNS算法  

Quick LNS Algorithm for Solving PDPTW Problem

作　　者：石磊[1] 谷寒雨[1] 席裕庚[1] 

机构地区：[1]上海交通大学自动化研究所,上海200240

出　　处：《控制工程》2007年第5期558-561,共4页Control Engineering of China

基　　金：国家自然科学基金资助项目(60474002);上海市科技发展基金资助项目(04DZ11008)

摘　　要：提出了一种解决有时间窗口的装卸货问题(PDPTW)的快速大规模领域搜索(LNS)算法。该算法基于大规模邻域搜索理论和随机扰动思想,在第一阶段主要以减少车辆为目标,第二阶段对第一阶段得到的解优化总路程长度。该算法能在较短时间内显著提高初始解的质量,克服了单纯以车辆数目或以总路程长度为目标的算法所得到解的局限性。通过标准算例的测试和同禁忌搜索的比较表明,该算法在求解PDPTW问题时,在计算时间和优化整体目标上更具优势。A quick large neighborhood search （LNS） algorithnl is proposed to solve the PDPTW problem, based on LNS and random disturbance. In the first stage, the number of vehicles is reduced. And in the second stage, the whole distance of all vehicles is reduced. This algorithm can get a good solution more quickly which can not be obtained when only setting the vehicle number or the total distance as the object. Benchmarks for PDPTW are used to test this algorithm, and the comparison with taboo-search method is given. The results show that this algorithm is advantageous in computing speed and can improve the quality, of solutions compared with traditional heuristic methods.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]