求解OVRPTW的多开始禁忌搜索算法

doi:10.3969/j.issn.1000-3428.2011.06.064

摘要/Abstract

摘要： 在对带时间窗的开放式车辆路径问题描述的基础上提出求解该类问题的一种多开始禁忌搜索算法。使用扫描算法和向前插入法相结合的两阶段方法产生随机的初始解，采用一种混合的启发式算法构建邻域结构，设计全局和局部2个禁忌表加强算法的全局寻优能力。用标准的测试算例对算法进行实验，结果表明该算法得到了较好的寻优效果。

关键词: 开放式车辆路径问题, 禁忌搜索算法, 时间窗

Abstract: On the basis of describing the Open Vehicle Routing Problem with Time Windows(OVRPTW), a Multi-Start Tabu Search(MS-TS) algorithm is presented. In this algorithm, the random initial solution is generated by the two-phase method of combining the sweep algorithm and push forward insertion heuristic, the neighborhood structure is constructed by a mixed heuristic algorithm, the capability of global optimization is improved by designing global and local Tabu list. With the normal test examples, the experiment is done, and a good optimization result is obtained.

Key words: open vehicle routing problem, Tabu search algorithm, time windows

中图分类号:

TP301.6

李三彬, 王黎明. 求解OVRPTW的多开始禁忌搜索算法[J]. 计算机工程, 2011, 37(6): 187-189.

LI San-Ban, WANG Li-Meng. Multi-start Tabu Search Algorithm for Solving OVRPTW[J]. Computer Engineering, 2011, 37(6): 187-189.

[1]	张阳,李雄飞. 基于时间窗口的舆情异动量化模型[J]. 计算机工程, 2019, 45(3): 315-320.
[2]	王劲松,李军燕,张洪玮. 基于IPv6的大规模网络异常流量检测系统设计[J]. 计算机工程, 2018, 44(10): 14-21.
[3]	郭小波,李松涛,张德贤. 基于联合退避-功率感知机制的物联网节点信息防碰撞算法[J]. 计算机工程, 2017, 43(6): 46-52.
[4]	韦炜,全渝娟,卓奕涛,陈学亮,林艳. 基于多阶马尔可夫预测的个性化推荐算法[J]. 计算机工程, 2015, 41(11): 59-66.
[5]	王群,戴秀岳,杨莉. 一种基于直觉模糊理论的P2P动态信任模型 [J]. 计算机工程, 2014, 40(8): 133-137.
[6]	杨春明，张晖，石大文. BBS网络舆情的在线自适应话题演化模型[J]. 计算机工程, 2014, 40(7): 317-321.
[7]	张艳梅,王璐. 适应用户兴趣变化的社会化标签推荐算法研究[J]. 计算机工程, 2014, 40(11): 318-321.
[8]	王连锋, 宋建社, 曹继平, 叶庆. 带硬时间窗模糊车辆路径问题的多目标优化[J]. 计算机工程, 2013, 39(4): 9-13,17.
[9]	陈忆群, 牟来彦, 陈国明, 李志业. 有数量限制的开放式车辆路径加速算法[J]. 计算机工程, 2012, 38(24): 137-140.
[10]	江俊杰, 王丽亚. 基于遗传算法的多技能需求现场产品服务调度[J]. 计算机工程, 2012, 38(18): 174-177.
[11]	王君, 李波, 卢志刚. 带时间窗动态车辆路径问题的优化调度策略[J]. 计算机工程, 2012, 38(13): 137-141.
[12]	潘立军, 符卓, 刘喜梅. 带工作时间与时间窗的开放式车辆路径问题[J]. 计算机工程, 2012, 38(04): 17-19.
[13]	李三彬, 柴玉梅, 王黎明. 需求可拆分的开放式车辆路径问题研究[J]. 计算机工程, 2011, 37(6): 168-171.
[14]	潘艳辉, 王韬, 吴杨, 王文豪. 基于信任的低地球轨道卫星网络路由安全机制[J]. 计算机工程, 2011, 37(20): 149-151.
[15]	刘卓扬. 复杂事件处理中时间窗口的改进[J]. 计算机工程, 2010, 36(19): 50-52.

求解OVRPTW的多开始禁忌搜索算法

Multi-start Tabu Search Algorithm for Solving OVRPTW

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10