Abstract: To improve the work efficiency and reduce the distribution cost,the material distribution route planning problem for multiple automated guided vehicles was analyzed,and it was formulated as a vehicle routing problem with soft time windows and split deliveries by order.By taking the minimum number of automated guided vehicles utilization,the lowest total travel cost and the time window deviation as the first and second optimization objective respectively,and combining with constraints such as the maximum route length,vehicle capacity,split deliveries by order and the satisfaction rate of time window,a corresponding mathematical model was constructed.An adaptive tabu search algorithm was designed to solve the problem.To enhance the searching capability,some strategies such as adaptability,random tabu length and reinitializing tabu list were added to the algorithm.Computational results by the proposed algorithm on Solomn benchmark problems were provided and compared with other methods in the literature.The comparison results showed that more savings on both the number of automated guided vehicles used and the travel cost were obtained,and the results were equal to or close to the best known solutions for benchmark problems in the literature,which reflected the effectiveness of the algorithm.

Key words: automated guided vehicle, distribution routing planning, vehicle routing problem, tabu search, split deliveries by order, soft time windows

摘要： 为了提升作业效率、降低配送成本,分析了多自动导引车物料配送路径规划问题,将其归结为一种带软时间窗的需求依订单拆分车辆路径问题。以使用自动导引车数目最少、行驶费用和时间窗偏离费用最低分别作为第一、第二优化目标,结合最大路长、载重、需求依订单拆分及时间窗满足率限制,建立了相应的数学模型,并设计了一种自适应禁忌搜索算法求解该问题。为了增强禁忌搜索能力,在算法中嵌入了自适应性、随机禁忌长度和禁忌表重新初始化策略。给出了自适应禁忌搜索算法对Solomn测试算例的求解结果,并与文献中的其他方法进行比较,结果表明该算法在自动导引车使用数和行驶费用方面都有较多节省,且达到或接近已知最好解,体现了该算法的有效性。

关键词: 自动导引车, 配送路径规划, 车辆路径问题, 禁忌搜索, 需求依订单拆分, 软时间窗