A Branch and Bound Algorithm and Iterative Reordering Strategies for Inserting Additional Trains in Real Time: A Case Study in Germany

Tan Yuyan; Jiang Zhibin

首页> 外文期刊>Mathematical Problems in Engineering >A Branch and Bound Algorithm and Iterative Reordering Strategies for Inserting Additional Trains in Real Time: A Case Study in Germany

【24h】

A Branch and Bound Algorithm and Iterative Reordering Strategies for Inserting Additional Trains in Real Time: A Case Study in Germany

机译：实时插入附加列车的分支定界算法和迭代重排序策略：以德国为例

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

With the aim of supporting the process of adapting railway infrastructure and future traffic needs, we have developed a method to insert additional trains efficiently to an existing timetable without introducing large consecutive delays to scheduled trains. In this work, the problem is characterized as a job-shop scheduling problem. In order to meet the limited time requirement and minimize deviations to the existing timetable, the modification that consists of retiming or reordering trains is implemented if and only if it potentially leads to a better solution. With these issues in mind, the problem of adding train paths is decomposed into two subproblems. One is finding the optimal insertion for a fixed order timetable and the other is reordering trains. The two subproblems are solved iteratively until no improvement is possible within a time limit of computation. An innovative branch and bound algorithm and iterative reordering strategy are proposed to solve this problem in real time. Unoccupied capacities are utilized as primary resources for additional trains and the transfer connections for passengers can be guaranteed in the new timetable. From numerical investigations, the proposed framework and associated techniques are tested and shown to be effective.

机译：为了支持适应铁路基础设施和未来交通需求的过程，我们开发了一种方法，可以在现有时间表中有效地插入额外的火车，而不会给计划的火车带来较大的连续延误。在这项工作中，该问题的特征是车间作业调度问题。为了满足有限的时间要求并最大程度地减少与现有时间表的偏差，只有在可能导致更好的解决方案的情况下，才进行由重新计时或重新排序列车组成的修改。考虑到这些问题，添加火车路径的问题被分解为两个子问题。一种是寻找固定订单时间表的最佳插入方式，另一种是对火车进行重新排序。迭代地解决两个子问题，直到在计算时限内无法进行任何改进为止。提出了一种创新的分支定界算法和迭代重排序策略来实时解决该问题。空余容量被用作额外火车的主要资源，并且可以在新的时间表中保证乘客的换乘连接。通过数值研究，对提出的框架和相关技术进行了测试，并证明是有效的。

著录项

来源
《Mathematical Problems in Engineering》 |2015年第5期|289072.1-289072.12|共12页
作者
Tan Yuyan; Jiang Zhibin;
展开▼
作者单位

Tech Univ Carolo Wilhelmina Braunschweig, Inst Railway Syst Engn & Traff Safety, D-38106 Braunschweig, Germany.;

Tongji Univ, Sch Transportat Engn, Shanghai 201804, Peoples R China.;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类
关键词

相似文献

外文文献
中文文献
专利

1. A Branch and Bound Algorithm and Iterative Reordering Strategies for Inserting Additional Trains in Real Time: A Case Study in Germany [J] . YuyanTan, ZhibinJiang Mathematical Problems in Engineering: Theory, Methods and Applications . 2015,第2期

机译：实时插入附加列车的分支定界算法和迭代重排序策略：以德国为例
2. Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds [J] . Xuesong Zhou, Ming Zhong Transportation Research Part B: Methodological . 2007,第3期

机译：保证最优性的单轨列车时间表：具有增强的下界的分支定界算法
3. Reordering and Local Rerouting Strategies to Manage Train Traffic in Real Time [J] . Andrea DAriano Francesco Corman Dario Pacciarelli Marco Pranzo TRANSPORTATION SCIENCE . 2008,第4期

机译：实时管理火车交通的重排序和本地重路由策略
4. G-SCAN: A Novel Real-Time Disk Scheduling Using Grouping and Branch-and-Bound Strategy [C] . Taeseok Kim, Eungkyu Song, Yunji Koh, International Conference on Computational Science and Its Applications(ICCSA 2006) pt.1; 20060508-11; Glasgow(GB) . 2006

机译：G-SCAN：使用分组和分支定界策略的新型实时磁盘调度
5. DCABB: A framework for the development of distributed branch and bound algorithms. [D] . Kudva, Gautham K. 1994

机译：DCABB：用于开发分布式分支定界算法的框架。
6. Metallic artifact reduction by evaluation of the additional value of iterative reconstruction algorithms in hip prosthesis computed tomography imaging [O] . Angeliki Neroladaki, Steve Philippe Martin, Ilias Bagetakos, -1

机译：通过评估髋关节假体计算机断层扫描成像中迭代重建算法的附加值来减少金属伪影
7. Figure 4: (A) One conserved sequence, which occurs 79 times in 46,264 binding site peaks from the ChIP-seq data-set. The mutation profile of this conserved sequence is illustrated, where ’_ ’ indicates this base is unchanged; DEL indicates this base is lost; INS X indicates a new base X is inserted in front of this base. (B) Several repeated elements patterns are listed. (C) In the first column, the top five DNA motifs, mined by meme-chip tools (Machanick Bailey, 2011) are illustrated. The resemblant conserved sequences, found by the CFSP algorithm are listed in the second column. In the third column, the position-specific scoring matrices, which are transformed from mutational information are listed. The similarity between meme motif and resemblant conserved sequence with PSSM format was calculated via a stamp motif comparison tool (Mahony Benos, 2007). The E-values for the similarity of those pairs is displayed in the fourth column. (D) One motif is selected in each group clustered by gkmsvm descriptors, and the corresponding motif found by the CFSP algorithm is listed below. (E) There are additional datasets (File No: ENCFF100GRL, ENCFF616IRT, ENCFF870CER, Target: SREBF1) collected from https://www.encodeproject.org. The top two motifs are selected in each file using meme tools, and the corresponding motifs found by our algorithm are listed below. [O] . -1

机译：图4：（a）一种保守序列，其发生在芯片-SEQ数据集中的46,264个结合位点峰值中的79倍。说明了这种保守序列的突变分布，其中'_'表示该碱度不变; del表示此基础丢失; INS X表示新的基础X插入此基础前面。（b）列出了几种重复的元素模式。（c）在第一栏中，示出了由MEME芯片工具（Machanick＆Bailey，2011）开采的前五个DNA主题。由CFSP算法发现的相应保守序列列于第二列中。在第三列中，列出了从突变信息转换的特定位置的评分矩阵。 MEME主题与PSSM格式的相似性与PSSM格式之间的相似性通过邮票图章比较工具（Mahony＆Benos，2007）计算。这些对相似性的电子值显示在第四列中。（d）在由GKMSVM描述符聚集的每个组中选择了一个图案，下面列出了CFSP算法的相应主题。（e）从https://www.encodeproject.org收集的，有附加数据集（文件no：cernff100grl，cenf616irl，conf8.20cer，target：srebf1）。使用MEME工具在每个文件中选择前两个图案，并且我们的算法发现的相应主题如下所示。

A Branch and Bound Algorithm and Iterative Reordering Strategies for Inserting Additional Trains in Real Time: A Case Study in Germany

摘要

著录项

相似文献

相关主题

期刊订阅