基于禁忌搜索算法的线路规划方案求解

摘要

针对物流部门中出现的时间窗和车辆限制的开放性车辆线路问题（open vehicle routing problem with time window and vehicle limits，m-OVRPTW），提出基于禁忌搜索算法的线路规划方案。对问题进行数学建模；通过设计4种邻域变化规则、设定多个禁忌长度来改进局部搜索，快速得到高质量近似解，解决m-OVRPTW问题；通过反复选取车辆数量，解决OVRPTW问题。用56组Solomon基准测试数据（VRPTW benchmark problem）进行测试，测试结果表明，将禁忌搜索算法应用在开放性车辆线路问题中取得了较好成果，其在最小车辆数量、最小车辆行程、平均车辆总行程等方面的表现都优于其它算法。%Time window for the logistics sector in open vehicles and restrictions on car lines (Open Vehicle Routing Problem With Time Window and Vehicle Limits,referred to as m-OVRPTW),the proposed routing scheme based on tabu search algorithms. Mathematical modeling issues first;then through four neighborhoods changed rules,setting more taboos-length to improve local search,fast access to high quality approximation to solve m-OVRPTW problems;by repeatedly selecting the number of vehicles, solve the OVRPTW problem;finally,the 5 6 Group Solomon benchmarking data (VRPTW Benchmark Problem)for testing,ex-perimental results show that Application of tabu search algorithm in an open vehicle wiring problems for better results compared with similar studies from the minimum number of vehicles,the minimum,average vehicle trips vehicle trips,and so have better than the other algorithms.