摘要
针对城市物流配送和交通运输中广泛存在的带时间窗车辆路径问题,为寻求最佳路径规划,应用惩罚函数,构建了以总运输成本最小为目标的数学模型。在车辆路径优化求解方面,根据问题具体特征设计了1种二维编码方式,并采用近邻初始化方式构建初始解从而提升寻优速率;随后,结合狼群算法觅食行为中的游走、召唤及围攻3种行为,重新定义其智能行为,设计了一种求解带时间窗车辆路径问题的狼群算法。由于原始狼群算法的召唤行为引入距离判定因子来增大种群搜索空间,但也增加了算法复杂性且易陷入局部最优,故本研究舍弃了距离判定因子,采用猛狼1次奔袭便进入围攻状态来降低算法复杂度,并在算法中进一步增强了种群间信息交互。最后,应用该狼群算法求解多个测试算例。结果表明:狼群算法在求解带时间窗的车辆路径问题时是可行的、有效的;与禁忌搜索算法、遗传算法、改进蚁群算法和混合粒子群算法等常见智能优化算法相比,狼群算法不仅具有收敛速度快和搜索质量高等优点,而且拥有良好的稳定性和求解效果。
Aiming at the problem of vehicle routing with time windows which is widely existed in urban logistics distribution and transport,in order to seek the best path planning,a mathematical model with the aim of minimizing the total transport cost is constructed by using the penalty function. A 2D coding mode is designed according to the specific characteristics of the problem for vehicle routing optimization,and the initial form of the nearest neighbor is used to construct the initial solution to improve the optimization rate.Based on the 3 kinds of foraging behaviors including migration,summon and attack in wolf pack algorithm,the intelligent behavior is redefined,and a new wolf pack algorithm for solving VRPTW is designed. Since the distance judgment factor is used in the original wolf pack algorithm to improve the search population space,but it also increased the complexity of the algorithm and easily getting into the local optimum in the process,so the distance judgment factor is abandoned from the new wolf pack algorithm,and the wolf has only one raid in attack process is used to reduce algorithm complexity. Then,the interaction of information among populations is enhanced in the algorithm. At last,several numerical examples are solved by this algorithm. The result shows that the wolf pack algorithm is feasible and effective for solving VRPTW;compared with other common intelligent optimization algorithms such as tabu search algorithm,genetic algorithm,improved ant colony algorithm and hybrid particle swarm optimization algorithm,the wolf pack algorithm not only has the advantages of better convergence and higher search quality,but also has goodstability and solution effect.
作者
叶勇
张惠珍
YE Yong ZHANG Hui-zhen(School of Management, University of Shanghai for Science and Technology, Shanghai 200093, Chin)
出处
《公路交通科技》
CAS
CSCD
北大核心
2017年第10期100-107,共8页
Journal of Highway and Transportation Research and Development
基金
国家自然科学基金项目(71401106)
教育部人文社会科学基金项目(No.16YJA630037)
上海市教育委员会科研创新项目(14YZ090)
沪江基金项目(A14006)
关键词
交通工程
路径优化
狼群算法
时间窗
车辆路径问题
traffic engineering
route optimization
wolf pack algorithm
vehicle routing problem
time windows
