求解时间依赖型绿色车辆路径问题的算法研究

Research on an Algorithm for Solving Time-Dependent Green Vehicle Routing Problem

蚁群优化(ACO)算法是一种模拟自然界蚂蚁寻找食物路径的优化算法,能够在动态变化的环境中无需任何外部指导或控制解决几何分布的非确定性多项式(NP)-Hard组合问题。针对ACO算法在求解NP-Hard问题时容易陷入局部最优、搜索的深度与广度之间难以平衡等问题,提出一种绿色智能进化蚁群优化(G-IEACO)算法。引入4种邻域操作算子,改进ACO算法的状态转移规则和信息素更新方式,以增强寻优性能并防止过早收敛,同时采用规避拥堵策略,平衡时间成本和环境成本。应用Solomon标准测试集中不同规模的算例进行仿真实验,数值分析结果表明,G-IEACO算法在处理车辆总行驶时间(TT)和车辆碳排放量(TCO_(2))方面优于遗传算法(GA),在客户规模为100的R2类和RC2类算例中平均降低了13.32%的TT和13.64%的TCO_(2),有效地促进了绿色低碳目标的实现。

The Ant Colony Optimization(ACO)algorithm is an optimization algorithm that simulates the behavior of ants identifying food paths.It can solve the Non-deterministic Polynomial(NP)-hard combination problem of geometric distributions in a dynamically changing environment without any external guidance or control.To prevent the ACO algorithm from falling easily into the local optimum and to mitigate the difficulty in balancing the depth and breadth of search when solving NP-hard problems,a Green Intelligent Evolutionary Ant Colony Optimization(G-IEACO)algorithm is proposed.By introducing four types of domain operators,the state transition rules and pheromone update methods of the ACO algorithm are improved,thus enhancing the optimization performance and preventing premature convergence.Additionally,a congestion avoidance strategy is adopted to balance between time and environmental costs.Results of numerical analysis show that the G-IEACO algorithm outperforms the Genetic Algorithm(GA)in terms of the Total driving Time(TT)and vehicle carbon emission(TCO_(2))of the fleet.Specifically,it reduces the TT and TCO_(2)by 13.32%and 13.64%on average,respectively,in test cases of R2 and RC2 involving 100 clients,thus implying that it can effectively promote the realization of green and low-carbon goals.