多车型电动汽车车辆路径问题的分支定价算法研究

Branch-and-price algorithm for heterogeneous electric vehicle routing problem

随着环境意识的日益提升和电动汽车的逐渐普及,考虑到物流企业中不同类型的电动汽车的电池最大容量、电池充电率、电量单位消耗率、最大载重量、固定成本和可变成本不同,本文研究含时间窗的多车型电动汽车车辆路径问题,建立了一个混合整数规划模型,并利用分支定价算法求其最优解.为了加快算法的求解速度,本文提出生成下界值的方法以对车辆类型进行预处理操作,并制定了生成整数解上界的策略以压缩解空间.然后,通过用多组算例验证了模型和算法结果的准确性,同时也证明了本文提出的加速过程能有效地提高算法的求解速率.最后,通过不同规模的算例分析了车辆可变成本的变化对结果的影响.

With the increase of environmental awareness, logistics companies begin to use different types of electric vehicles for deliveries. The types of vehicles differ with respect to battery capacity, battery charge rate, battery consumption rate, load capacity, fixed cost and variable cost. In this paper, we present the heterogeneous electric vehicle routing problem with time windows. The problem is formulated as a mixed integer programming model. A modified branch-and-price algorithm is proposed to obtain the optimal solution. In order to accelerate converging process, we generate the lower bound and upper bound of the solution to pre-process the vehicle types and compress the solution space. Furthermore, compared with the MIP solver of CPLEX, the computational results based on the benchmark instances show the accuracy and efficiency of the algorithm. Finally, the effect of variable cost is analyzed based on different sized examples.