基于混合禁忌搜索算法的随机车辆路径问题  

Stochastic vehicle routing problem based on hybrid tabu search algorithm

作　　者：李国明 李军华 LI Guo-ming;LI Jun-hua(Key Laboratory of Jiangxi Province for Image Processing and Pattern Recognition,Nanchang Hangkong University,Nanchang 330063,China)

机构地区：[1]南昌航空大学江西省图像处理与模式识别重点实验室,南昌330063

出　　处：《控制与决策》2021年第9期2161-2169,共9页Control and Decision

基　　金：国家自然科学基金项目(61440049,61866025,61866026);江西省自然科学基金项目(20181BAB202025);江西省优势科技创新团队计划项目(20181BCB24008)。

摘　　要：针对实际配送过程中客户需求、车辆服务时间随机可变,提出带软时间窗的随机需求和随机服务时间的车辆路径问题.以配送车辆行驶路径为研究对象,建立基于配送成本、时间惩罚成本、修正成本的配送车辆路径优化模型,并提出一种混合禁忌搜索算法.该算法将最近邻算法和禁忌搜索算法相结合,将时间窗宽度及距离作为最近邻算法中节点选择标准;并对禁忌搜索算法中禁忌长度等构成要素进行自适应调整,引入自适应惩罚系数.实验结果表明,改进后的混合禁忌搜索算法具有较强的寻优能力、较高的鲁棒性,同时算法所得车辆行驶路径受客户需求变动影响较小.In view of the stochastic change of customer demand and vehicle service time in the actual distribution process,this paper proposes the vehicle routing problem with stochastic demand and stochastic service time with soft time window.Taking the distribution vehicle driving path as the research object,a distribution vehicle path optimization model based on distribution cost,time penalty cost and modified cost is established.A hybrid tabu search algorithm is proposed which combines the nearest neighbor algorithm with the tabu search algorithm,the time window width and distance are taken as the criteria for node selection in the nearest neighbor algorithm.In addition,the tabu length and other components of tabu search algorithm are adaptive adjusted,and the adaptive penalty coefficient is introduced.The experimental results show that the improved hybrid tabu search algorithm has strong optimization ability,high robustness,and the vehicle driving path obtained by the algorithm is less affected by the change of customer demand.

关 键 词：随机需求 随机服务时间 机会约束规划 混合禁忌搜索算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]