• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual IEEE International Systems Conference >Segmented arrival graph based evacuation plan assessment algorithm using linear programming
【24h】

Segmented arrival graph based evacuation plan assessment algorithm using linear programming

机译：基于线性规划的分段到达图疏散计划评估算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The evacuation routing problem is NP-hard and hence no polynomial-time algorithm exists for the problem. There have been many studies on the evacuation planning heuristic algorithms but the in-depth comparison between them is not available especially in terms of the performance ratio. Without knowing the heuristic solution quality with respect to the optimal solution, we cannot accurately determine each heuristic algorithm's strengths and weaknesses that can lead to a better combination of heuristic algorithms. In this paper we present a Linear Programming (LP) based iterative algorithm to assess the evacuation planning algorithms in terms of the evacuation time. The proposed algorithm takes the paths that are found and/or used in a heuristic algorithm as the input and finds the minimum evacuation time using only those paths. To get the optimal solution, our algorithm repeatedly solves relaxed LP formulations formed from the concept of segmented arrival graphs. We segment the arrival graphs of paths based on the edge-sharing and construct the LP formulations along the segmented edges on the graphs. The computational experiment shows that the proposed algorithm computes the solution using time that is comparable to that of the heuristic algorithms as long as the number of paths is adequately maintained. Using the algorithm we perform the comparison between the existing heuristic algorithms, CCRP++, SMP, EET, and FBSP.
机译：疏散路由问题是NP难题，因此不存在用于该问题的多项式时间算法。关于疏散计划启发式算法的研究很多，但无法进行深入的比较，尤其是在性能比方面。在不了解启发式解决方案相对于最佳解决方案的质量的情况下，我们无法准确确定每种启发式算法的优缺点，而这些优势和劣势可能导致启发式算法的更好组合。在本文中，我们提出了一种基于线性规划（LP）的迭代算法，以根据疏散时间评估疏散计划算法。所提出的算法将在启发式算法中找到和/或使用的路径作为输入，并仅使用那些路径来找到最小疏散时间。为了获得最佳解决方案，我们的算法反复求解由分段到达图的概念形成的松弛LP公式。我们基于边缘共享对路径的到达图进行分段，并沿图上的分段边缘构造LP公式。计算实验表明，只要充分保持路径数量，该算法就可以使用与启发式算法相当的时间来计算解。使用该算法，我们可以在现有启发式算法CCRP ++，SMP，EET和FBSP之间进行比较。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号