求解PDPTW问题的快速启发式算法  

Quick Heuristic Algorithm for Solving PDPTW Problem

作　　者：姜政[1] 谷寒雨[1] 席裕庚[1] 

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

出　　处：《控制工程》2006年第5期413-415,419,共4页Control Engineering of China

基　　金：国家自然科学基金资助项目(6027401360474002)

摘　　要：提出了一种解决有时间窗口装卸货问题(PDPTW)的快速启发式算法.该算法基于局域搜索和随机扰动的思想,以减少车辆数目为主要目标,采用了启发式的搜索方法并加入了随机扰动以跳出局部最小点。该算法可以在很短的时间内显著地提高解的质量,这是仅以减少总路程为主要目标的局域搜索和现代启发式算法不能达到的。对标准算例的测试和与禁忌搜索算法计算结果的比较,表明该算法对于求解此类有时间窗口装卸货问题比传统的启发式算法在计算速度和减少车辆数目上更具优势。A quick heuristic algorithm is proposed to solve the pickup and delivery problem wich time windows （PDFTW）. This algorithm is based on the idea of local search and random disturbance, wich takes reducing the vehicle number as its main target, applies heuristic search method and uses random disturbance when entrapped in local minimum. This algorithm can get good solutions quickly. Benchmarks for PDTW are used to test the algorithm and the comparison with taboo-search method is given. The results show that the algorithm has its own advantages in computing speed and reducing vehicle number compared with traditional heuristic method.

关 键 词：带时间窗装卸货问题 NP-难问题 局域搜索 随机扰动 时间窗口 

分 类 号：O22[理学—运筹学与控制论]