# Optimization Method of Locomotive Working Diagram Layout

Authors: Yajing Zheng; Wenzhou Jin
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

Rational scheduling of locomotive paths (the locus of the locomotive point in the train working diagram) is an important step in drawing a locomotive working diagram by a computer. But there are some problems in this process, such as the computer usually drawing a locomotive path that overlaps with another locomotive path (in the circumstances, the actual users of the locomotive working diagrams often misread the locomotive planning). At present, there are many studies about assigning sets of locomotives to each train in a preplanned train schedule; in contrast, the studies of visualizing the locomotive planning are relatively rare. Through investigating the locomotive working diagram users, this paper points out that the layout of locomotive paths should put the distance between lines being as large as possible and should put the number of the intersection between lines being as few as possible as the optimization aim which is based to solve the problem of the lines overlap or the problem of the lines beyond the margins for drawing the locomotive paths. This paper also builds the optimization model of locomotive working diagram layout. Based on determining the position of locomotive paths which can be delineated, a genetic algorithm is used to solve the optimizing model of locomotive working diagram layout in this paper. An example of a train working diagram with 36 trains is given at the end of the paper, which indicates that the optimization model of locomotive working diagram layout can better solve the problem of locomotive planning visualization.


---

## Body

## 1. Introduction

Chinese railways now not only have the computational ability for automatic train scheduling [1–3], but have also made relatively good progress in automatically compilinglocomotive scheduling([4, 5]). Locomotive scheduling involves optimally assigning a set of locomotives to trains while simultaneously satisfying a variety of business constraints and minimizing the total scheduling cost [6–8]. It is usually composed of two-step process: ① assigning sets of locomotives to each train in a preplanned train schedule (it is also commonly referred to as thelocomotive planning problem, [9, 10]); ② visualizing the locomotive planning to thelocomotive working diagram (a graphic form of locomotive planning).Previous research in this field has focused mainly on step 1 (for example, Ghoseiri and Ghannadpour [11] consider the locomotive planning problem with homogeneous locomotives; Nourbakhsh and Ouyang [12] and Raviv and Kaspi [13] study the optimal fueling strategies for locomotives; Piu and Speranza [14] give a comprehensive review on the locomotive planning problem; Xu et al. [15, 16] make train timetabling and locomotive planning decisions simultaneously), whereas studies on step 2, which is just as important, remain fairly scarce.However, addressing the key theme of this paper visualizes the locomotive planning and depends essentially on optimizing the graphic representation of the locomotive planning. Although the problem resembles the train flow diagram (a train flow diagram is a direct graphic form which shows the category, path and number of all kinds of passenger, and freight train flow in railway network, which includes railway network and train flow line [17–19]), given the very different approach that needs to be taken in this case, available train flow diagram solutions cannot be adapted to the problem of locomotive planning visualization.Thelocomotive path, which includes thetrain paths and theconnection lines(a connection line means a locomotive from an inbound train to an outbound train at the same station in practice), is the locus of the locomotive point in the train working diagram. The difficulty in visualizing locomotive planning is that quantifying the layout of connection lines. Consequently, this paper proposes a method for automatically optimizing locomotive working diagrams based on a detailed investigation into the practices actually employed by those who use the locomotive working diagram. This method can contribute to making better and more systemic automatically generated the locomotive working diagram.


## 2. The Position of the Connection Lines

There are three drawing areas in the locomotive working diagram for positioning connection lines (as shown in Figure1): ① the top (hereinafter referred to as “upper section”); ② the bottom (hereinafter referred to as “lower section”); ③ the middle (hereinafter referred to as “middle section”). In reality, depending on the situation, areas called “middle section” in this paper may not exist at all or there may be several of them at one time. For simplicity and actuality, this paper assumes that there is only one middle section. In general, as shown in Figure 1, each section is equal in height (Δ in this paper indicates the height of each section), and the line position of each connection line is a series of equally spaced horizontal lines in each section. In this paper, each horizontal line, representing the line positions, is numbered 1,2… as shown in Figure 1. If R represents the distance between adjacent horizontal lines, then R=Δ/K+1 (where K in the formula is the maximum value of the horizontal lines’ number; this value is derived from the train schedule and the locomotive planning and is explained in detail in Section 3.2 of this paper).Figure 1
Line position of connection lines in the cyclic locomotive plan.Generally, a “complete” connection line consists of three segments (as shown in Figure2): ① the initial segment of the connection line is the left vertical line (hereinafter referred to as “LL”); ② the middle segment of the connection line is the horizontal line (hereinafter referred to as “ML”); ③ the end segment of the connection line is the right vertical line (hereinafter referred to as “RL”).Figure 2
The diagrams of the connection line.
(a) (b) (c) (d)The four types shown in Figure3 show all the possible types of a “complete” connection line. In general, upper sections only display the type shown in Figure 3(a), while lower sections only display the type shown in Figure 3(b). Middle sections may display any of the four types. In order to automatically draw the four types of connection lines according to the locomotive planning on the basic train diagram, the most efficient approach is to confirm a location of the connection lines as drawing the ML of the connection line on the smallest number line position which does not conflict with any ML. In this paper, the above method is referred to as the “smallest distribution” method. However, applying the smallest distribution method to generate locomotive working diagrams by some diagrams editing systems in practice frequently produces cases where the LL or the RL overlap during parallel operation at both ends of a station (as shown in Figure 3(a), two RLs overlap as trains are dispatched simultaneously from this station at each end of the station).Figure 3
Commonly seen problems and solutions in traditional locomotive working diagrams editing systems.
(a) (b) (c) (d)This situation will affect the way that locomotive working diagram users interpret the locomotive planning; therefore, to avoid this becoming a problem, overlapping LLs or RLs can be handled in the way illustrated in Figures3(b) and 3(c): ① Figure 3(b) swaps the position of the two lines representing the parallel operations and then adapts the other affected connection lines. ②Figure 3(c) adds a new line position, which is used to replace one of the connection lines in the parallel operation. The visual impact of these modifications on the locomotive diagram is clear: in Figure 3(b) the spacing between the MLs is larger, whereas in Figure 3(c), there are fewer crossover points between the connection lines. As such, there are two ways to solve the problem, in visualizing the locomotive planning, caused by parallel operations being conducted at both ends of the station. ① Maximize the spacing between each line position. ② Minimize the number of crossover points between connection lines. According to the data collected for this paper through surveys from the actual users of the locomotive working diagrams, the majority of respondents said that when there were fewer connection lines on the diagram, minimizing crossover points was more important than maximizing the space between lines, whereas the opposite was true when there were a large number of connection lines. Figure 3(d) is an optimized version of the diagram in Figure 3(a), where minimizing crossover points was more important than maximizing the space between lines. In addition, determining the number of the line positions before generating a planning diagram is a precondition to studying the optimization of visualizing the locomotive planning.Therefore, the issue of visualizing the locomotive planning discussed in this paper can be summarized as follows: assuming that the locomotive planning is known, when adding the necessary connection lines to the train diagram, it is necessary to avoid overlapping LLs and RLs due to parallel operations at both ends of a station. To this end, it is necessary to ensure maximum spacing between adjacent MLs and minimize the number of crossover points between connection lines. In order to give this problem a general nature, for the purposes of this study a real-life locomotive planning (results of a train schedule) was used, which means that it was not a cycle diagram.


