动态路网选址–路径优化算法及实现

Dynamic road network location-routing optimization algorithm and implementation

中文关键词  选址–路径  最近邻算法  最大–最小蚁群系统  模拟退火

英文关键词  location-routing  nearest neighbor algorithm  max-min ant system  simulated annealing

中文摘要

      针对路段通行时间随旅行时段变化的实际城市路网环境下的选址–路径问题, 建立其混合非线性整数规划 模型; 并在双层规划模型的基础上, 利用遗传算法进行设施选址, 改进蚁群算法进行车辆路径优化, 提出一种遗传算 法与改进蚁群算法协同的求解方法(GA–IACO). 在路径优化中, 基于NNC算法生成初始可行解集; 采用Max-Min蚁 群系统策略动态更新信息素范围, 降低陷入局部最优的可能性; 并通过模拟退火过程, 对邻域解集按照Metropolis准 则进行接收, 以增强算法的全局搜索能力. 在测试集上的结果表明了算法在时变有向网络上的可行性, 为验证算法 的有效性, 通过构建杭州市路网的富属性网络模型, 在得到路网结点间OD成本矩阵的基础上进行求解, 实验结果表 明, 配送成本平均降低6.92%, 选址–路径规划总成本平均降低7.09%, 所得结论为实际优化决策提供了理论支持.

英文摘要

      Aiming at the time dependent location-routing problem (LRP) under the actual urban road network environment, a mixed nonlinear integer programming model is established. Based on the Two-Level programming model, a collaborative solution of genetic algorithm and improved ant colony algorithm is proposed. Genetic algorithms solves the facility-location problem (FLP). The ant colony algorithm was improved to solve vehicle routing problem (VRP). It uses the NNC algorithm to generate the initial solutions, updates pheromone through Max-Min ant system strategy and receives the solutions with simulated annealing process so as to enhance the global search ability of the algorithm. The results on the test set show the feasibility of the algorithm on the time-varying directed network. The results of the experiment based on the OD cost matrix of Hangzhou road network show that the average delivery cost is reduced by 6.92%, and the total cost is reduced by 7.09%. The conclusions provide theoretical support for the actual Location-Routing optimization decision.