摘要
提出了一种解决有时间窗口装卸货问题(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.
出处
《控制工程》
CSCD
2006年第5期413-415,419,共4页
Control Engineering of China
基金
国家自然科学基金资助项目(6027401360474002)