| 有时间窗的车辆路径问题的局部下降搜索算法 |
| |
| 引用本文： | 王兆赓,李建更.有时间窗的车辆路径问题的局部下降搜索算法[J].数学的实践与认识,2007,37(10):107-112. |
| |
| 作者姓名： | 王兆赓 李建更 |
| |
| 作者单位： | 北京工业大学,电子信息与控制工程学院,北京,100022 |
| |
| 基金项目： | 北京工业大学交通工程重点实验室开放课题;北京工业大学校科研和教改项目 |
| |
| 摘 要： | 介绍了一个求解有时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)的启发式算法——基于λ-交换的局部下降搜索算法(Local search descent method based on λ-interchange).VRPTW是指合理安排车辆行驶路线,为一组预先设定有时间限制的客户运送货物,在不违反时间要求和车辆容量限制的条件下使得成本最小.它是一个典型的NP-难题,可以通过启发式算法获得近优解来解决.通过两个实验验证,显示了局部下降搜索算法的优良性能,取得了很好的效果,可以作为进一步研究复杂算法的基础.
|
| 关 键 词： | 有时间窗的车辆路径问题 启发式算法 λ-交换 |
| 修稿时间： | 2004年9月5日 |
A Local Search Descent Method Heuristic for the Vehicle Routing Problem with Time Windows |
| |
| WANG Zhao-geng,LI Jian-geng.A Local Search Descent Method Heuristic for the Vehicle Routing Problem with Time Windows[J].Mathematics in Practice and Theory,2007,37(10):107-112. |
| |
| Authors: | WANG Zhao-geng LI Jian-geng |
| |
| Abstract: | This paper describes a heuristic in solving vehicle routing problem with time windows(VRPTW),called local search descent method based on λ-interchange.VRPTW is to serve a number of customers with known demand and predefined time windows at minimum cost,without violating the capacity and total time constraints for each vehicle.It is a typical NP-hard problem and best solved to near optimum by heuristics.These two experiments show the excellent performance of the algorithm and obtain good solution.Furthermore this algorithm can be a basic cornerstone of the more complex heuristics. |
| |
| Keywords: | vehicle routing problem heuristics λ-interchange |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
