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

作     者：程琳 宁翊森 宋茂灿 CHENG Lin;NING Yi-sen;SONG Mao-can

作者机构：东南大学交通学院江苏南京211189 

基　　金：国家自然科学基金项目(52172318 52131203) 

出 版 物：《交通运输工程学报》 (Journal of Traffic and Transportation Engineering)

年 卷 期：2022年第22卷第4期

页      码：273-284页

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

主 题 词：交通规划 弧路径 拉格朗日松弛 时间-空间网络 时变最短路 动态规划 

学科分类：0711[理学-心理学类] 08[工学] 082303[082303] 0835[0835] 0701[理学-数学类] 082302[082302] 0823[工学-农业工程类] 

核心收录：

D　O　I：10.19818/j.cnki.1671-1637.2022.04.021

馆 藏 号：203114482...