蚁群混合算法求解带时间窗车辆路径问题

发布时间：2018-03-23 12:02

本文选题：VRPTW　切入点：蚁群算法　出处：《西安科技大学》2017年硕士论文

【摘要】：随着经济的繁荣发展,企业对物流配送的需求量急剧增加,对物流配送服务质量的要求也越来越高。对于物流配送企业来说,要保持核心竞争力,就要在提高服务质量的同时降低运输成本。本文首先将物流企业所面临的问题归类于带时间窗车辆路径问题(VRPTW),并建立以固定成本、可变成本、时间惩罚费用最小化为目标函数的数学模型,在所有可行方案中保留满足约束的最优方案,该方案既节省了物流企业的配送成本,又提高了客户对服务的满意程度。其次,将遗传、蚁群两种算法融合得到改进的蚁群混合算法(ACO-GAF)。为了使蚂蚁寻优结果更符合VRPTW的需求,在蚁群状态转移概率公式中增加容量因素和时间窗紧度因素;为了使遗传算法跳出局部最优,在交叉、变异操作后引入鱼群算子继续寻优。再将遗传、蚁群寻优解群体合并,计算适应度函数后通过轮盘赌选择出最优个体,寻优完成后更新路径信息素。在MATLAB平台上,使用Solomon数据库中的RC系列算例,设置适当的参数值,以路程最短和车辆数最少为目标,并将ACO-GAF算法求解各算例的结果与目前最优解进行对比,结果表明ACO-GAF算法在减少车辆数上取得了较大的进步;另外,将ACO-GAF算法求解结果与遗传算法、蚁群算法、鱼群算法求解结果进行对比,ACO-GAF算法在寻优效率和寻优结果方面均优于各单一算法。最后,将带时间窗车辆路径问题数学模型应用于实例中,以某厂商为华润万家超市配送货物为例,使用ACO-GAF算法求解车辆配送路线方案,求解结果在总路程、迟到惩罚费用方面得到了优化,求解结果表明本文建立的求解带时间窗车辆路径问题模型具有一定的实用性,求解带时间窗车辆路径问题的ACO-GAF算法有效可行。
[Abstract]:With the development of economy, the demand for logistics and distribution is increasing rapidly, and the requirement for service quality of logistics distribution is becoming higher and higher. For logistics distribution enterprises, it is necessary to maintain the core competitiveness. At the same time, it is necessary to reduce the transportation cost while improving the service quality. Firstly, the problems faced by the logistics enterprises are classified into the vehicle routing problem with time window (VRPTWN), and the fixed cost and variable cost are established. The mathematical model of minimizing the cost of time punishment as the objective function preserves the optimal scheme which satisfies the constraints in all feasible schemes. This scheme not only saves the distribution cost of the logistics enterprise, but also improves the satisfaction degree of the customer to the service. ACO-GAFA, an improved ant colony hybrid algorithm, is fused by genetic and ant colony algorithms. In order to meet the requirements of VRPTW, the capacity factor and the time window tightness factor are added to the ant colony state transition probability formula. In order to make the genetic algorithm jump out of the local optimum, after crossover, mutation operation, the fish swarm operator is introduced to continue the optimization. Then the genetic and ant colony optimization solutions are combined, the fitness function is calculated and the optimal individual is selected by roulette. Update path pheromone after optimization. On MATLAB platform, use RC series of examples in Solomon database, set appropriate parameter value, take the shortest distance and the least number of vehicles as the target, The results of ACO-GAF algorithm are compared with the current optimal solution. The results show that the ACO-GAF algorithm has made great progress in reducing the number of vehicles. In addition, the result of ACO-GAF algorithm is compared with that of genetic algorithm, Ant Colony algorithm (ACA). Compared with the results of fish swarm algorithm, ACO-GAF algorithm is superior to any single algorithm in the efficiency and result of optimization. Finally, the mathematical model of vehicle routing problem with time window is applied to an example. Taking a manufacturer as an example, the ACO-GAF algorithm is used to solve the vehicle distribution route scheme. The result is optimized in the aspects of total distance, late penalty cost, etc. The results show that the model established in this paper is practical and the ACO-GAF algorithm for solving the vehicle routing problem with time window is effective and feasible.
【学位授予单位】：西安科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：F252;TP18

【参考文献】