计算机科学 ›› 2015, Vol. 42 ›› Issue (4): 230-234.doi: 10.11896/j.issn.1002-137X.2015.04.047
蔡延光,汤雅连,朱 君
CAI Yan-guang, TANG Ya-lian and ZHU Jun
摘要: 考虑到实际生活中车辆受发车时间限制以及道路路况影响运输成本等因素,建立了带客户软时间窗、车场硬时间窗、多车型、道路路况等约束的关联运输调度问题模型。结合禁忌搜索与遗传算法的优势,构造了混合禁忌搜索算法,以通过构造多个初始解来增大搜索空间;设计了两种禁忌表,分别为局部禁忌表和全局禁忌表,这不仅能加快寻优速度,还可以摆脱对单个解的依赖;将禁忌搜索生成的优化解作为遗传算法的初始解,可以加快寻优速度;自适应调整禁忌表长度可以避免早熟收敛;提取核心路径便于进行后期优化,relocate算子能减少路径网络回路数目。对实例进行的仿真表明,提出的IVRP优于一般的VRP,可节约大量成本,且提出的算法在收敛速度和寻优结果两方面都优于遗传算法和禁忌搜索算法。由3种算法求解得到的总成本、总里程及收敛时间的标准差体现出该算法的稳定性 比另外两种算法的好。
[1] Reed M,Yiannakou A,Evering R.An ant colony algorithm for the multi-compartment vehicle routing problem[J].Applied Soft Computing,2014,15:169-176 [2] Azi N,Gendreau M,Potvin J Y.An adaptive large neighborhood search for a vehicle routing problem with multiple routes[J].Computers & Operations Research,2014,41:167-173 [3] Michallet J,Prins C,Amodeo L,et al.Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services[J].Computers & Operations Research,2014,41:196-207 [4] Archetti C,Guastaroba G,Speranza M G.An ILP-refined tabu search for the directed profitable rural postman problem [J].Discrete Applied Mathematics,2014,163:3-16 [5] Gómez J R,Pacheco J,Gonzalo-Orden H.A Tabu Search Methodfor a Bi-Objective Urban Waste Collection Problem[J].Compu-ter-Aided Civil and Infrastructure Engineering,2013,30(1):1-18 [6] Cai Y,Zhang Z,Guo S,et al.A tree-based tabu search algorithm for the manpower allocation problem with time windows and job-teaming constraints[C]∥Proceedings of the Twenty-Third international joint conference on Artificial Intelligence.AAAI Press,2013:496-502 [7] Jia H,Li Y,Dong B,et al.An Improved Tabu Search Approach to Vehicle Routing Problem[J].Procedia-Social and Behavioral Sciences,2013,96:1208-1217 [8] 朱玲玲,杨爱琴,吴宽仁.基于协同自适应禁忌的多时窗VRP算法实现[J].计算机应用研究,2012,29(12):4542-4545 [9] Nguyen P K,Crainic T G,Toulouse M.A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows [J].European Journal of Operational Research,2013,231(1):43-56 [10] Tarantilis C D.Adaptive multi-restart Tabu Search algorithmfor the vehicle routing problem with cross-docking [J].Optimization letters,2013,7(7):1583-1596 [11] Jair J,Paternina-Arboleda C D,Cantillo V,et al.A two-pheromone trail ant colony system—tabu search approach for the he-terogeneous vehicle routing problem with time windows and multiple products[J].Journal of Heuristics,2013,19(2):233-252 [12] 余明珠,李建斌,雷东.装卸一体化的车辆路径问题及基于插入法的新禁忌算法[J].中国管理科学,2010,18(4):89-95 [13] 胡大伟,陈诚.遗传算法 (GA) 和禁忌搜索算法 (TS) 在配送中心选址和路线问题中的应用[J].系统工程理论与实践,2007,27(9):171-176 [14] 郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究[J].管理工程学报,2004,18(1):81-84 [15] 邵春福,熊志华,姚智胜.道路网短时交通需求预测理论、方法及应用[M].北京:清华大学出版社,2011 [16] 钟石泉.物流配送车辆路径优化方法研究[D].天津:天津大学,2007 [17] 汤雅连,蔡延光,赵学才.关联物流运输调度问题的改进遗传算法[J].微型机与应用,2012,31(17):69-71 [18] 张建林.MATLAB&Excel 定量预测与决策-运作案例精编[M].北京:电子工业出版社,2012 [19] Gendreau M,Hertz A,Laporte G.New insertion and postoptimization procedures for the traveling salesman problem[J].Ope-rations Research,1992,40(6):1086-1094 |
No related articles found! |
|