蚁群算法在西餐连锁店配送路径中应用

Western-Style Food Delivery for Chain Store on Ant Colony Optimization

西餐连锁店的路径优化是各连锁店食品配送路线的优化,要求满足各连锁店时间窗的约束,可抽象为带时间窗的车辆路径问题(VRPTW).文中采用启发式算法对VRPTW求解.为正确衡量信息素和期望值浓度在进化的不同阶段对算法的贡献,引入了一种自适应转移策略来提高算法的求解效率,并通过综合考虑全局和局部信息的更新策略——蚁权策略进行信息素更新,加快算法的收敛速度.最后,通过11个经典VRPTW对该算法的性能进行了检验.并以大连市西餐连锁店为研究对象,运用本文所提出的蚁群算法求解大连市西餐连锁店的配送路线.

The routing problem of western-style food chain store（RPWF）is to provide food to the chain stores,which need meet the time constraints of different chain stores.So,the RPWF can be considered as the vehicle routing problem with time windows（VRPTW）.This paper proposes an improved ant colony optimization（IACO）to solve the RPWF.To judge whether the influence of pheromone trail and heuristic function satisfy the current condition or not,an adaptive strategy is developed to improve the solution quality of ACO and ant-weight strategy is used to accelerate the rate of convergence.Computational results on some benchmark instances with VRPTW problems examine the performance of ACO.In addition,the results in solving the real instance of RPWF in Dalian indicate that the proposed algorithm is effective.