## 3. Mathematical Modeling

### 3.1. Symbol Definition

To facilitate explanations, the count time (start and stop time of the train working diagram) of the locomotive planning in this paper was set to 0:00. The symbolφ represents sections where connection lines can be positioned in the locomotive working diagram. In this paper, the value of φ is 0, 1, and 2 corresponding to the upper section, the lower section, and the middle section, respectively (if there are two or more middle sections, the value can be further increased). Let Hφ be the number set of the connection lines in the range of φ in a certain locomotive working diagram; any “complete” connection line (h∈Hφ) may consist of two lines shown in Figure 4 (in this paper, this is referred to as the four “basic lines”). For example, the connection line shown in Figure 2(a) is composed of two basic lines from Figures 4(a) and 4(c).Figure 4
The basic lines of connection lines.
(a) (b) (c) (d)In general, if a connection line does not cross the count time 0:00, it consists of two basic lines in Figure4, and if a connection line crosses the count time 0:00, it is constituted by one basic line in Figure 4. For convenience, in this paper, all the connection lines across 0:00 will be completed as being formed of two basic lines (generally speaking, there are two ways of completion; each can be chosen arbitrarily), so that all the connection lines will contain the following three attributes: ①  tsh, time corresponding to LL or start time of connection line h, ②  teh, time corresponding to RL or end time of connection line h, and ③  sh representing the number of the line position of the connection line h. Variables ah, bh, ch, and dh are defined as 0-1: if the connection line h contains the types of line shown in Figure 4(a), ah=1. If the connection line h contains the types of line shown in Figure 4(b), bh=1. If the connection line h contains the types of line shown in Figure 4(c), ch=1. If the connection line h contains the types of line shown in Figure 4(d), dh=1. Take the connection line in Figure 2(a) as an example: ah=1, bh=0, ch=1, and dh=0.K φ is the set of numbered line positions within section φ, according to the numbering rules of this paper, which define kφ∈Kφ as offset multiplier relative to the horizontal line (the center of intermediate train distancing point).Variablepijφ is defined as 0-1 within section φ; if the connection line i and the connection line j have an overlap in time, apply 1; otherwise, apply 0.Variablemijφ is defined as 0-1; if the connection line i and the connection line j are all in the range of φ and tsj<tsi<tej, apply 1; otherwise, apply 0.Variablenijφ is defined as 0-1; if the connection line i and the connection line j are all in the range of φ and tsj<tei<tej, apply 1; otherwise, apply 0.Define 0-1 variableθkiφ; if the variable is 1, it means that within section φ, connection line i will select line position kφ. If the variable is 0, it means that connection line i will not select line position kφ. Then, sh clearly satisfies the relative formula sh=∑kkφ·θkhφ.Define the functiony=fx; when x is true, y=1, and when x is false, y=0. Table 1 summarizes the situation for all eight connection line crossover points.Table 1
Summary of connection lines and analysis of each type of connection lines crossover point.
Example diagram Constraint condition (a)  Whenφ=0 or φ=2: Ifai=1, aj=1, pijφ=1, mijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω1ijφ=ai⋅aj⋅pijφ⋅mijφ⋅fsi>sj=1, then the i and j have a crossover point.  (b)  Whenφ=2: Ifci=1, cj=1, pijφ=1 and nijφ=1, then i and j have a crossover point; i.e., ifω2ijφ=ci⋅cj⋅pijφ⋅nijφ⋅fsi>sj=1, then i and j have a crossover point;.  (c)  Whenφ=2: Ifbi=1, bj=1, pijφ=1, mijφ=1 and fsi<sj=1, then i and j have a crossover point; i.e., ifω3ijφ=bi⋅bj⋅pijφ⋅mijφ⋅fsi<sj=1, then i and j have a crossover point. Whenφ=1: Ifbi=1, bj=1, pijφ=1, mijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω3ijφ=bi⋅bj⋅pijφ⋅mijφ⋅fsi>sj=1, then i and j have a crossover point.  (d)  Whenφ=2: Ifdi=1, dj=1, pijφ=1, nijφ=1 and fsi<sj=1, then i and j have a crossover point; i.e., ifω4ijφ=di⋅dj⋅pijφ⋅nijφ⋅fsi<sj=1, then i and j have a crossover point. Whenφ=1: Ifdi=1, dj=1, pijφ=1, nijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω4ijφ=di⋅dj⋅pijφ⋅nijφ⋅fsi>sj=1, then i and j have a crossover point.  (e)  Whenφ=2: Ifai=1, bj=1, pijφ=1, mijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω5ijφ=ai⋅bj⋅pijφ⋅mijφ⋅fsi>sj=1, then i and j have a crossover point.  (f)  Whenφ=2: Ifbi=1, aj=1, pijφ=1, mijφ=1 and fsi<sj=1, then i and j have a crossover point; i.e., ifω6ijφ=bi⋅aj⋅pijφ⋅mijφ⋅fsi<sj=1, then i and j have a crossover point.  (g)  Whenφ=2: Ifci=1, dj=1, pijφ=1, nijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω7ijφ=ci⋅dj⋅pijφ⋅nijφ⋅fsi>sj=1, then i and j have a crossover point.  (h)  Whenφ=2: Ifdi=1, cj=1, pijφ=1, nijφ=1 and fsi<sj=1, then i and j have a crossover point; i.e., ifω8ijφ=di⋅cj⋅pijφ⋅nijφ⋅fsi<sj=1, then i and j have a crossover point.


