求解带时间窗车辆路径问题的狼群算法

发布时间：2018-04-23 06:44

本文选题：交通工程 + 路径优化　；参考：《公路交通科技》2017年10期

【摘要】：针对城市物流配送和交通运输中广泛存在的带时间窗车辆路径问题,为寻求最佳路径规划,应用惩罚函数,构建了以总运输成本最小为目标的数学模型。在车辆路径优化求解方面,根据问题具体特征设计了1种二维编码方式,并采用近邻初始化方式构建初始解从而提升寻优速率;随后,结合狼群算法觅食行为中的游走、召唤及围攻3种行为,重新定义其智能行为,设计了一种求解带时间窗车辆路径问题的狼群算法。由于原始狼群算法的召唤行为引入距离判定因子来增大种群搜索空间,但也增加了算法复杂性且易陷入局部最优,故本研究舍弃了距离判定因子,采用猛狼1次奔袭便进入围攻状态来降低算法复杂度,并在算法中进一步增强了种群间信息交互。最后,应用该狼群算法求解多个测试算例。结果表明:狼群算法在求解带时间窗的车辆路径问题时是可行的、有效的;与禁忌搜索算法、遗传算法、改进蚁群算法和混合粒子群算法等常见智能优化算法相比,狼群算法不仅具有收敛速度快和搜索质量高等优点,而且拥有良好的稳定性和求解效果。
[Abstract]:Aiming at the vehicle routing problem with time windows widely existing in urban logistics distribution and transportation, a mathematical model with the goal of minimizing the total transportation cost is constructed to find the best path planning and to apply the penalty function. In the aspect of vehicle path optimization, a two-dimensional coding method is designed according to the specific characteristics of the problem, and the initial solution is constructed by using the nearest neighbor initialization method to improve the optimization rate. The intelligent behavior of summoning and besieging is redefined and a wolf swarm algorithm is designed to solve the vehicle routing problem with time windows. Because the call behavior of the original wolf swarm algorithm introduced the distance decision factor to increase the population search space, but also increased the complexity of the algorithm and easily fell into the local optimum, so this study abandoned the distance decision factor. In order to reduce the complexity of the algorithm, the wolf is used to attack once and then enter the besieged state, and the information interaction among the populations is further enhanced in the algorithm. Finally, the wolf swarm algorithm is applied to solve multiple test cases. The results show that the wolf swarm algorithm is feasible and effective in solving the vehicle routing problem with time windows, and compared with Tabu search algorithm, genetic algorithm, improved ant colony algorithm and hybrid particle swarm optimization algorithm. The wolf swarm algorithm not only has the advantages of fast convergence and high search quality, but also has good stability and solution effect.
【作者单位】：上海理工大学管理学院;
【基金】：国家自然科学基金项目(71401106) 教育部人文社会科学基金项目(No.16YJA630037) 上海市教育委员会科研创新项目(14YZ090) 沪江基金项目(A14006)
【分类号】：TP18;U116.2

【相似文献】