基于拉格朗日松弛的水灾逃生路径规划
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

O224

基金项目:

基金项目:中央高校基本科研业务费专项资金,项目编号:ZY2004;国家重点研发计划项目(国家危险化学品风险预警与信息共享服务关键技术研究与示范)资金,项目编号:2018YFC0809300;国家重点研发计划项目(典型危险化学品储存设施安全预警与防护一体化关键技术研究与应用示范)资金,项目编号:2016YFC0801200


Flood escape route planning based on Lagrange relaxation
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    本文研究了假设路段通行时间为随机变量的交通网络约束最短路径问题。建立0-1整数规划模型,求出最小期望通行时间路径。除流量平衡和路段通行能力约束外,还引入了唯一通路选择约束以保证最终只能生成最优路径。然后,提出了拉格朗日松弛法对难约束进行松弛处理,并将松弛模型分解成两个子问题。结合次梯度算法、标号修正算法和 最短路径算法设计了一个算法框架,以最小化上下界的差距寻找近似最优解,用改进的算法框架进行求解。最后将该框架应用于龙岩市新罗区进行了计算试验。结果表明,该算法能够找到相对间隙较小的高质量解,验证了该方法的有效性。

    Abstract:

    In this paper, the constrained shortest path problem of traffic network with the assumption that the road passage time is a random variable is studied. The 0-1 integer programming model is established to find out the path of the minimum expected travel time. In addition to flow balance and section capacity constraints, unique path selection constraints are introduced to ensure that only the optimal path can be generated in the end. Then, a Lagrange relaxation method is proposed to relax the difficult constraints and the relaxation model is decomposed into two subproblems. In order to minimize the difference between upper and lower bounds, an algorithm framework is designed, which combines the subgradient algorithm, label correction algorithm and -shortest path algorithm to find the approximate optimal solution. Finally, the framework is applied to xinluo District of Longyan city for calculation test. The results show that the proposed algorithm can find high quality solutions with small relative gaps, and the validity of the proposed algorithm is verified.

    参考文献
    相似文献
    引证文献
引用本文

锁启凤,张仲荣,窦站. 基于拉格朗日松弛的水灾逃生路径规划[J]. 科学技术与工程, 2021, 21(19): 7884-7890.
Suo Qifeng, Zhang Zhongrong, Dou Zhan. Flood escape route planning based on Lagrange relaxation[J]. Science Technology and Engineering,2021,21(19):7884-7890.

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-11-09
  • 最后修改日期:2021-04-20
  • 录用日期:2021-03-14
  • 在线发布日期: 2021-07-22
  • 出版日期:
×
律回春渐,新元肇启|《科学技术与工程》编辑部恭祝新岁!
亟待确认版面费归属稿件,敬请作者关注