### 3.2. Confirming the Line Positions

The premise for optimizing the layout of locomotive working diagrams is to confirm the line positions in each section, that is, to determine the largestkφ in the set Kφ. This can be done following the steps set out as follows.Step 1.
Letφ=0, θ2=0.Step 2.
Sort alltsh and teh within section φ in ascending order by time, forming sequence Ti; when the time is the same, in addition to tsh1=teh2, tsh1 should be ranked first, and in the other situations, the order can be determined randomly.Step 3.
Letθ1=0, scanning time sequence Ti sequentially; if tsh is scanned, θ1=θ1+1, θ2=max⁡θ1,θ2. If teh is scanned, θ1=θ1-1, θ2=max⁡θ1,θ2.Step 4.
φ = φ + 1; if the value of φ is larger than the number of the line positions on the locomotive working diagram, go to step 5. Otherwise, go to step 2.Step 5.
Construct the number setKφ of the line positions in the range of φ, in which max⁡kφ=θ2, kφ∈Kφ.At this point, the line positions of each drawing area have been determined, and that means the setKφ is known.


### 3.3. Model Construction and Solution

#### 3.3.1. Constraint Conditions

① One connection line can only select one line position:(1)∑kθkhφ=1,∀kφ∈Kφ,hφ∈Hφ② Connection lines cannot overlap(2)pijθkiφ+θkyφ≤1,∀kφ∈Kφ,hφ∈Hφ③ Whenφ=2, if two locomotives are engaged in parallel operations at both ends of a station, this is reflected in the locomotive working diagram; that is, the LL or RL of a certain connection line and the LL or RL of another connection line are at the same time, and it is obvious that the two vertical lines, which are at the same time, cannot overlap in the diagram.Parameteruijφ is defined as 0-1; if i≠j and tsi=tsj, apply 1; otherwise, apply 0. Define 0-1 parameter vijφ; if i≠j and tei=tej, apply 1; otherwise, apply 0. Parameter rijφ is defined as 0-1; if i≠j and tei=tsj, apply 1; otherwise, apply 0. There are four cases shown in Table 2.Table 2
Schematic representation of overlapping LL and RL in locomotive working diagram.
Example diagram Constraint condition (a)  Ifbi=1, aj=1 and uijφ=1, then i and j subject to si-sj≥1; i.e.,bi⋅aj⋅uijφ⋅si-sj≥bi⋅aj⋅uijφ.  (b)  Ifdi=1, aj=1 and rijφ=1, then i and j subject to si-sj≥1; i.e.,di⋅aj⋅rijφ⋅si-sj≥di⋅aj⋅rijφ.  (c)  Ifci=1, bj=1 and rijφ=1, then i and j subject to sj-si≥1; i.e.,ci⋅bj⋅rijφ⋅sj-si≥ci⋅bj⋅rijφ.  (d)  Ifdi=1, cj=1 and vijφ=1, then i and j subject to si-sj≥1; i.e.,di⋅cj⋅vijφ⋅si-sj≥di⋅cj⋅vijφ


#### 3.3.2. Objective Function

① Minimum number of connection line crossover points:(3)min⁡Z1=∑φ∑iφ∈Hφjφ∈Hφω1ijφ+ω2ijφ+ω3ijφ+ω4ijφ+ω5ijφ+ω6ijφ+ω7ijφ+ω8ijφ② To improve the visual aspect of locomotive working diagrams, connection lines should occupy the smaller delineable line positions as far as possible:(4)min⁡Z2=∑φ∑hφ∈Hφshφ


### 3.4. Model Solution

The model constructed above in this paper is a nonlinear pure-integer programming model with multiple objects. These two objective functions are incommensurable, which means they have different units and cannot be solved by linear weighting methods effectively. However, these two objective functions can be solved using a delaminating sequence method in order of priority: First, solve the single-object optimized model applying formula (3) as the objective function, and formulae (1) and (2) as constraint conditions. Then, under the conditions of the above calculation results, solve the single-object optimized model, with formula (4) as the objective function, and formulae (1) and (2) as constraint conditions.It is very difficult to obtain these solutions using this method with of-the-shelf commercially available software (such as Lingo), and even if this kind of software could produce an optimal solution, the computation time required to reach the solution would be too long to be practically viable (take the 4th section of this paper for example; the layout of the connection lines in the middle section was generated by Lingo, with Intel Core i3 CPU and 4G memory, and it still took 4 hours to reach the optimal solution). To this end, the genetic algorithm is used to solve the model in this paper. Although it is impossible to guarantee that the output will be the optimal solution, it is effective enough for practical purposes. The algorithm is described as follows.


