附录A 外文翻译-中文部分
直到所有的列车已经形成。如果一个分类轨道仅用于接收一辆驶出火车，但这些列车从来没有拉回到驼峰轨道，它被称为列车编组的轨道。
相关工作从工程的角度出发，在20世纪50年代和60年代的许多出版物中提出了多级方法。克雷尔比较两个基本方法和三个其中之一改进，包含一个从有限的可利用的分类轨道的例子。这些方法以前就被以不同形式弗兰多佛尔描述过。这些方法与1972年再次被西德迪克分析，19世纪80年代在一个由丹格则、道林和霍尔写的系列出版物。这些出版书一般处理多个出站列车，但列车入站的实际结构是完全被忽略。一个与单级排序类似的分类问题被达尔豪斯、霍雷克、曼尼、米勒和瑞安于2000年研究。对于他们的列车分类模型，他们给了列车的进入想法，用于改善分类过程。在出站列车要求，顺序被视为自由，而找到一个最优调度等类型的最佳证明是不完全的。
汉斯曼和齐默尔曼给出了一个单一的分类和多级分类方法的系统框架。对于一个有限数量的分类轨道和扩展的出站要求，把车列处理成同一类型，在第六章中自主地获得结果。此外，作者展示了一个特定的多级方法，寻找一个最优调度上述提到的出站规范是很难的。鲍曼解释了有关多层次列车分类的设计方面的，在瑞士蘇黎世利馬特河编组站编组。 由此产生的布局功能类似驼峰辅助图第2（c），这是由于目前没有使用成本和组织的原因。本节中提到的历史性成果是在第四章从更多的理论基点重新考虑。 二、大纲
在下面的部分，我们正式地介绍上述的问题和概念，包括我们的问题。然后，我们在第三章为分类过程提出有效的编码。在第四章中让我们扼要地描述和分析上述方法。接着是分析第五章和第六章新问题的变化，和第七章结论性意见。 2.1分类调度
在本节中，我们描述的二进制数集的分类编码附表。相反，我们将展示如何将其解释为调度表，这将产生一个两者之间双射的关系。此外，有预排序的概念引入，使推导最优调度。事实证明，一个分类计划的核心已经可以考虑如何通过指定一个驶入火车火车到一个驶出排序。为此，我们首先考虑这种情况下开发的编码方案。在本节结束时，我们展示如何在一般情况下扩展结果。 2.2同时变种编组站
在基本型的同时编组，每一节列车被拉出一次，推送两次，在任一阶段。在其他的变种此限制被丢弃。相反的阶段，这些变种被指定成驼峰步骤序列，每种方法的特点是编码的共同属性类。
三角排序 所谓的同步编组给出三角排序变种，对应于每车允许至多三推式业务（包括最终推出了它的驶出列车车）。对于调度表编码，这将产生每节车厢不超过两位的限制。
37
附录A外文翻译－中文部分
2.3轨道容量限制 一般情况下
假设的分类范围内的轨道能力产生一个艰难的问题，如下定理三所示。在轨道上的约束能力，形式化如下：所有的轨道有一个最大能力，它们可容纳最多解体列车，采用特定
的轨道在列车编组异常出站列车的形成。我们不会允许这些轨道上牵出。
定理3.很难找到轨道能力内的上的最佳调度表。
证明。通过从“完全不等于3 - SAT的”， 这是已知的完全复位。给定一个实例变量有n和m的条款，我们构造一个列车为2n驶入要排序为2n个驶出列车，没有任何两列火车之间相互作用的实例，即第i个驶入列车只对第i驶出车厢。请注意，即使有多个驶入列车，它们的顺序是无关紧要的，因为有一个驶入与驶出列车（此形成对比的一般情况讨论的引理3）一对一的对应关系。为了论述方便，我们首先提出两个假设，并证明后，这些可以很容易地执行。首先，每车厢最多可以是部分额外的推送中。其次，我们可以对所有的轨道规定每个各自的能力。
该证明的主要思想是允许使用给定的数M= 4n + 2m的步骤，从而轨道让所有的驶入列车具有完全相同的M – 1链。因此，最多每列车的通路之一可以被分割或一个单一的轨道可以被闲置（如果有两个相同的列车在同一轨道上，他们必须在错误的顺序，因此必须有额外路线，与第一个假设矛盾）。该转型强制所有列车后一种可能性。因此，统一规定我们可以为每个列车编码，以免轨道不被闲置。
我们继续说明如何使用转换这个想法，并给出一个如图四的例子。首先，对驶入火车，
就足以说明了他们的路线各有长短，而不是让全序列导致这些路线。例如，我们将定义一个列车为
（1，4，2），由它的链（链序列）序列，而忽略这是否从一个驶入列车（2，6，1，3，4，7，5）附带或（ 6，2，3，1，4，5，7）。走行路线和轨道紧密相连。由于所有链链序列将有一个链少于所有轨道路线，走行路线分配可以通过给出的差距来指定到遗漏的轨道位置，例如，（1，*，4个指定位置， 2）。 2.4其他结果
有界最佳分类能力的最大能力调度表，每个位置总额的1的通过相应链的长度是有限的最大能力加权物业二进制编码。我们最近表明，如果所有的走行路线具有相同的长度可以构造最优的代码效率（中所形成的代码大小）。另一方面，对任意的链长的上述证明显示了完整性。
在本节中，我们考虑调车场宽度约束。我们特别感兴趣的是分类任务上不受宽度限制的最优分类表，需要一个抽屉数n，因此，有比可以利用的轨道数目W更多的合理的轨道。这个调度表是一般不直接实施的。在本节中我们将展示如何构建受限制宽度最优调度。从观察一，我们知道这是足以考虑一个单输入单输出驶出列车。如上文第一节，因为这是一
38
附录A 外文翻译-中文部分
个给定包括相应的调度表和可用于一个给定轨道的排序的最大数量设置的示例。如前所述，汉斯曼和齐默尔曼独立获得相同的结果。他们的描述还包括一个有许多同一类型的车 辆驶入，相同的整数可能会出现一次以上的驶入。
三、结束语
我们已经制定了一个调度表，以货物列车编组效率的编码方式来提出、分析并制定现 实世界的编组站的分类方法。这令人惊讶的简单的功能强大的编码可用于分析常用的 多级方法，我们证明在驼峰步骤方面的变种的同步最优排序，考虑到预分类输入效率。
四、未来工作
这可能是有趣的发现列车在文献分类的进一步优化准则，在实践中相关的，以纳入这 些目标的编码方案。有进一步的可能性指定出站要求，类似上述分块的概念，一个简单的 问题是如何在最佳的调度表得出这样的设置。最后，如果所提出的方法可以成功地模拟工 作，在实践中，其执行可能会加速在许多现实世界的驼峰码分类过程。
39