拉格朗日松弛启发式算法求解时空网络下的弧路径问题

为减少车辆调度成本，优化车辆运输路径，在时空网络中研究路段作业车辆的弧路径问题；考虑道路出行的时变性，利用车辆运行的时间、空间特征，构建时间-空间网络，建立弧路径问题的时空网络流模型；设计了拉格朗日松弛启发式算法，引入拉格朗日乘子松弛耦合约束，构建拉格朗日松弛问题；进一步通过拉格朗日分解，把松弛问题分解为单车最短路问题；用次梯度算法更新乘子，求解拉格朗日对偶问题，并更新原问题最优解的下界；使用启发式算法获得可行解，并更新原问题最优解的上界；用六结点运输网络和Sioux-Falls网络下的算例对算法进行实证分析。计算结果表明：六结点运输网络中6个算例的上下界间隙值等于0或接近0，Sioux-Falls网络中算例2的间隙值为0.02%，其余5个算例的间隙值等于0，均可以得到质量较高的近似最优解；在最复杂的算例(15辆车，70个任务)中，算法在可接受的时间内也得到了间隙值为0的解，找出了最优的车辆路径；随着迭代次数的增加，拉格朗日乘子会逐步收敛到固定值；当车辆容量从50增加到100时，最优解从52下降到42，说明在任务数和车辆数一定时，适当增加车容量可以降低运营成本。可见，与商业求解器相比，拉格朗日松弛启发式算法的间隙值更小，求解质量更高，可以更有效地求解弧路径问题。

Lagrangian relaxation heuristic algorithm of arc routing problem under time-space network

The arc routing problem of road operating vehicles under the time-space network was studied to reduce the vehicle dispatching cost and optimize the vehicle transportation path. In view of the time variation of road travel and the time-space characteristics of vehicle operation, a time-space network was constructed, and a time-space network flow model for the arc routing problem was built. A heuristic algorithm based on Lagrangian relaxation was designed, and the Lagrangian multipliers were introduced to relax the coupling constraints to establish the Lagrangian relaxation problem. Furthermore, the relaxation problem was decomposed into the single vehicle shortest path problem by the Lagrangian decomposition. The sub-gradient algorithm was applied to update the multipliers, solve the Lagrangian dual problem, and update the lower bound of the optimal solution for the original problem. The heuristic algorithm was employed to produce a feasible solution and update the upper bound of the optimal solution for the original problem. Empirical analysis of the algorithm was carried out in different cases under the six-node transportation network and Sioux-Falls network. Calculation results show that the values of the gap between the upper and lower bounds of the six cases in the six-node transportation network are equal to 0 or close to 0. In the Sioux-Falls network, the gap value of Case 2 is 0.02%, and those of the remaining five cases are equal to 0. The approximate optimal solution with high quality can be obtained in all cases. In the most complex case (15 vehicles, 70 tasks), a solution without gap is obtained by the algorithm in an acceptable time, and the optimal vehicle paths are calculated. With the increase of the number of iterations, the Lagrangian multipliers will become fixed through gradual convergence. When the vehicle capacity increases from 50 to 100, the optimal solution reduces from 52 to 42, which shows that when the numbers of tasks and vehicles are constant, an appropriate increase in vehicle capacity is capable of reducing operating cost. Therefore, compared with commercial solvers, the heuristic algorithm based on the Lagrangian relaxation, featuring a smaller gap value and higher solution quality, is able to solve the arc routing problem more efficiently. 7 tabs, 11 figs, 33 refs.