#### 3.4.1. Chromosome Encoding and Initialization

Chromosome encoding uses digital string coding. In the drawing section, each chromosome represents one combination of all the selected line positions selected by connection lines. The number of chromosome genes is equal to the number of connection lines in the drawing area. The genes of each chromosome are sorted according to the given sequence of the connection line numbers, and each gene corresponds to the drawing area of the corresponding connecting line. For example, the chromosome “2, 1, 2” indicates that there are 3 connection lines, and the corresponding solution isθ2,1φ=1, θ1,2φ=1, θ2,3φ=1. It means that the connection line numbered 1 corresponds to the line position 2, the connection line numbered 2 corresponds to the line position 1, and the connection line numbered 3 corresponds to the line position 2.The integerpop_size is defined as the number of chromosomes in the population; at the beginning of the genetic algorithm, the chromosomes need to be initialized.Step 1.
Randomly generate an unmarked integerhxφ between 1 and hmaxφ.Step 2.
According to the smallest distribution method, draw the connection linehxφ to the smallest line position label that does not conflict with other connection lines. And the labeling value of the line position was filled in the corresponding position of the chromosome.Step 3.
Mark the integerhxφ.Step 4.
Verify if all integers in 1-100 are marked or not. If so, turn to Step 5; otherwise, turn to Step 1.Step 5.
The obtained chromosomes are tested and placed into the initial population if the constraints of Section2 model construction are satisfied. Otherwise, restart the first step to construct a new chromosome. When the initial population reaches the size of a chromosome, the initialization of the population is completed.When the initial population reachespop_size chromosomes, the population initialization stage is complete.


#### 3.4.2. Calculation of Chromosome Fitness

First, calculate the valueZ defined by the following formula for each chromosome, which reflects the pros and cons of the two objective functions of a certain chromosome:(5)Z=Z1+Z2MIn the formula,M is a sufficiently large real number, set at 10,000 in this paper.Then the chromosomes are sorted according to their value (ascending) to obtain the chromosomal sequenceV1,V2,…,Vpop_size. Then the order-based evaluation function is defined:(6)evalVi=0.5ii=1,2,…,pop_sizeIn the formula,i=1 means the chromosome is best, and i=pop_size means worst.


#### 3.4.3. Chromosome Selection Process

The chromosome selection process is based on its fitness; the greater the fitness of a chromosome, the greater the probability that it will be selected. The selection process steps are as follows.Step 1.
For each chromosomeVi, calculate the cumulative probability qi:(7)q0=0qi=∑j=1ievalVi,i=1,2,…,pop_sizeStep 2.
Generate a random numberr from the interval 0,qpop_size.Step 3.
Ifqi-1<r≤qi, select chromosome Vi as No. i.Step 4.
Repeat step 2 and step 3 for a total ofpop_size times to obtain pop_size replicated chromosomes.


#### 3.4.4. Chromosome Crossover Operation

DefinePc as the probability of a crossover operation, indicating an average of Pc·pop_size chromosome crossover operations in each population. The crossover operation uses a partial matching crossover method, so the chromosomes after crossover must be viable. Since chromosome genes are sorted according to the number of connection lines, crossover operations are performed as follows.Step 1.
Generate a random numberε1 between 0,1 from i=1 to pop_size repeatedly; if ε1<Pc, choose Vi as a parent.Step 2.
Pair the parentsV1′,V2′,V3′⋯ generated in Step 1 into groups randomly.Step 3.
Generate a random integerε2 between 1,hmaxφ randomly, then select a group of parent chromosomes that have not been selected in Step 2, and swap all the genes of these two chromosomes from ε2 to the end, as shown in the Figure 5.Figure 5
Chromosome crossover operation.If the generation of descendants is viable, they can replace the parent. Otherwise, keep the viable subject and regenerate a new random number and repeat the crossover operation until two viable descendants or a given number of cycles are used up. Only the viable descendant can replace the parent in the chromosome crossover operation.


#### 3.4.5. Chromosome Mutation Operation

DefinePm as the probability of mutation operation, which indicates that there is an average of Pm·pop_size chromosomes in each population mutating. Selecting the parent of a chromosome mutation is similar to parent selection in the crossover operation, and mutation is performed as follows.Step 1.
Generate two unequal random integersε3 and ε4 between 1,hmaxφ.Step 2.
Exchange the gene at the positionε3 with the gene at the position ε4 in the chromosome, as shown in Figure 6.Figure 6
Chromosome mutation.If the chromosome obtained after mutation is viable, the original chromosome will be replaced. Otherwise, repeat Step 1 and Step 2 until a viable chromosome mutation is achieved or the given number of cycles is used up.


## 3.1. Symbol Definition

