• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Experimental and Efficient Algorithms(WEA 2005); 20050510-13; Santorini Island(GR) >A Cut-Based Heuristic to Produce Almost Feasible Periodic Railway Timetables
【24h】

A Cut-Based Heuristic to Produce Almost Feasible Periodic Railway Timetables

机译：基于削减的启发式方法来生成几乎可行的定期铁路时刻表

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider the problem of satisfying the maximum number of constraints of an instance of the Periodic Event Scheduling Problem (PESP). This is a key issue in periodic railway timetable construction, and has many other applications, e.g. for traffic light scheduling. We generalize two (in-) approximability results, which are known for MAXI-MUM-K-COLORABLE-SUBGRAPH. Moreover, we present a deterministic combinatorial polynomial time algorithm. Its output violates only very few constraints for five real-world instances.
机译：我们考虑满足周期性事件调度问题（PESP）实例的最大约束数量的问题。这是定期铁路时间表建设中的关键问题，并且还有许多其他应用，例如用于交通灯调度。我们归纳出两个（in-）近似结果，这些结果对于MAXI-MUM-K-COLORABLE-SUBGRAPH来说是已知的。此外，我们提出了确定性组合多项式时间算法。它的输出仅违反了五个实际实例的极少约束。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号