多约束选址—路径问题的改进混合遗传算法研究

摘要

The location-routing problem(LRP),which simultaneously tackles both facility location and the vehicle routing decisions to minimize the total system cost,is of great importance in designing an integrated logistic distribution network.This paper developed a simulated annealing algorithm(SA) based hybrid genetic algorithm(GA) to solve the LRP with capacity constraints (CLRP) on depots and routes.The proposed algorithm modified the population generation method,genetic operators and recombination strategy and realized the combination of the local searching ability of SA and global searching ability of GA.To evaluate the performance of the proposed approach,this paper conducted an experimental study and compared its results with other heuristics on a set of well-known Barreto Benchmark instances.The experimental results verifies the feasibility and effectiveness of the approach.%选址—路径问题(LRP)同时解决设施选址和车辆路径问题,使物流系统总成本达到最小,在集成化物流配送网络规划中具有重要意义.针对带仓库容量约束和路径容量约束的选址—路径(CLRP)问题,提出了一种结合模拟退火算法的混合遗传算法进行整体求解.改进混合遗传算法分别对初始种群生成方式、遗传操作和重组策略进行改进,并实现了模拟退火的良好局部搜索能力与遗传算法的全局搜索能力的有效结合.运用一组Barreto Benchmark算例进行数值实验测试其性能,并将求解结果与国外文献中的启发式算法进行比较,验证了改进混合算法的有效性和可行性.