To facilitate explanations, the count time (start and stop time of the train working diagram) of the locomotive planning in this paper was set to 0:00. The symbolφ represents sections where connection lines can be positioned in the locomotive working diagram. In this paper, the value of φ is 0, 1, and 2 corresponding to the upper section, the lower section, and the middle section, respectively (if there are two or more middle sections, the value can be further increased). Let Hφ be the number set of the connection lines in the range of φ in a certain locomotive working diagram; any “complete” connection line (h∈Hφ) may consist of two lines shown in Figure 4 (in this paper, this is referred to as the four “basic lines”). For example, the connection line shown in Figure 2(a) is composed of two basic lines from Figures 4(a) and 4(c).Figure 4
The basic lines of connection lines.
(a) (b) (c) (d)In general, if a connection line does not cross the count time 0:00, it consists of two basic lines in Figure4, and if a connection line crosses the count time 0:00, it is constituted by one basic line in Figure 4. For convenience, in this paper, all the connection lines across 0:00 will be completed as being formed of two basic lines (generally speaking, there are two ways of completion; each can be chosen arbitrarily), so that all the connection lines will contain the following three attributes: ①  tsh, time corresponding to LL or start time of connection line h, ②  teh, time corresponding to RL or end time of connection line h, and ③  sh representing the number of the line position of the connection line h. Variables ah, bh, ch, and dh are defined as 0-1: if the connection line h contains the types of line shown in Figure 4(a), ah=1. If the connection line h contains the types of line shown in Figure 4(b), bh=1. If the connection line h contains the types of line shown in Figure 4(c), ch=1. If the connection line h contains the types of line shown in Figure 4(d), dh=1. Take the connection line in Figure 2(a) as an example: ah=1, bh=0, ch=1, and dh=0.K φ is the set of numbered line positions within section φ, according to the numbering rules of this paper, which define kφ∈Kφ as offset multiplier relative to the horizontal line (the center of intermediate train distancing point).Variablepijφ is defined as 0-1 within section φ; if the connection line i and the connection line j have an overlap in time, apply 1; otherwise, apply 0.Variablemijφ is defined as 0-1; if the connection line i and the connection line j are all in the range of φ and tsj<tsi<tej, apply 1; otherwise, apply 0.Variablenijφ is defined as 0-1; if the connection line i and the connection line j are all in the range of φ and tsj<tei<tej, apply 1; otherwise, apply 0.Define 0-1 variableθkiφ; if the variable is 1, it means that within section φ, connection line i will select line position kφ. If the variable is 0, it means that connection line i will not select line position kφ. Then, sh clearly satisfies the relative formula sh=∑kkφ·θkhφ.Define the functiony=fx; when x is true, y=1, and when x is false, y=0. Table 1 summarizes the situation for all eight connection line crossover points.Table 1
Summary of connection lines and analysis of each type of connection lines crossover point.
Example diagram Constraint condition (a)  Whenφ=0 or φ=2: Ifai=1, aj=1, pijφ=1, mijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω1ijφ=ai⋅aj⋅pijφ⋅mijφ⋅fsi>sj=1, then the i and j have a crossover point.  (b)  Whenφ=2: Ifci=1, cj=1, pijφ=1 and nijφ=1, then i and j have a crossover point; i.e., ifω2ijφ=ci⋅cj⋅pijφ⋅nijφ⋅fsi>sj=1, then i and j have a crossover point;.  (c)  Whenφ=2: Ifbi=1, bj=1, pijφ=1, mijφ=1 and fsi<sj=1, then i and j have a crossover point; i.e., ifω3ijφ=bi⋅bj⋅pijφ⋅mijφ⋅fsi<sj=1, then i and j have a crossover point. Whenφ=1: Ifbi=1, bj=1, pijφ=1, mijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω3ijφ=bi⋅bj⋅pijφ⋅mijφ⋅fsi>sj=1, then i and j have a crossover point.  (d)  Whenφ=2: Ifdi=1, dj=1, pijφ=1, nijφ=1 and fsi<sj=1, then i and j have a crossover point; i.e., ifω4ijφ=di⋅dj⋅pijφ⋅nijφ⋅fsi<sj=1, then i and j have a crossover point. Whenφ=1: Ifdi=1, dj=1, pijφ=1, nijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω4ijφ=di⋅dj⋅pijφ⋅nijφ⋅fsi>sj=1, then i and j have a crossover point.  (e)  Whenφ=2: Ifai=1, bj=1, pijφ=1, mijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω5ijφ=ai⋅bj⋅pijφ⋅mijφ⋅fsi>sj=1, then i and j have a crossover point.  (f)  Whenφ=2: Ifbi=1, aj=1, pijφ=1, mijφ=1 and fsi<sj=1, then i and j have a crossover point; i.e., ifω6ijφ=bi⋅aj⋅pijφ⋅mijφ⋅fsi<sj=1, then i and j have a crossover point.  (g)  Whenφ=2: Ifci=1, dj=1, pijφ=1, nijφ=1 and fsi>sj=1, then i and j have a crossover point; i.e., ifω7ijφ=ci⋅dj⋅pijφ⋅nijφ⋅fsi>sj=1, then i and j have a crossover point.  (h)  Whenφ=2: Ifdi=1, cj=1, pijφ=1, nijφ=1 and fsi<sj=1, then i and j have a crossover point; i.e., ifω8ijφ=di⋅cj⋅pijφ⋅nijφ⋅fsi<sj=1, then i and j have a crossover point.


## 3.2. Confirming the Line Positions

The premise for optimizing the layout of locomotive working diagrams is to confirm the line positions in each section, that is, to determine the largestkφ in the set Kφ. This can be done following the steps set out as follows.Step 1.
Letφ=0, θ2=0.Step 2.
Sort alltsh and teh within section φ in ascending order by time, forming sequence Ti; when the time is the same, in addition to tsh1=teh2, tsh1 should be ranked first, and in the other situations, the order can be determined randomly.Step 3.
Letθ1=0, scanning time sequence Ti sequentially; if tsh is scanned, θ1=θ1+1, θ2=max⁡θ1,θ2. If teh is scanned, θ1=θ1-1, θ2=max⁡θ1,θ2.Step 4.
φ = φ + 1; if the value of φ is larger than the number of the line positions on the locomotive working diagram, go to step 5. Otherwise, go to step 2.Step 5.
Construct the number setKφ of the line positions in the range of φ, in which max⁡kφ=θ2, kφ∈Kφ.At this point, the line positions of each drawing area have been determined, and that means the setKφ is known.


