关键词: 电动汽车, 车辆路径, 时空网络, 分支定价算法

Abstract: This paper proposes a novel branch and price (B&P) algorithm to realize the route planning of vehicles and goods for the inter-town express package delivery system supported by electric vehicles. The time-space network is used to discretize the time to build a mathematical programming model, while the management of vehicle resources, storage resources and charging pile resources are taken into account. In the B&P algorithm, the combination of branch strategy and cutting plane strategy effectively weakens the symmetry problem caused by time discretization. The strengthening strategy effectively filters the generated path variables and uses a solver to help the algorithm quickly find a high-quality feasible solution. The experiment compares the B&P algorithm with commercial solvers and heuristic algorithms based on column generation. It shows that the B&P algorithm has obvious advantages in accurately solving small-scale problems and heuristically solving medium-scale problems, so that it can effectively solve the problems. 

Key words: electric vehicle, vehicle routing, time-space network, branch and price algorithm