基于时空状态网络的电动物流车辆路径优化方法

针对电动物流车辆续航里程有限与充电基础设施不足的问题，综合考虑电池容量、车辆承载能力、充电站能力、客户服务时间窗、路网空间结构等约束条件，基于离散时空状态网络建立整数线性规划模型。扩展的状态维度可同时表征车辆剩余载重量和剩余电量的时空轨迹。通过对客户服务需求和充电站能力约束进行拉格朗日松弛，并增加二次惩罚项，构建增广拉格朗日模型。经过线性化处理二次目标函数，在块坐标下降框架下，原问题被分解为最短路径子问题，嵌入前向动态规划算法，循环依次求解。惩罚项的引入可以克服解的对称性问题，加快算法的收敛速率。通过计算最优上界与下界之间的间隙，评估可行解的质量。基于Sioux Falls网络构建测试算例，实验结果表明，该方法可以在时间、空间和状态维度上同步优化电动车辆路径和充电决策，可以有效避免车辆绕行充电，节省在途充电时间和配送成本，实现城市电动化物流资源的时空优化配置。

Electric Logistics Vehicle Routing Optimization Based on Space-time-state Network

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.