## 3.3. Model Construction and Solution

### 3.3.1. Constraint Conditions

① One connection line can only select one line position:(1)∑kθkhφ=1,∀kφ∈Kφ,hφ∈Hφ② Connection lines cannot overlap(2)pijθkiφ+θkyφ≤1,∀kφ∈Kφ,hφ∈Hφ③ Whenφ=2, if two locomotives are engaged in parallel operations at both ends of a station, this is reflected in the locomotive working diagram; that is, the LL or RL of a certain connection line and the LL or RL of another connection line are at the same time, and it is obvious that the two vertical lines, which are at the same time, cannot overlap in the diagram.Parameteruijφ is defined as 0-1; if i≠j and tsi=tsj, apply 1; otherwise, apply 0. Define 0-1 parameter vijφ; if i≠j and tei=tej, apply 1; otherwise, apply 0. Parameter rijφ is defined as 0-1; if i≠j and tei=tsj, apply 1; otherwise, apply 0. There are four cases shown in Table 2.Table 2
Schematic representation of overlapping LL and RL in locomotive working diagram.
Example diagram Constraint condition (a)  Ifbi=1, aj=1 and uijφ=1, then i and j subject to si-sj≥1; i.e.,bi⋅aj⋅uijφ⋅si-sj≥bi⋅aj⋅uijφ.  (b)  Ifdi=1, aj=1 and rijφ=1, then i and j subject to si-sj≥1; i.e.,di⋅aj⋅rijφ⋅si-sj≥di⋅aj⋅rijφ.  (c)  Ifci=1, bj=1 and rijφ=1, then i and j subject to sj-si≥1; i.e.,ci⋅bj⋅rijφ⋅sj-si≥ci⋅bj⋅rijφ.  (d)  Ifdi=1, cj=1 and vijφ=1, then i and j subject to si-sj≥1; i.e.,di⋅cj⋅vijφ⋅si-sj≥di⋅cj⋅vijφ


### 3.3.2. Objective Function

① Minimum number of connection line crossover points:(3)min⁡Z1=∑φ∑iφ∈Hφjφ∈Hφω1ijφ+ω2ijφ+ω3ijφ+ω4ijφ+ω5ijφ+ω6ijφ+ω7ijφ+ω8ijφ② To improve the visual aspect of locomotive working diagrams, connection lines should occupy the smaller delineable line positions as far as possible:(4)min⁡Z2=∑φ∑hφ∈Hφshφ


## 3.3.1. Constraint Conditions

① One connection line can only select one line position:(1)∑kθkhφ=1,∀kφ∈Kφ,hφ∈Hφ② Connection lines cannot overlap(2)pijθkiφ+θkyφ≤1,∀kφ∈Kφ,hφ∈Hφ③ Whenφ=2, if two locomotives are engaged in parallel operations at both ends of a station, this is reflected in the locomotive working diagram; that is, the LL or RL of a certain connection line and the LL or RL of another connection line are at the same time, and it is obvious that the two vertical lines, which are at the same time, cannot overlap in the diagram.Parameteruijφ is defined as 0-1; if i≠j and tsi=tsj, apply 1; otherwise, apply 0. Define 0-1 parameter vijφ; if i≠j and tei=tej, apply 1; otherwise, apply 0. Parameter rijφ is defined as 0-1; if i≠j and tei=tsj, apply 1; otherwise, apply 0. There are four cases shown in Table 2.Table 2
Schematic representation of overlapping LL and RL in locomotive working diagram.
Example diagram Constraint condition (a)  Ifbi=1, aj=1 and uijφ=1, then i and j subject to si-sj≥1; i.e.,bi⋅aj⋅uijφ⋅si-sj≥bi⋅aj⋅uijφ.  (b)  Ifdi=1, aj=1 and rijφ=1, then i and j subject to si-sj≥1; i.e.,di⋅aj⋅rijφ⋅si-sj≥di⋅aj⋅rijφ.  (c)  Ifci=1, bj=1 and rijφ=1, then i and j subject to sj-si≥1; i.e.,ci⋅bj⋅rijφ⋅sj-si≥ci⋅bj⋅rijφ.  (d)  Ifdi=1, cj=1 and vijφ=1, then i and j subject to si-sj≥1; i.e.,di⋅cj⋅vijφ⋅si-sj≥di⋅cj⋅vijφ


## 3.3.2. Objective Function

① Minimum number of connection line crossover points:(3)min⁡Z1=∑φ∑iφ∈Hφjφ∈Hφω1ijφ+ω2ijφ+ω3ijφ+ω4ijφ+ω5ijφ+ω6ijφ+ω7ijφ+ω8ijφ② To improve the visual aspect of locomotive working diagrams, connection lines should occupy the smaller delineable line positions as far as possible:(4)min⁡Z2=∑φ∑hφ∈Hφshφ


## 3.4. Model Solution

The model constructed above in this paper is a nonlinear pure-integer programming model with multiple objects. These two objective functions are incommensurable, which means they have different units and cannot be solved by linear weighting methods effectively. However, these two objective functions can be solved using a delaminating sequence method in order of priority: First, solve the single-object optimized model applying formula (3) as the objective function, and formulae (1) and (2) as constraint conditions. Then, under the conditions of the above calculation results, solve the single-object optimized model, with formula (4) as the objective function, and formulae (1) and (2) as constraint conditions.It is very difficult to obtain these solutions using this method with of-the-shelf commercially available software (such as Lingo), and even if this kind of software could produce an optimal solution, the computation time required to reach the solution would be too long to be practically viable (take the 4th section of this paper for example; the layout of the connection lines in the middle section was generated by Lingo, with Intel Core i3 CPU and 4G memory, and it still took 4 hours to reach the optimal solution). To this end, the genetic algorithm is used to solve the model in this paper. Although it is impossible to guarantee that the output will be the optimal solution, it is effective enough for practical purposes. The algorithm is described as follows.


