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

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

Dynamic road network location-routing optimization algorithm and implementation

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, acollaborative solution of genetic algorithm and improved ant colony algorithm is proposed. Genetic algorithms solves thefacility-location problem (FLP). The ant colony algorithm was improved to solve vehicle routing problem (VRP). It usesthe NNC algorithm to generate the initial solutions, updates pheromone through Max-Min ant system strategy and receivesthe solutions with simulated annealing process so as to enhance the global search ability of the algorithm. The results on thetest set show the feasibility of the algorithm on the time-varying directed network. The results of the experiment based onthe OD cost matrix of Hangzhou road network show that the average delivery cost is reduced by 6.92%, and the total costis reduced by 7.09%. The conclusions provide theoretical support for the actual Location-Routing optimization decision.