基于分支定价算法的电动汽车车辆路径问题

Electric Vehicle Routing Problem Based on A Branch-and-Price Algorithm

目前,随着电动汽车的普及,物流企业逐渐重视电动汽车的应用。本文考虑到电动汽车在实际应用中的行驶里程、充电耗时以及配送时间等因素,研究含时间窗的电动汽车车辆路径问题,建立了相应的混合整数规划模型,然后改进分支定价算法以求得其最优解。改进的分支定价算法首先根据Dantzig-Wolfe分解原理将原问题分解为基于路径的主问题(MP)和求最短路径的子问题,然后用列生成和动态规划算法在主问题和子问题之间进行迭代以求得主问题线性松弛后的最优解,最后采用基于弧的分支策略求得其整数解。通过用改进的Solomon算例的实验数据,与CPLEX比较验证了模型和算法结果的准确性,并对该问题进行了灵敏度分析,证明了本文提出的算法具有一定的应用价值。

At present, green logistics issues are emerging as the new agenda item and gaining interest in supply chain management. The traditional objective of distribution management has been developed into tem-wide costs which consider economic and environmental issues. With the popularity of electric tics enterprises are starting to pay attention to the application of them. In this paper, we study the routing problem with time windows, and take the limited battery capacities and the recharging minimizing sysvehicles, logiselectric vehicle time of electric vehicles of the practical application into account, then establish the corresponding mixed integer programming model. Furthermore, We put forward a modified branch-and-price algorithm for the problem, and obtain the optimal solution. Firstly, the algorithm decompose the original problem into a main problem （MP）based on path and a shortest path problem with resource constraints（ SPPRC）, then use column generation method and dynamic programming algorithm to calculate between the linear relaxation of the main problem and the sub problem to seek the optimal solution iteratively. At last, we use the branching strategy which is based on the arc for integer solutions of the model. We use the improved Solomon instances as the experimental data. The accuracy of the model and algorithm are validated by CPLEX, and the sensitivity analysis of larger instances demonstrates that the proposed algorithm has a certain application value.