### 3.4.1. Chromosome Encoding and Initialization

Chromosome encoding uses digital string coding. In the drawing section, each chromosome represents one combination of all the selected line positions selected by connection lines. The number of chromosome genes is equal to the number of connection lines in the drawing area. The genes of each chromosome are sorted according to the given sequence of the connection line numbers, and each gene corresponds to the drawing area of the corresponding connecting line. For example, the chromosome “2, 1, 2” indicates that there are 3 connection lines, and the corresponding solution isθ2,1φ=1, θ1,2φ=1, θ2,3φ=1. It means that the connection line numbered 1 corresponds to the line position 2, the connection line numbered 2 corresponds to the line position 1, and the connection line numbered 3 corresponds to the line position 2.The integerpop_size is defined as the number of chromosomes in the population; at the beginning of the genetic algorithm, the chromosomes need to be initialized.Step 1.
Randomly generate an unmarked integerhxφ between 1 and hmaxφ.Step 2.
According to the smallest distribution method, draw the connection linehxφ to the smallest line position label that does not conflict with other connection lines. And the labeling value of the line position was filled in the corresponding position of the chromosome.Step 3.
Mark the integerhxφ.Step 4.
Verify if all integers in 1-100 are marked or not. If so, turn to Step 5; otherwise, turn to Step 1.Step 5.
The obtained chromosomes are tested and placed into the initial population if the constraints of Section2 model construction are satisfied. Otherwise, restart the first step to construct a new chromosome. When the initial population reaches the size of a chromosome, the initialization of the population is completed.When the initial population reachespop_size chromosomes, the population initialization stage is complete.


### 3.4.2. Calculation of Chromosome Fitness

First, calculate the valueZ defined by the following formula for each chromosome, which reflects the pros and cons of the two objective functions of a certain chromosome:(5)Z=Z1+Z2MIn the formula,M is a sufficiently large real number, set at 10,000 in this paper.Then the chromosomes are sorted according to their value (ascending) to obtain the chromosomal sequenceV1,V2,…,Vpop_size. Then the order-based evaluation function is defined:(6)evalVi=0.5ii=1,2,…,pop_sizeIn the formula,i=1 means the chromosome is best, and i=pop_size means worst.


### 3.4.3. Chromosome Selection Process

The chromosome selection process is based on its fitness; the greater the fitness of a chromosome, the greater the probability that it will be selected. The selection process steps are as follows.Step 1.
For each chromosomeVi, calculate the cumulative probability qi:(7)q0=0qi=∑j=1ievalVi,i=1,2,…,pop_sizeStep 2.
Generate a random numberr from the interval 0,qpop_size.Step 3.
Ifqi-1<r≤qi, select chromosome Vi as No. i.Step 4.
Repeat step 2 and step 3 for a total ofpop_size times to obtain pop_size replicated chromosomes.


### 3.4.4. Chromosome Crossover Operation

DefinePc as the probability of a crossover operation, indicating an average of Pc·pop_size chromosome crossover operations in each population. The crossover operation uses a partial matching crossover method, so the chromosomes after crossover must be viable. Since chromosome genes are sorted according to the number of connection lines, crossover operations are performed as follows.Step 1.
Generate a random numberε1 between 0,1 from i=1 to pop_size repeatedly; if ε1<Pc, choose Vi as a parent.Step 2.
Pair the parentsV1′,V2′,V3′⋯ generated in Step 1 into groups randomly.Step 3.
Generate a random integerε2 between 1,hmaxφ randomly, then select a group of parent chromosomes that have not been selected in Step 2, and swap all the genes of these two chromosomes from ε2 to the end, as shown in the Figure 5.Figure 5
Chromosome crossover operation.If the generation of descendants is viable, they can replace the parent. Otherwise, keep the viable subject and regenerate a new random number and repeat the crossover operation until two viable descendants or a given number of cycles are used up. Only the viable descendant can replace the parent in the chromosome crossover operation.


### 3.4.5. Chromosome Mutation Operation

DefinePm as the probability of mutation operation, which indicates that there is an average of Pm·pop_size chromosomes in each population mutating. Selecting the parent of a chromosome mutation is similar to parent selection in the crossover operation, and mutation is performed as follows.Step 1.
Generate two unequal random integersε3 and ε4 between 1,hmaxφ.Step 2.
Exchange the gene at the positionε3 with the gene at the position ε4 in the chromosome, as shown in Figure 6.Figure 6
Chromosome mutation.If the chromosome obtained after mutation is viable, the original chromosome will be replaced. Otherwise, repeat Step 1 and Step 2 until a viable chromosome mutation is achieved or the given number of cycles is used up.


## 3.4.1. Chromosome Encoding and Initialization

Chromosome encoding uses digital string coding. In the drawing section, each chromosome represents one combination of all the selected line positions selected by connection lines. The number of chromosome genes is equal to the number of connection lines in the drawing area. The genes of each chromosome are sorted according to the given sequence of the connection line numbers, and each gene corresponds to the drawing area of the corresponding connecting line. For example, the chromosome “2, 1, 2” indicates that there are 3 connection lines, and the corresponding solution isθ2,1φ=1, θ1,2φ=1, θ2,3φ=1. It means that the connection line numbered 1 corresponds to the line position 2, the connection line numbered 2 corresponds to the line position 1, and the connection line numbered 3 corresponds to the line position 2.The integerpop_size is defined as the number of chromosomes in the population; at the beginning of the genetic algorithm, the chromosomes need to be initialized.Step 1.
Randomly generate an unmarked integerhxφ between 1 and hmaxφ.Step 2.
According to the smallest distribution method, draw the connection linehxφ to the smallest line position label that does not conflict with other connection lines. And the labeling value of the line position was filled in the corresponding position of the chromosome.Step 3.
Mark the integerhxφ.Step 4.
Verify if all integers in 1-100 are marked or not. If so, turn to Step 5; otherwise, turn to Step 1.Step 5.
The obtained chromosomes are tested and placed into the initial population if the constraints of Section2 model construction are satisfied. Otherwise, restart the first step to construct a new chromosome. When the initial population reaches the size of a chromosome, the initialization of the population is completed.When the initial population reachespop_size chromosomes, the population initialization stage is complete.


