基于拉格朗日分解的电动汽车充电路径优化

Optimization of Electric Vehicle Charging Path Based on Lagrangian Decomposition

针对电动汽车充电路径优化问题,构建简单有效的车辆充电网络,考虑车辆剩余电量和充电站服务能力约束,以车辆行驶总时间最小为优化目标,建立基于多商品流的0-1整数规划模型.在拉格朗日分解框架下,构造所建模型的对偶问题,并利用次梯度算法对其求解.次梯度迭代过程中,对偶问题能够被分解为易处理的最短路径问题和半指派问题.通过应用标号算法求解最短路问题,设计有效的启发式方法求解半指派问题.仿真计算表明,求解算法能够在很短时间内达到非常小的优化间隙,验证了所提方法的可行性.

Aiming at the problem of electric vehicle charging path optimization,a simple and effective electric vehicle charging network is constructed in this paper.During the charging process,the remaining battery capacity of electric vehicles and the service capacity of charging stations are considered.By constructing vehicle charging network,a binary integer programming model is established to minimize the total vehicle travel time.Under Lagrangian decomposition framework,the Lagrangian dual problem is first established for the proposed model,which is then solved by the sub-gradient method.At each iteration,the dual problem is decomposed into the tractable shortest path problems and the solvable knapsack problems.Thus the labeling algorithm is employed to solve the shortest path problems,and design the customized heuristic method to work out the knapsack problems.Simulation results show that the algorithm can achieve a very small optimization gap in a very short time,and the feasibility of the proposed method is verified.