关键词: 物流工程, 车辆路径问题, 增广拉格朗日松弛, 电动车辆, 时空状态网络

Abstract:

In view of the problems existed in logistic vehicle operations like limited battery capacity and insufficient number of recharging stations, this paper proposes an integer linear programming model for vehicle route optimization based on the discrete time- space- state network. The modeling process considers the constraints of battery capacity, vehicle capacity, recharging station capacity, customer service time window, the spatial structure of road network, and so on. The state dimension is expanded to reflect the spatiotemporal trajectory of both the remaining loads and the remaining electricity of vehicles. The augmented Lagrangian model is established through the Lagrangian relaxation of customer service demand and recharging station capacity constraints, and the quadratic penalty items are added. The quadratic objective function is linearized, and the original problem is transformed as a series of shortest path subproblems, which can be circularly solved by the forward dynamic programming algorithm embedded in the block coordinate descent framework. Adding the penalty terms can break the symmetry problem of solutions and accelerate the convergence rate. The gap between the optimal upper and lower bounds is calculated to evaluate the quality of the feasible solutions. Test examples are constructed based on the Sioux Falls network. The experimental results show that the proposed method can synchronously optimize electric vehicle routing and recharging decisions in time, space and state dimensions, which can effectively avoid vehicles recharge detouring, reduce the recharging time in delivery, reduce the operational costs, and realize the optimal spatial-temporal allocation of urban electric logistics resources.

Key words: logistics engineering, vehicle routing problem, augmented Lagrangian relaxation, electric vehicles, timespace-state network