车辆路径问题的禁忌搜索算法研究

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (24): 179-181.

车辆路径问题的禁忌搜索算法研究

刘兴^1,2，贺国光¹

1.天津大学管理学院，天津 300072
2.军事交通学院，天津 300161

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-08-21 发布日期:2007-08-21
通讯作者: 刘兴

Study on tabu search algorithm for stochastic vehicle routing problem

LIU Xing^1,2，HE Guo-guang¹

1.School of Management，Tianjin University，Tianjin 300072，China
2.Military Transportation Institute，Tianjin 300161，China

Received:1900-01-01 Revised:1900-01-01 Online:2007-08-21 Published:2007-08-21
Contact: LIU Xing

摘要/Abstract

摘要： 简要回顾了车辆路径问题的禁忌搜索算法的发展现状，提出了一种改进的禁忌搜索算法。该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题，然后用禁忌搜索算法求解每个子问题，最后从所有子问题的最优解中选出全局最优解。理论分析和实验结果表明该算法比以往的算法有以下优点：拓展了搜索空间，提高了最优解的效果;是一种将问题进行空间分解的并行算法，可采用多台计算机同时运算以减少整体运行时间。

关键词: 物流, 车辆路径问题, 禁忌搜索算法

Abstract: On the basis of describing the vehicle routing problem briefly，a new improved tabu search algorithm is presented.In this algorithm，routing problem is divided into several sub-problems according to vehicle-customer assigning structure，and an inner tabu search algorithm is applied for each sub-problem，at last the answer of the whole problem is find among the answers of all sub-problems.Two conclusions are drawn by computation results and theory：the algorithm extends the search scope，improving the optimisation effect;The algorithm is a collateral algorithm that can be run by several computer at the same time to decrease the whole optimisation time.

Key words: logistics, Stochastic Vehicle Routing problem（SVRP）, tabu search algorithm

刘兴^1,2，贺国光¹. 车辆路径问题的禁忌搜索算法研究[J]. 计算机工程与应用, 2007, 43(24): 179-181.

LIU Xing^1,2，HE Guo-guang¹. Study on tabu search algorithm for stochastic vehicle routing problem[J]. Computer Engineering and Applications, 2007, 43(24): 179-181.

[1]	张芳，武杰，杨悦. 风险规避的冷链物流服务供应链减排协调决策[J]. 计算机工程与应用, 2021, 57(24): 259-267.
[2]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[3]	李家斌，何世伟，刁丹丹，靳国伟，郭小乐. 物流包装租赁系统配送库存路径模型与算法[J]. 计算机工程与应用, 2021, 57(22): 263-272.
[4]	马艳芳，李保玉，杨屹夫，冯翠英. 客户分类下生鲜配送两级路径问题与算法研究[J]. 计算机工程与应用, 2021, 57(20): 287-298.
[5]	付朝晖，刘长石. 多物流中心共同配送的车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(16): 291-298.
[6]	张凯，靳鹏，崔勇. 带时间窗的多车型需求可拆分揽收配送问题[J]. 计算机工程与应用, 2021, 57(14): 281-288.
[7]	陈展，公建宁，刘媛媛，徐京邦. 基于禁忌搜索的多AGV系统路径优化算法[J]. 计算机工程与应用, 2021, 57(10): 273-278.
[8]	付朝晖，刘长石. 生鲜电商配送的开放式时变车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(1): 271-278.
[9]	张森，叶剑，李国刚. 面向冷链物流的区块链技术方案研究与实现[J]. 计算机工程与应用, 2020, 56(3): 19-27.
[10]	张建军，赵启兰. 线上零售商主导下供应链结构选择及演化[J]. 计算机工程与应用, 2020, 56(24): 249-259.
[11]	李锐，李晓会，陈鑫. 可靠性绿色物流配送选址-路径问题研究[J]. 计算机工程与应用, 2020, 56(23): 237-244.
[12]	应毅，任凯，刘亚军. 基于GIS技术和加权kNN算法的实时揽件调度方法[J]. 计算机工程与应用, 2020, 56(21): 248-252.
[13]	霍晴晴，郭健全. TBL理论下3C产品可持续闭环物流网络模糊优化[J]. 计算机工程与应用, 2020, 56(19): 237-243.
[14]	马艳芳，应斌，康凯，栾新凤. 模糊需求下绿色同时取送货问题与算法研究[J]. 计算机工程与应用, 2020, 56(16): 248-257.
[15]	张明伟，李波，屈晓龙，郭盈. 基于混合蚁群算法的异质车队低碳VRP研究[J]. 计算机工程与应用, 2020, 56(14): 240-249.