## 3.4.2. Calculation of Chromosome Fitness

First, calculate the valueZ defined by the following formula for each chromosome, which reflects the pros and cons of the two objective functions of a certain chromosome:(5)Z=Z1+Z2MIn the formula,M is a sufficiently large real number, set at 10,000 in this paper.Then the chromosomes are sorted according to their value (ascending) to obtain the chromosomal sequenceV1,V2,…,Vpop_size. Then the order-based evaluation function is defined:(6)evalVi=0.5ii=1,2,…,pop_sizeIn the formula,i=1 means the chromosome is best, and i=pop_size means worst.


## 3.4.3. Chromosome Selection Process

The chromosome selection process is based on its fitness; the greater the fitness of a chromosome, the greater the probability that it will be selected. The selection process steps are as follows.Step 1.
For each chromosomeVi, calculate the cumulative probability qi:(7)q0=0qi=∑j=1ievalVi,i=1,2,…,pop_sizeStep 2.
Generate a random numberr from the interval 0,qpop_size.Step 3.
Ifqi-1<r≤qi, select chromosome Vi as No. i.Step 4.
Repeat step 2 and step 3 for a total ofpop_size times to obtain pop_size replicated chromosomes.


## 3.4.4. Chromosome Crossover Operation

DefinePc as the probability of a crossover operation, indicating an average of Pc·pop_size chromosome crossover operations in each population. The crossover operation uses a partial matching crossover method, so the chromosomes after crossover must be viable. Since chromosome genes are sorted according to the number of connection lines, crossover operations are performed as follows.Step 1.
Generate a random numberε1 between 0,1 from i=1 to pop_size repeatedly; if ε1<Pc, choose Vi as a parent.Step 2.
Pair the parentsV1′,V2′,V3′⋯ generated in Step 1 into groups randomly.Step 3.
Generate a random integerε2 between 1,hmaxφ randomly, then select a group of parent chromosomes that have not been selected in Step 2, and swap all the genes of these two chromosomes from ε2 to the end, as shown in the Figure 5.Figure 5
Chromosome crossover operation.If the generation of descendants is viable, they can replace the parent. Otherwise, keep the viable subject and regenerate a new random number and repeat the crossover operation until two viable descendants or a given number of cycles are used up. Only the viable descendant can replace the parent in the chromosome crossover operation.


## 3.4.5. Chromosome Mutation Operation

DefinePm as the probability of mutation operation, which indicates that there is an average of Pm·pop_size chromosomes in each population mutating. Selecting the parent of a chromosome mutation is similar to parent selection in the crossover operation, and mutation is performed as follows.Step 1.
Generate two unequal random integersε3 and ε4 between 1,hmaxφ.Step 2.
Exchange the gene at the positionε3 with the gene at the position ε4 in the chromosome, as shown in Figure 6.Figure 6
Chromosome mutation.If the chromosome obtained after mutation is viable, the original chromosome will be replaced. Otherwise, repeat Step 1 and Step 2 until a viable chromosome mutation is achieved or the given number of cycles is used up.


## 4. Examples

Figure7 shows a locomotive working diagram corresponding to a certain train operations diagram, which uses the smallest distribution method to draw the connection lines, and there is an overlap of two RLs caused by parallel operations in an intermediate station. As a comparison, the author used the method in this paper to optimize the layout of the locomotive working diagram shown in Figure 7.Figure 7
Locomotive working diagram generated using the smallest distribution method.When the size of the population is 30, the probability of crossover (Pc) is 0.3, the probability of mutation (Pm) is 0.2, and the number of random models is 1000, and the system calculates three traceable areas separately on a computer which has Intel Core i3 CPU and 4G memory. The middle area takes the longest time, about 1 minute, to get the best chromosome in this area (6, 5, 4, 1, 3, 2, 2, 6, 3, 5, 2, 1, 3, 1, 3, 4, 1, 5), and the target value of this chromosome is 24.0057, which means that the number of crossover points between connection lines in the optimal plan in the middle section is 24. According to the three chromosomes obtained, the locomotive turnover diagram as shown in Figure 8 can be obtained.Figure 8
The locomotive operations diagram drawn by the method of this paper.In the locomotive working diagram generated using the method in this paper, the number of crossover points between the connection lines is 42, 5 less than the number of crossover points in Figure7 which was drawn manually. The displacement per connection line is 9mm, 2mm more than in Figure 7 (the height of the middle section in the original diagram was 63mm). With regard to the visualization of these examples, the locomotive working diagram generated using the method presented in this paper is clearer and easier to understand and is more relevant and more legible for the purposes of front line staff.


## 5. Conclusions

Up until now, there had been little research into the visual representation of locomotive working diagrams. This paper proposes an improved and more systematic planning method to solve some of the problems encountered with computer-generated plans, such as lack of capacity or overlapping of connection lines in locomotive working diagrams, and it also dramatically improves the legibility of locomotive working diagrams. In addition, by adjusting the model slightly, the proposed method could also be applied for other purposes, such as deadhead or light travel, indicating that this method can be very versatile.



---

*Source: 1315638-2019-05-02.xml*