摘要
车辆路径是一类NP(non-deterministic polynomial)完全问题,研究解决车辆路径问题的高质量启发式算法有着重要理论价值和现实意义。提出一种将最近邻搜索法和禁忌搜索法优势相结合的混合超启发式算法,用来解决带容量约束的车辆路径问题。先利用最近邻搜索法构建初步路线,再利用禁忌搜索法对内部线路和互跨线路进行优化。通过对基于标准数据集和6 772个烟草客户真实数据集进行应用验证,新算法在减少线路的总路程上具有显著效果,为大规模车辆路径问题的求解提供了新的求解思路。
Vehicle routing is a NP-complete problem.It is of theoretical and practical significance to study good quality heuristic algorithm for solving the vehicle routing problem.In order to solve the vehicle routing problem with capacity constraint,the paper presents a new and effective hybrid metaheuristic algorithm which combines the strengths of the well-known nearest neighbor search and tabu search.Nearest neighbor search is used to construct initial routes in the first stage,and then tabu search is utilized to optimize the intra-route and the inter-route in the second stage.The computational experiments are carried out on a standard benchmark and a real dataset with 6772 tobacco customers.The results demonstrate that the suggested method is highly competitive in reducing the total distance.It provides a new idea to solve the large scale vehicle routing problem.
出处
《华东交通大学学报》
2011年第1期62-67,共6页
Journal of East China Jiaotong University
基金
湖北省自然科学基金项目(2009CDB338)
关键词
大规模车辆路径问题
容量约束
最近邻搜索
禁忌搜索
混合启发式算法
large-scale vehicle routing problem
capacity constraint
nearest neighbor search
tabu search
hybrid heuristic algorithm
