基于Benders分解的鲁棒最短路算法

• 作者: 冯轩 周和平 彭巍
• 来源期刊: 长沙理工大学学报（自然科学版）
• 学科: 交通运输
• 关键词: 路径选择 区间数据 鲁棒优化 最短路径 鲁棒成本 Benders分解算法
• 年，卷（期）: 2018,（2）
• 所属期刊栏目: 交通运输、土木与水利工程
• 页码范围: 16-20,42
• 页数: 6页
• 分类号: U491.1
• 字数: 3831字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-9331.2018.02.004

摘要

为了研究路段行程时间不确定条件下的最短路问题,采用区间数据表示路段行程时间,介绍了鲁棒偏差和鲁棒成本的概念,并据此给出鲁棒最短路的定义,运用鲁棒优化中的min-max准则构建了鲁棒最短路问题的混合整数规划模型.通过固定路径决策变量将鲁棒最短路问题分解为子问题和主问题,同时结合对偶理论给出子问题的对偶模型.在此基础上设计出鲁棒最短路问题的Benders分解算法,采用AMPL编程实现算法并调用CPLEX进行求解.并在一个仿真网络中对本研究方法进行了验证分析.研究结果表明,相较于传统最短路Dijkstra算法,本研究方法求得的鲁棒最短路在不确定网络中具有更强的可靠性,设计的算法迭代效率较高,能迅速缩小迭代范围并找到最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周和平	长沙理工大学交通运输工程学院	37	366	11.0	17.0
2	彭巍	长沙理工大学交通运输工程学院	6	14	3.0	3.0
3	冯轩	长沙理工大学交通运输工程学院	1	1	1.0	1.0