附录A外文翻译－原文部分
which are picked up by freight locomotives to leave the classi?cation yard.Regarding the actual classi?cation procedure, there are essentially two modes of operation for shunting yards, which are typically performed in parallel or alternatingly: single-stage and multistage sorting. In single-stage sorting, each classi?cation track usually corresponds to a common destination, such as a remote classi?cation yard. Departing trains are built by collecting the cars from one or several tracks and coupling them into trains that leave the bowl to the departure yard—if there is any. Single-stage sorting is normally performed for large volume tra?c, e.g. tra?c between classi?cation yards, and the cars of the created trains are in arbitrary order.
For tra?c directly going to its ?nal destination, multistage sorting is used.Since the order requirements for this type of outgoing trains are more complex,single-stage sorting is not applicable here. In multistage sorting, after the incoming trains have been pushed over the hump (primary humping), a shunting engine repeatedly pulls back the cars from a given track (pull-out operation) over the hump on the hump track. These cars are then pushed over the hump again,so that again each car can be independently routed through the ladder to any classi?cation track. This process, called rehumping, is iterated until all outgoing trains have been formed. If a classi?cation track is used only for receiving cars of an outgoing train, but the cars on it are never pulled back to the hump track,it is called train formation track.
Related Work Multistage methods are presented from an engineering point of view in a number of publications from the 1950s and 1960s. Krell compares two basic multistage methods and three improvements of one of them, including an example for dealing with a restricted number of available classi?cation tracks. Some of these methods had been described earlier in a di?erent fashion by Flandor?er.Some of these methods were again considered by Siddiqee in 1972 and in a series of publications in the 1980s by Daganzo, Dowling, and Hall.These publications generally deal with multiple outbound trains, but the actual structure of inbound trains is completely ignored.A classi?cation problem similar to single-stage sorting was studied by Dahlhaus, Horak, Manne, Miller, and Ryan in 2000. For their train classi?cation model, they give a notion of presortedness of the input train which is used to improve the classi?cation process. Several degrees of freedom in the order requirement of the outbound train are regarded , while ?nding an optimal schedule for one speci?c such type is shown to be NP-complete.
A systematic framework for classifying single- and multistage classi?cation methods is given by Hansmann and Zimmermann. For the case of a limited number of classi?cation tracks
32
附录A 外文翻译-原文部分
and an extended output requirement which handles several cars being of the same type, they independently obtain the result we give in Sect. 6. Furthermore, the authors show for a speci?c multistage method that ?nding an optimal schedule is NP-hard for the output speci?cation of mentioned above.Baumann explains the design aspects concerning multistage train formation for the design of the classi?cation yard ?Z¨urich-Limmattal? in Switzerland.
The resulting layout features a secondary hump similar to Fig. 2(c), which is currently not used due to cost and organizational reasons.The historic results mentioned in this section are reconsidered in Sect. 4 from a more theoretical point of view. Outline
In the following section we introduce the above described problem and concepts formally, including the objective of our problem. Then, we present an e?cient encoding for representing the classi?cation process in Sect. 3. This allows us to concisely describe and analyze the above methods as done in Sect. 4,followed by analyzes of new problem variants in Sect. 5 and Sect. 6 and some concluding remarks in Sect. 7. Classi?cation Schedules
In this section we describe an encoding of classi?cation schedules by sets of binary numbers. Conversely, we show how to interpret such sets as schedules, which yields a bijective relation between both. Furthermore, a notion of presortedness is introduced, which allows deducing optimal schedules. As it turns out, the core of a classi?cation scheme can already be given by specifying how a single input train is sorted into a single output train. For this reason we ?rst consider this case and develop the encoding scheme. At the end of this section we show how to extend the results to the general case. Variant Of Simultaneous Marshalling
In the basic variant of simultaneous marshalling, every car is pulled out once and rolled in twice, once in either stage. In other variants this restriction is dropped. Instead of stages, these variants are speci?ed by sequences of hump steps, and each method is characterized by a class of encodings of common attributes.
Triangular Sorting A variant of simultaneous marshalling called triangular sorting is given by allowing at most three roll-in operations (including the ?nal roll-in of a car to its output train) for each car. For the schedule encoding, this yields a restriction of not more than two bits equal to one per car.
Restricted Track Capacities
33
附录A外文翻译－原文部分
General Case
Assuming bounded track capacities for the classi?cation tracks yields an NP-hard problem as shown in Thm. 3 below. The bound on the track capacities is formalized as follows: All tracks have a bounded capacity of Cmax, they can accommodate at most Cmaxcars, with the exception of speci?c train formation tracks where the outbound trains are formed. We do not allow to pull-out from these tracks.
Theorem 3.It is NP-hard to ?nd the optimal classi?cation schedule for capacitybounded tracks.Proof. By reduction from “Not ALL Equal 3-SAT” which is known to be NP-complete. Given an instance having n variables and m clauses, we construct an instance of 2n input trains that are to be sorted into 2n outgoing trains without any interaction between the trains, the ith input train has cars only for the ith outgoing train. Note that even though there are multiple input trains their order is irrelevant, because there is a one-to-one correspondence of input to output trains (this is in contrast to the general situation discussed in Lemma 3). For ease of exposition we start the proof by making two assumptions, and show later that these can be easily enforced. First,each car can be part of at most one additional roll-in. Second, we can have individual capacity bounds for all logical tracks.
The main idea of the proof is to allow to use a given number M= 4n + 2m of steps and thus logical tracks and to let all input trains have exactly M ? 1chains. It follows that at most one of the chains of each train can be split or a single logical track can be left unused (if two chains of the same train end up on the same track they must be in wrong order, which necessitates an additional roll-out in contradiction to the ?rst assumption). The transformation enforces the latter possibility for all trains. Thus, the “local decisions” that we can encode are for each train, which track should be left unused.
We proceed to show how to use this idea in the transformation and give an example in Fig. 4. First, for the input trains it is enough to specify the length of each of their chains, instead of giving the full sequence that leads to these chains.For example we will de?ne a train as (1, 4, 2) by its sequence of chains (chain sequence ) and ignore whether this comes from an input train (2, 6, 1, 3, 4, 7, 5) or (6, 2, 3, 1, 4, 5, 7). chains and logical tracks are tightly connected. As all chain sequences will have one chain less than there are logical tracks, the chain-to-track assignment can be speci?ed by giving the position of the gap, the logical track left out, e.g., (1, ?, 4, 2). Other Results
Optimal classi?cation schedules for tracks of bounded capacity Cmax translate to binary encodings B with the property that for each bit position the total sum of 1?s weighted by the
34
附录A 外文翻译-原文部分
lengths of the corresponding chains is bounded by Cmax. We have recently shown that if all chains have the same length optimal codes can be constructed e?ciently (in the size of the resulting codes). On the other hand, for arbitrary chain length the above proof shows NP-completeness.
In this section we consider the width constraint of a shunting yard. In particular we are interested in classi?cation tasks for which the optimal classi?cation schedule without width restriction needs a number n of pull-outs and thus logical tracks that is greater than the available number of physical tracks W . This schedule is in general not directly implementable. In this section we show how to construct optimal schedules under restricted width. From Observation 1 we know that it is enough to consider the case of a single input and a single outgoing train. As mentioned in Sect. 1, an example for this setting is given including the corresponding schedule and maximum number of cars that can be sorted for a number of given tracks. As mentioned before, Hansmann and Zimmermann independently obtain the same result . Their description also covers the case of an input with several cars being of the same type, i.e., the same integer may occur more than once in the input. Concluding Remarks
We have developed an e?cient encoding of freight train classi?cation schedules to present, analyze, and develop train classi?cation methods for real-world hump yards. This surprisingly simple though powerful encoding can be used to analyze the e?ciency of commonly used multistage methods, of which we proved the optimality of the simultaneous variant geometric sorting in terms of hump steps,considering presorted input. Future Work
It might be interesting to ?nd further optimization criteria for train classi?cation in the literature which are relevant in practice, in order to incorporate these objectives in the encoding scheme. There are further possibilities to specify output requirements, similar to the mentioned concept of blocks,and a straightforward question is how to derive optimal schedules in such settings. Finally, if the presented methods can be simulated to successfully work in practice, their implementation may accelerate the classi?cation process in many real-world hump yards.
35
附录A外文翻译－中文部分
附录A外文翻译－中文部分 货物列车多级分类方法
里克雅各，彼得马顿，延斯和马克纳克舍尔
摘要
本文建立了货运列车的分类方法是一致的编码。这种编码方案提出了一种有效的介绍和分类方法，我们成功申请，说明从理论的角度更多最相关的历史性成果分析的有力工具。我们准确地分析他们的表现和发展新的分类方法，利用固有的最优性条件的编码使用。最 后，我们推导最优算法和复杂性研究结果对于限制真实世界的设置。
一、简介
在现实世界中的铁路分类码,即将来临的火车是分解成单一的汽车,然后重新组装,形 成出站的列车。结果这个过程中往往构成的“瓶颈”货运, 但是价格不菲续约或重新设计分类码被设计来满足交通需求几十年前完全不同的今天。一个明显的方式性能要求的不断提高,现有的分类码是优化分类过程本身。为此我们重新分类方法的历史,深入的有效表示这些计划, 它允许他们稳定的介绍和分析。针对这一小说刻画了最优分类编码方案,并分析其潜在的算法问题。
一个完整的分类码如图1显示。它由一个编组站,因为在此进入的火车到达场,他们在那里排序,和一个出发,即将驶出的火车在是这里形成的。每个编组站都设有驼峰，在地面上解体，在这里,车辆在轨道上分类解体编组。这些码被称为驼峰码平码,对比分类的一般过程，它的整体分类训练过程看起来如下:驶入火车是集中在到达场，一组痕迹称为接受轨迹,从那里他们被移到驼峰的轨道。
在那里，火车列车断开和完整的列车被调机推送过了驼峰，发送这些列车通过一系列的交换场，分别指导每节列车到预先分类好的调车场线路。这个过程被称为推送过程。然后，实际排序过程，生成出站列车，这些车辆聚集起来准备离开调车场。对于实际的分类过程，基本上有两种调车码，这是典型的并行执行或可交替变换的操作模式：单级和多级排序。在单排序中,每个分类轨道通常对应一个共同的目的，如远程编组站。收集很多车辆在一个或几个轨道和编组成出发列车离开编组站，如果有的话。单级排序通常适用于大体积流量，如编组站之间的交通，以及创建列车的车辆都是任意的顺序。
直接到达其最终目的地的，使用多级排序。自从对于这种类型的出站列车的要求更为复杂，单级排序是这里不适用。在多级排序中，后进站的火车已经推送过了驼峰（小驼峰），调机可以在一个给定的轨道，多次拉回来到驼峰轨道上（拉出式操作）。这些列车，然后再推送过了驼峰，又使每节车厢都可以独立通过任何分类轨道。这个过程被称为重复解体，
36