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