引用本文:武楚雄,陈驰,张贵军.动态路网选址–路径优化算法及实现[J].控制理论与应用,2020,37(11):2398~2412.[点击复制]
WU Chu-xiong,CHEN Chi,ZHANG Gui-jun.Dynamic road network location-routing optimization algorithm and implementation[J].Control Theory and Technology,2020,37(11):2398~2412.[点击复制]
动态路网选址–路径优化算法及实现
Dynamic road network location-routing optimization algorithm and implementation
摘要点击 1807  全文点击 529  投稿时间：2019-12-23  修订日期：2020-06-30
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2020.91017
  2020,37(11):2398-2412
中文关键词  选址–路径  最近邻算法  最大–最小蚁群系统  模拟退火
英文关键词  location-routing  nearest neighbor algorithm  max-min ant system  simulated annealing
基金项目  国家自然科学基金项目(61773346), 浙江省自然科学基金重点项目(LZ20F030002)资助.
作者单位E-mail
武楚雄 浙江工业大学 wcx@zjut.edu.cn 
陈驰 浙江工业大学  
张贵军* 浙江工业大学 zgj@zjut.edu.cn 
中文摘要
      针对路段通行时间随旅行时段变化的实际城市路网环境下的选址–路径问题, 建立其混合非线性整数规划 模型; 并在双层规划模型的基础上, 利用遗传算法进行设施选址, 改进蚁群算法进行车辆路径优化, 提出一种遗传算 法与改进蚁群算法协同的求解方法(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.