有时间窗的车辆路径问题的近似算法研究  

Improved large neighborhood search algorithm for vehicle routing problem with time windows

作　　者：刘小兰[1] 郝志峰[1] 汪国强[1] 符克强[1] 

机构地区：[1]华南理工大学应用数学系,广东广州510640

出　　处：《计算机集成制造系统》2004年第7期825-831,共7页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(19901009);广东省自然科学基金资助项目(000463;031360);教育部优秀青年基金资助项目;广东省"千百十工程"优秀人才基金资助项目。~~

摘　　要：为了克服原有大规模邻域搜索算法不能有效求解时间窗较宽的车辆路径问题的缺陷,介绍了有时间 窗的车辆路径问题(VRPTW)的通用数学模型。通过分析各主要变量之间的关系,构造了一种简单、快速的确定性 初始算法。通过引入”短路径优先策略”,构造了一种改进的大规模邻域搜索算法,该策略也可嵌入到求解时间窗 比较窄的车辆路径问题中,达到加速搜索的目的。试验结果表明,改进的算法可以在较短的时间内有效地求得 VRPTW的优化解,是求解VRPTW的一个较好方案。The vehicle routing problem with time windows (VRPTW) cannot be solved effectively by using the existing Large Neighborhood Search (LNS) algorithm. A universal mathematical model of VRPTW was built. By analyzing the relation of several main variables, a simple, fast deterministic initial algorithm was proposed. An improved LNS algorithm was put forward based on the shortest route priority strategy, which could solve the problems with long scheduling horizon effectively. The strategy could also be applied to solving the problems with short scheduling horizon to accelerate searching process. Experiment results show that the improved algorithm can find the optimal or near optimal solution to VRPTW in short time.

关 键 词：有时间窗的车辆路径问题 大规模邻域搜索算法 初始算法 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置]