计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (36): 42-44.DOI: 10.3778/j.issn.1002-8331.2008.36.011

• 博士论坛 • 上一篇    下一篇

有软时窗多车场开放式车辆路径及其禁忌搜索

段凤华,符 卓   

  1. 中南大学 交通运输工程学院,长沙 410075
  • 收稿日期:2008-09-02 修回日期:2008-10-31 出版日期:2008-12-21 发布日期:2008-12-21
  • 通讯作者: 段凤华

MultiDepot Open Vehicle Routing Problem with soft time windows and its Tabu Search

DUAN Feng-hua,FU Zhuo   

  1. School of Traffic and Transportation Engineering,Central South University,Changsha 410075,China
  • Received:2008-09-02 Revised:2008-10-31 Online:2008-12-21 Published:2008-12-21
  • Contact: DUAN Feng-hua

摘要: 有软时窗约束多车场开放式车辆路径问题是在基本的车辆路径问题上增加了时间窗约束和多车场作业的一种变化形式,是一个典型的NP-难问题。建立了问题模型,运用改进的禁忌搜索算法测试了算例。快速获得的高质量解验证了模型的正确性和算法性能的优良性。

关键词: 物流配送, 开放式车辆路径问题, 软时间窗, 多车场作业, 禁忌搜索

Abstract: MultiDepot Open Vehicle Routing Problem with soft time windows is a variation of the Vehicle Routing Problem constrained by multidepot and soft time windows,which is a typical NP-hard problem.The mathematical model and example about the problem are built,an improved Tabu Search(TS) is designed to solve the problem.Excellent computational results of examples obtained quickly show the right of the model and goodness of the algorithm.

Key words: delivery, Open Vehicle Routing Problem, soft time windows, MultiDepot, Tabu Search(TS)