基于遗传算法的时间表冲突自动解决

铁路运营的基础是一个有效的、无冲突的时间表，值得庆幸的是，每天都没有发生重大变化。但是，变化和调整是日常业务的正常组成部分，必须以时间表仍然可行的方式执行。更改的原因包括由于建筑措施或额外的火车路线造成的预定偏差。

当涉及到重新安排时间表时，计划者目前依赖于现代世界已知的最强大的计算器——他们的大脑。考虑到有许多潜在的有效时间表可供选择，重新安排特定领域的时间表需要很多经验。时间表计划者有责任找到一个好的解决方案;换句话说，定义一个可行的时间表，同时将额外的问题(如延误)保持在最低限度。其目的是在线路中断后尽快恢复到标准时间表。然而，时间表计划者不能保证他们所选择的时间表是在中断事件中所有潜在解决方案中最好的。因此，SBB的基础设施IT解决方案中心开发了一个全自动应用程序，以帮助时间表计划者在发生中断或轨道/资源分配冲突时，只需按一下按钮就可以计算出可行、有效的时间表。

遗传算法作为解决这一问题的方法

使用传统的方法和算法似乎不是解决这个规划问题的可行方法，因为它是一个所谓的NP(非确定性多项式)问题。换句话说，规划者寻找解决方案的搜索空间的大小不会随着输入参数的数量呈多项式增长，而是呈指数增长。为了说明，图1显示了两列火车从A点行驶到B点时的可能选项;一次在单轨上，一次在经过的轨道上。

图1:单轨和双轨线路的选项图

简单地添加一个经过的轨道将解决方案空间从两个扩展到12个有效选项。图表显示，“列车1”总是在“列车2”之前行驶，因此选项的数量又增加了一倍，因为列车2同样可以在列车1之前行驶。重要的是要注意，这些示例没有考虑时间。如果时间随着出发时间和旅程时间的变化而变化，这就产生了一个几乎无限的问题空间(搜索空间)。

为了解决这个复杂的问题，我们借鉴了人工智能领域的一种方法——“遗传算法”。这种方法遵循“适者生存”的进化策略。它的优势在于，即使在非常大的问题空间中，只要参数化正确，它也能收敛并找到好的解决方案。找到的每个解决方案都保证了时间表的可行性和无冲突性。然而，进一步的标准，如准点率和连接服务，用于评估时间表的质量，在日常运营中发挥作用。这些软标准使找到的每个时间表能够根据当前的操作状态进行重新评估。然而，它们也很难集成到算法中，因此当根据这些软标准进行测量时，不能保证任何一个选项都代表最佳解决方案。算法找到最佳解的可能性与待解决问题的复杂性成反比。

最终，快速找到一个好的解决方案比在太晚的阶段找到完美的解决方案更重要。

遗传算法是如何工作的

遗传算法与当前时间表同时建立。这个时间表在线路中断时不再可行，但它为遗传算法提供了一个很好的起点，现在它试图生成一个有效的解决方案。因此，现有的时间表被认为是第一个个体，时间表内的所有信息构成染色体，一条信息代表基因。

就像在进化中一样，单个个体不会形成一代人。由于这个原因，时间表被复制了n次，这意味着第一个人口由相同的时间表或n个个体组成。

然后根据每个个体(时间表)完成任务的情况进行评估，也就是说，它离可行的、有效的时间表有多近。评估函数依赖于这样的假设:一个糟糕的时间表包含很多冲突，而一个好的时间表只有少数冲突。如果一个时间表包含很多冲突，它将被分配一个高误差值，反之亦然。此外，误差函数还包括对延迟的评估，延迟的权重较小。这就导致了第二个条件，即一个好的时间表很少会造成延误。在误差函数中，占用冲突的权重中等，封闭轨道的权重很高。

在第一代中，所有个体的误差值显然是相同的，因为第一代种群由初始已知时间表的副本组成。遗传算法遵循自然规律，在类似于人类繁殖的过程中形成下一代，即随机选择一个个体作为母亲，另一个个体作为父亲，误差值低的个体被优先选择。这两个人就成了父母。父母的基因是随机混合的。染色体混合产生一个后代(一个新的个体=一个新的时间表)。个体经历了更多的随机突变，即在新个体产生之后，算法允许基因发生更多的随机突变。这使得新时间表成为新一代的第一个孩子，由于突变，新一代可能与父母不同。

这个过程进行n次，直到形成新一代的时间表。在评估了新的时间表之后，再生产周期再次开始，即生产下一代。这个过程不断重复，直到某个人解决了问题，也就是说，直到找到一个充分满足可行时间表条件的时间表。

由于必须假设算法不一定会找到最佳时间表，我们重新启动算法几次，并将它找到的所有解呈现给时间表规划器。然后，他们可以从建议的时间表中选择并激活他们最喜欢的，或者根据自己的标准进一步修改它。

图2:代表时间表的染色体示意图，其特征表示为基因

图3:两条染色体如何繁殖的示意图

内部开发的软件

我们在本文中描述的软件是一个“演示”应用程序。它的目的是确定在SBB中自动化精确定义的任务(自动重新安排现有时间表)的可行性。该项目使用敏捷方法来帮助我们快速对结果做出反应，并将新的发现直接集成到原型中。

该软件目前从SBB自己的外围系统收集数据，用于时间表规划和网络拓扑。下一步，核心算法将在软件方面进一步发展，并适应高性能计算架构(HPCA)的使用。由于该算法提供了非常高的并行性，因此计算将进一步调整以在新的高科技平台上运行。最大的挑战将是用一种可以找到HPCA优化结构的方式来表示数据。

其目的是开发一种应用程序，只需按一下按钮，就可以优化整个瑞士的时间表。实现这一目标的困难在于，它涉及超过10万次火车旅行和超过6000个点，产生了几乎无限的问题空间(搜索空间)。这就是为什么我们目前的目标听起来像是乌托邦。长期以来，许多专家也认为在这个问题上已经开展的工作是理想主义的。然而，如今只需按下一个按钮，就可以生成一个节点时间表。

图4:显示遗传算法如何工作的示意图

传记

德克亚伯学习计算机科学，特别关注人工智能。他是基础设施部门解决方案中心“研究与创新平台”的负责人瑞士联邦铁路公司(SBB)。在这个职位上，他负责实验解决方案，并寻找有关铁路优化问题的未知答案。

Jurg Balsiger是一名认证的商业信息专家- MBA ' IIMT ';弗里堡大学国际技术管理学院。j rg是瑞士联邦铁路(SBB)基础设施部信息技术主管。在此职位上，他负责“铁路控制系统”等解决方案。2010年之前，他曾担任Ernst & Young的企业基础设施架构全球总监。