首页 | 本学科首页   官方微博 | 高级检索  
     

带多软时间窗VRP及其禁忌搜索算法
引用本文:谢九勇,符卓,邱萌,夏扬坤. 带多软时间窗VRP及其禁忌搜索算法[J]. 计算机工程与应用, 2019, 55(6): 252-256. DOI: 10.3778/j.issn.1002-8331.1711-0276
作者姓名:谢九勇  符卓  邱萌  夏扬坤
作者单位:中南大学 交通运输工程学院,长沙 410075;中南大学 交通运输工程学院,长沙 410075;中南大学 交通运输工程学院,长沙 410075;中南大学 交通运输工程学院,长沙 410075
基金项目:国家自然科学基金;中南大学中央高校基本科研业务费专项资金项目
摘    要:分析了带多软时间窗VRP实际应用背景和特点,以使用的车辆数、行驶费用和偏离时间窗的惩罚费用为优化目标,结合车辆载重、最大路长等限制,建立该问题的数学模型,并设计求解该问题的自适应禁忌搜索算法。为增强算法的全局寻优能力,设计了多邻域结构并在算法中嵌入一种有限地接受不可行解的自适应机制。分别用文献中的算例和以Solomon标准算例为基础构建的新算例测试该算法,并将结果与其他方法进行对比分析。对比结果表明,所提出的算法性能较好,能在可接受的时间内求出运输成本更少、满意度更高的解。

关 键 词:车辆路径问题  多软时间窗  禁忌搜索  物流配送

Tabu Search Algorithm for Vehicle Routing Problem with Multiple Soft Time Windows
XIE Jiuyong,FU Zhuo,QIU Meng,XIA Yangkun. Tabu Search Algorithm for Vehicle Routing Problem with Multiple Soft Time Windows[J]. Computer Engineering and Applications, 2019, 55(6): 252-256. DOI: 10.3778/j.issn.1002-8331.1711-0276
Authors:XIE Jiuyong  FU Zhuo  QIU Meng  XIA Yangkun
Affiliation:School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China
Abstract:The practical application background and characteristics of the Vehicle Routing Problem with Multiple Soft Time Windows(VRPMSTW) are analyzed. Taking the number of vehicles required, total travel cost and time window deviation as the optimization objective, combined with constraints such as vehicle capacity, maximum route length, a corresponding mathematical model is constructed. An adaptive tabu search algorithm is designed to solve the problem. In order to enhance the optimization ability of the algorithm, a multi neighborhood structure is designed and an adaptive mechanism is embedded in the algorithm to accept the infeasible solution. The algorithm is tested with examples in the literature and new instances based on the Solomon benchmark problems. Computational results are compared with other methods in the literature. The comparison results show that the algorithm proposed in this paper has better performance, and it can get the solution with less transportation cost and higher satisfaction in acceptable time.
Keywords:vehicle routing problem  multiple soft time windows  tabu search  distribution management  
本文献已被 万方数据 等数据库收录!
点击此处可从《计算机工程与应用》浏览原始摘要信息
点击此处可从《计算机工程与应用》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号