Model and algorithm of wagon-flow allocating in marshalling station based on sequence theory

Abstract

The propose of this paper is building the flow shop model with full-loaded constraints and maximum wagons within the stage. Based on sequence theory, technical operations of marshalling station are described as process of flow shop. By definition of key trains, the adjustment of the classification schedule of inbound trains is attributed to the adjustment of key trains for reducing invalid solution. Based on the LS rules to construct an initial solution, tabu search algorithm (TS) dynamically adjusts taboo step, and build a network model of static wagon-flow allocation for the objective function, to ensure the feasibility of solutions. Finally, the example demonstrates the effectiveness of the algorithm, and differences between full-loaded and full-cars constrains.

Keywords

Marshaling station wagon-flow allocating sequence theory taboo search full-loaded

1. Introduction

Marshaling station is an important production unit of railway transportation, whose intelligent degree of dispatching command directly affects the development level of railway modernization. As the theoretical vital basis for intelligent dispatching, auxiliary decision optimization theory for the stage plan must explore the internal mechanism of marshaling station operation organization, construct a practical decision optimization model and have a complete theoretical system with the guide of systematic methods. Therefore, the stage plan is organized scientifically instead of empirically, which can improve the level of decision, the quality of plans organization, and the efficiency of transportation. Furthermore, scientific plans help with getting rid of manual operation and laying reliable theoretical foundation for dispatching intelligence of marshaling station.

Assignment problem, core of the phase plan aided decision optimization theory, has become the focus of the research on phase plan optimization recent years, among which scholars have done a lot of useful work. Currently, the researches on wagon-flow allocating mostly concentrate on two aspects: theory and solution.

The specific contributions of this paper include:

A literature survey about various existing distribution problems, analyzing the status of problems.

Based on the sorting theory, the train’s operation flow in marshaling station is analyzed, and a flow-time operation model of flow distribution problem is constructed.

A tabu search algorithm based on reducing the combination of comprehension sequences is proposed.

Effectiveness analysis and algorithm evaluation of the proposed algorithm.

The paper is organized as follows: Section 1 briefly introduces the wagon-flow allocating in marshaling station as well as the significance of the study. Section 2 briefly introduces the relater work. Studies on the process analysis of flow allocation and the operation process of marshaling station, a flow shop model based on the sequencing theory to solve the flow assignment problem is proposed in Section 3. Section 4 explains the model establishment. Section 5 introduces the essence of static wagon-flow allocation, which is the computing method of objective function. Section 6 puts forward the concept of key train and employs the Tabu Search Algorithm as basis to solve the assignment problem. Section 7 introduces the solving steps of Tabu Search Algorithm. In order to testify the effectiveness of the model and algorithm, a numerical example using the algorithm is presented in Section 8. Finally, Section 9 summarizes the conclusion.

2. Related work

Wang Ciguang [1, 2] firstly decomposed assignment problem into dynamic wagon-flow allocation and static wagon-flow allocation, putting forward new idea to solve the problem. Next Zhao Jun [3, 4] applied plenty of optimization algorithms based on the new idea, which greatly improved the efficiency of solving assignment problem. Jing Yun [5] cited uncertainty to dynamic wagon-flow allocation stage, expanding the application scale of assignment problem. Xue Feng [6] made use of large scale system theory to research on the cooperative relationship among the solutions. In recent years, much attention has been paid to the assignment problems under the condition of uncertainty due to the development of the uncertainty theory. Literature [7] put forward the uncertainty of technical operation; and literature [8] believed that the uncertainty comes from changes of break-up operation time and evaluates itquantitatively.

In the respect of solution and application, He Shiwei [9] made use of sequencing theory as well as Wang Minghui [10] made use of neighborhood adjustment for Longitudinal Marshalling Stations. Niu Huiming [11] took capacity constraints of each subsystem into consideration for the Bidirectional Marshalling Stations. Peng Qiyuang [12] researched on the assignment problem which existed in the stage plans. Li Wenquan [13], Xu Jie [14] and Wang Shidong [15] studied the wagon-flow by linking up the locomotives using plans as a thread and got the wagon-flow allocation plans.

In brief, the researches discussed had put forward many valuable theory and methods to get the wagon-flow allocation plans. Firstly, they pointed out how to transfer the wagon-flow allocation problem into an abstract mathematical problem. The related work decomposed the problem into static allocation and dynamic allocation two stages and gradually combines theories such as fuzzy theory, large scale system theory, and sequencing theory to improve the study. Secondly, the researchers made a targeted study of wagon-flow allocation in special marshaling stations, which expanded the application and practicability of wagon-flow allocation. However, there is few papers that research the wagon-flow allocation compressively and systematically. Especially, the uncertainty theory is increasingly developed and urgent to be taken into consideration. But the research on uncertainty and fuzzy theory has not been enough.

3. Process analysis of flow allocation

3.1. Settlement for assignment problem

As the main content in stage plans for marshalling station, settlements for assignment problem can be classified into brunch optimization and integrated optimization:

Type one is brunch optimization. The assignment process is divided into static and dynamic assignment stages. First, determine the reasonable uncoupling order throng dynamic wagon-flow allocation. Next composition of a dispatched trains as well as its sourcing wagons are fixed by static wagon-flow allocation.

Static wagon-flow allocation. Literature [1] transforms static wagon-flow allocation into transportation problem under the given uncoupling order, which can be solved by scheduling method in table. Literature [16] further turns the problem into network model, which can be solved by maximum flow algorithm.

Dynamic wagon-flow allocation. Literature [2] builds a scheme tree and applies backtracking algorithm to solve the problem of dynamic wagon-flow allocation. Literature [3] shrinks the adjustment scale of trains by defining the relevant train and the solution is solved by the local neighborhood search algorithm. Literature [5] takes the uncertainty of the time into consideration and solve the assignment problem throng the establishment of virtual yard, making use of ant colony algorithm.

Jugging form the findings above, the essence of static wagon-flow allocation is the solution of the objective function for assignment problem, which is relatively mature with tiny differences in complexity among different algorithms. While dynamic allocation can be regarded as an assignment problem with simplified function or slack constraints, which is the preprocessing stage. The objective function of dynamic allocation is usually defined as the approximate equivalent function. For example, literature [2] makes use of scenario values to replace the objective function. Or some constraints are be slacked, such as relaxation of connect time constraints in literature [4], and relaxation of train formation direction constraints in literature [5]. However, the solution obtained by dynamic flow allocation may not be the optimization not even a feasible solution after examined by static flow allocation. As a result, it can fall into the situation where local optimal solution is regarded as global optimal solution when heuristic algorithms are used to solve massive assignment problem.

Type two is integrated optimization, which is the basic method to the assignment problem in stage plan. Literature [7 –13] are put forward base on the idea. The method first fixes the uncoupling order, allocate wagon flow statically according the order, and find the optimization throng repeated iteration finally. Due to the complexity of static wagon-flow allocation, it’s unreasonable to allocate the flow for each order using the method. Therefore, it is necessary to restrict the uncoupling order according to realistic conditions and shrink the search space in order to improve efficiency. To achieve the goal, literature [3] defines waiting set and literature [5] comes up with relevant train.

This paper makes use of sequencing theory to reconstruct the optimization model of marshaling station dispatch in the framework of integrated optimization, and refers to the neighborhood thought in literature [7] and sorting thought in literature [8] to the solve the assignment problem under the uncertainty time of uncoupling and marshalling.

3.2. Operation process of marshalling station

The arrival trains must go through several segments, including arrival operation, arrival technical operation, break-up operation, marshalling operation, pull-out operation and departure technical operation, which is a production process. Each job has a set of identical parallel machines available, and the vehicle queuing in the whole process is serial and impassable as Fig. 1

Fig.1

A schematic layout of a hump yard and activities performed on each car passing through the yard.

As the first stage of technical operation in marshalling station, declassification system is composed of meeting operation, arrival operation and break-up operation. And train is divided into vehicles in the process of break-up operation. In declassification system, the capability of arrival operation and arrival technical operation is relatively abundant, and the job can be arranged easily. While restricted by humps and locomotives, the capacity of break-up operation is strain, which causes reasonable uncoupling order becomes the key factor to guarantee the operation in declassification system conducted smoothly.

As the second stage, marshaling and departure system includes marshaling operation, pull-out operation and departure operation, and vehicles are combined into trains during the process. The capability of pull-out operation and departure operation is relatively abundant, while capacity of marshaling operation is strain. Therefore, reasonable arrangement of marshaling order is vital for the smooth production in marshaling and departure system. Since the vehicles coming into classification yard after the first stage act as the “raw materials” for the second stage, it is necessary to unify operation sequence of the two stages. This paper constructs flow shop model based on sequencing theory.

4. Model establishment

4.1. Variable declaration

I represents the set of all arrival trains at this stage; n denotes the number of arrival trains; J represents the set of all departure trains at this stage; m denotes the number of departure trains; $t_{i}^{d}$ represents the arrival time of train I_i; $t_{j}^{f}$ denotes the departure time of train J_j; $t_{i}^{dj}$ represents the arrival technical operation time of train I_i; $t_{j}^{fj}$ denotes the departure technical operation time of train J_j; $t_{i}^{jt}$ denotes the break-up time of train I_i; $t_{j}^{bz}$ represents the marshalling time of train J_j; $t_{i}^{b}$ denotes the time when breaking up begins of train I_i; $t_{j}^{c}$ denotes the time when marshalling begins of train J_j. π (i) represents an array of arrival trains I; π (j) denotes an array of departure trains J; O_ij is a Boolean variable which indicates whether there is a continuation relationship between train I_i and train J_j, and if there is continuation relationship, O_ij = 1, and if not, O_ij = 0; Vector $I_{i}^{k} (g, l, p)$ represents the information of k in I_i, among which carrying capacity is $g_{i}^{k}$ , converted length is $l_{i}^{k}$ , group number is $p_{i}^{k}$ ; |I_i| represents the number of vehicles of I_i; the lower bound of weight constraint of J_j is $g_{j}^{min}$ while upper bound is $g_{j}^{max}$ ; the lower bound of length constraint is $l_{j}^{min}$ , while upper bound is $l_{j}^{max}$ ; Destination constraint is p_j; P represents the set of the destinations; $J_{j}^{p}$ denotes the group number contained in J_j; x_ij represents the number of vehicles that from I_i to J_j; $x_{ik}^{j}$ represents whether the vehicle k of train i is allocated to train j. If it is allocated to train j, the value is 1; and if not, the value is 0.

4.2. Model establishment

Assignment model is set in order to get to maximum number of departure trains in the stage based on the technical operation standards of thestation under the condition that trains are full loaded, on time and don’t break the rules of mars-haling. $Z = max \sum_{i = 1}^{n} \sum_{j = 1}^{m} x_{ij}$ (1) $(t_{π (i)}^{b} + t_{π (i)}) O_{ij} \leq t_{π (i)}^{c} - t_{π (i)}$ (2)

$\begin{matrix} t_{i}^{b} & = & max (t_{π (i)}^{d} + t_{π (i)}^{dj}, t_{π (i) - 1}^{d} \\ + t_{π (i) - 1}^{dj} + t_{π (i) - 1}^{jt}), \forall i \in (0, n) \end{matrix}$ (3)

$\begin{matrix} t_{j}^{c} & = & min (t_{π (i)}^{f} - t_{π (i)}^{fj}, t_{π (i) - 1}^{f} \\ - t_{π (i) - 1}^{fj} - t_{π (i) - 1}^{bz}), \forall j \in (1, m) \end{matrix}$ (4) ${\begin{matrix} \sum_{i \in I} \sum_{k \in K} \sum_{p \in p_{j}} I_{i}^{k} (g, p) x_{ik}^{j} - g_{j}^{min} ⩾ 0 \\ \sum_{i \in I} \sum_{k \in K} \sum_{p \in p_{j}} I_{i}^{k} (g, p) x_{ik}^{j} - g_{j}^{max} \leq 0 \end{matrix}, \forall j \in J$ (5) ${\begin{array}{l} \sum_{i \in I} \sum_{k \in K} \sum_{p \in p_{j}} I_{i}^{k} (l, p) x_{i k}^{j} - l_{j}^{\min} ⩾ 0, \forall j \in J \\ \sum_{i \in I} \sum_{k \in K} \sum_{p \in p_{j}} I_{i}^{k} (l, p) x_{i k}^{j} - l_{j}^{\max} \leq 0 \end{array}$ (6) $J_{j}^{p} = p_{j}, \forall j \in (1, m)$ (7)

Formula 2 represents the process constraint, which means that only when break-up operation is finished, can marshalling operation begin. If the departure train need the vehicles that come from the arrival trains, they must obey the formula. For any given uncoupling order of a train, its connection matrix O can be obtained by the formula as well.

Formula 3 represents the break-up time for I_i of given π (i). For operation of single rolling on double pushing track, when a yard engine is breaking up a train, another is preparing for the pushing to the peak. Hence the break-up time of I_i is regarded as decomposition time of train, which is equal to single rolling on single pushing track. As for π (j), formula 4 denotes the beginning time of marshalling time for J_j.

Formula 5 represents the weight constraint for and formula 6 denotes the length constraint, neither of which is satisfied means that the train is full axis. Under Axle train can be fixed by adjusting the lower bound of full axis. So, all the departure trains should satisfy with the lower bound of full axis.

Formula 7 represents that the vehicles marshalled in departure trains must meet with the formation plan.

4.3. Model analysis

Departure trains can only depart form marshalling station when meet with all the constraints including full axis, on time and fitting in with the formation plan, which can be classified into continuous time constraint and formation constraint.

Continuous time constraint means that the vehicles of departure train must go through the production process in marshalling station. It usually divide the whole stage into several time segments in order to meet with the constraint [3]. For every arrival train I_i, there is a 0-1 variable, which denotes whether the train is broken up in this segment. With the citing of uncertain information, the segments become more intense and complexity of algorism is higher. Guided by sequencing theory, this paper first fixes the uncoupling order and then gets the time table when the break-up operation begins and ends according the order in order to calculating the continuation time of traffic flow.

Type two is the constraint of marshalling formation. Full axis is required with the condition that formation plans are satisfied in order to make full use of the lines capacity. Full axis includes full weight and full length two parts, and meeting either of conditions is acceptable. The wagon-flow allocation plan based on full axis constraint is in line with the local fact situation with large amount of calculation. To reduce calculation load, the paper fixes x_ij first, and selects the vehicles of train according to chronological order that are submitted to the classification yard, that is: $\sum_{k = 1}^{x_{ij}} x_{ik}^{j} = x_{ij}$ (8)

5. Static wagon-flow allocation

The essence of static wagon-flow allocation is the computing method of objective function. It will make the calculation more complexed that the objective function serves as the evaluation for assignment problem, which also guarantees the feasibility of the solution.

5.1. Construction of network model

The evaluation function is used to test the values of objective function, that is whether the uncoupling order is rational should be test by the evaluation function. This paper calculates the objective function of assignment problem based on wagon-flow allocation network model which is constructed in literature [2]. The schematic diagram of Static wagon-flow allocation network model as Fig. 2.

Fig.2

Static wagon-flow allocation network model.

Capacity of arc in the network is denoted as u; flow is denoted as v, among which u_{SI
_i} and v_{SI
_i} represent the capacity and flow of arc between virtual starting point and single group respectively; u_{I
_i
s
_i} and v_{I
_i
s
_i} represent the capacity and flow of arc between single group and combined group respectively; u_{s
_i
t
_j} and v_{s
_i
t
_j} represent the capacity and flow of arc between combined group and the single departure group respectively; u_{t
_j
J
_j} and v_{s
_i
J
_j} represents the capacity and flow of arc between single departure group and the departure train respectively; u_{J
_j
T} and v_{J
_j
T} represents the capacity and flow of arc between departure train and virtual end-point.

Some of the departure trains includes only one group while some includes multiple groups, where the group means the vehicles that have the same destination or go through the same boundary station.

If represents all the groups to the same destination, the group number is arranged in order from near to far: $P^{'} \in (P_{1}^{'} ≺ P_{2}^{'} ≺ P_{3}^{'} ≺ \dots)$ (9)

$J_{j}^{p} \in p^{'}, \forall j \in J$ (10)

Formula 10 indicates that the groups involved in J_j have the same destination. In order to reduce the resorting operation on the way as possible, the group number in P′ will be arrayed inversely from the top to bottom. Therefore, when searched in the augmented path from top to bottom, nodes ranked in the top will give priority to enter the augmented path, which guarantees the trains in higher level has source of vehicles first.

5.2. Calculation method of full axis

Information matrix of I_i is denoted as, $I_{i} (g, l, q) = (\begin{matrix} g_{i}^{1}, & g_{i}^{2}, & \dots, & g_{i}^{k}, & \dots, & g_{i}^{| I_{i} |} \\ l_{i}^{1}, & l_{i}^{2}, & \dots, & l_{i}^{k}, & \dots, & l_{i}^{| I_{i} |} \\ p_{i}^{1}, & p_{i}^{2}, & \dots, & p_{i}^{k}, & \dots, & p_{i}^{| I_{i} |} \end{matrix})$ (11)

I_i was divided into single group of vehicles, and according the order that is submitted into classification yard, information matrix $S_{π (i)}^{p}$ is denoted as, $I_{i} (g, l, q) = (\begin{matrix} g_{i}^{1}, & g_{i}^{2}, & \dots, & g_{i}^{k}, & \dots, & g_{i}^{| I_{i} |} \\ l_{i}^{1}, & l_{i}^{2}, & \dots, & l_{i}^{k}, & \dots, & l_{i}^{| I_{i} |} \\ p_{i}^{1}, & p_{i}^{2}, & \dots, & p_{i}^{k}, & \dots, & p_{i}^{| I_{i} |} \end{matrix})$ (12)

The single groups that have the same degree are combined [2], and information matrix S_p represents the information of combined group p, which is sorted by the uncoupling order. $S^{p} = (S_{π (1)}^{p}, S_{π (2)}^{p}, \dots, S_{π (i)}^{p}, \dots)$ (13)

Due to the capacity constrain of network model is the number of vehicles, there is need to transform it into constraints of weight and length as follows, $v_{J_{j} T}^{gl} \leq u_{J_{j} T}^{gl}$ (14)

Among the formula, $u_{J_{j} T}^{gl} = (g_{J_{j} T}^{max}, l_{J_{j} T}^{max})^{'}$ (15) $v_{J_{j} T} = (g_{J_{j} T}, l_{J_{j} T})^{'} = S^{p} \cdot E_{gl}$ (16) $E_{gl} = {(1, 1, \dots, x_{ij}, 0, \dots, | S^{p} |)}^{'}$ (17)

When arcs related to arrival trains are calculated, the constraint is the number of vehicles to make sure that the number of arrival vehicles is equal to that of departure vehicles. While when arcs related to departure trains are calculated, the constraint is full axis.

5.3. Calculation steps

Step 1. Acquire information of I_i, and generate the information matrix I (g, l, q) of I_i;

Step 2. Divide I_i into several single groups according the number, whose information matrix is $S_{π (i)}^{p}$ ;

Step 3. Simplify the network according the method in literature [2], and the matrix of combined groups is S^p. The information of single group should be reserved in order to check the specific source of vehicles.

Step 4. Search the augmenting path matrix of the network from top to bottom and calculate the maximum flow by means of maximum flowalgorithm.

Step 5. Make use of formula 14 to exam the constraint of full axis. If it is not satisfied, the bound can be reduced by u_{J
_j
T}.

Step 6. Calculate the flow of the whole network v, and obtain the under-axis trains $J_{j}^{'}$ . Record the set $I_{i}^{j}$ of key trains. The flow chat of Static wagon-flow allocation algorithm flow as Fig. 3.

Fig.3

Static wagon-flow allocation algorithm flow.

6. Tabu search algorithm

The key to solve the assignment problem in marshalling station is how to reduce the uncoupling order combination according the realistic situation. This paper puts forward the concept of key train and employs the Tabu Search Algorithm (TS) as basis to solve the problem.

6.1. Key trains

Key train of under axis train $J_{j}^{'}$ refers to the arrival trains that can’t provide with vehicles to it needs due to the constraint of connect time for the given π (i) , π (j), which is denoted as $I_{i}^{j}$ . $I_{i}^{j} = {i | I_{i}^{p} \cup J_{j}^{p} \cup (1 - O_{ij}) \neq 0, \forall j \in J}$ (18)

As known in formula 18, $I_{i}^{j}$ is not unique in π (i), and whether $J_{j}^{'}$ can be full axis is closely relative to the uncoupling order of the key train in π (i).

6.2. Neighborhood structures

Tabu search algorism usually acquires its new solution by means of 2-opt exchange randomly. However, it will lead to a waste of the yard engines, which also reduce the efficiency of the hump. As a result, the algorism acquires new solution through driving forward the key procedure in order to guarantee the departure trains full axis as possible. $ψ (I_{i}^{j})$ is denoted as driving forward the uncoupling order of $I_{i}^{j}$ ,that is $I_{π (i) - 1} \leftarrow I_{π (i)}^{j}$ (19)

Formula 19 can make $I_{i}^{j}$ satisfy with the connection time constraint with J_j. If the waiting time of the yard engine is enough to break up another train after the procedure of $ψ (I_{π (i)}^{j})$ , it can be expressed as follow. $t_{π (i)}^{b} - t_{π (i) - 1}^{b} ⩾ t_{i}$ (20)

Formula 20 represents that the waiting time between I_π(i) and I_π(i)-1 is enough to break up I_i, which indicates that uncoupling order is unreasonable.

6.3. Algorism parameters setting

Parameters of the algorism is relatively sensitive. Hence, they are set as follows through abundant data-testing.

Selection of taboo objectives

The purpose of the tabu list is to avoid repeated research, reducing generation of unreasonable soluble vectors. Taboo objectives includes permanent taboo and regular taboo: (1) if the solution obtained after $ψ (I_{i}^{j})$ is unreasonable, the original numbers (I_i′, I_i) of the two trains are listed intopermanent taboo; (2) the operation of putting forward is forbidden if the vehicle $I_{i}^{j}$ has been put forward.

Taboo length

Taboo length refers to the iteration times without breaking the criterion when operation $ψ (I_{i}^{j})$ is forbidden. Short taboo length will lead to too much operations of pre-insert and slow the convergence rate. Conversely, fewer operations of pre-insert will cause local optimal solution. Since the dynamic taboo length has better robustness compared with the static state, it should be adaptive to the optimization process, which is denoted as the function f (x_ij) of current optimal values. $f (x_{ij}) = \sqrt{\sum_{i = 1}^{n} \sum_{j = 1}^{m} x_{ij} / - (n + m)}$ (21)

(3) Aspiration Criterion

Aspiration criterion incentives the local search for a better solution, which is beneficial to efficient. If the uncoupling order after the operation of pre-insert is obviously better than others tested by static wagon-allocation, the taboo is ignored and eliminated from the taboo list. If all the operations are forbidden, and the termination condition is not satisfied, it will allow all the operation to work in order to continue searching.

Termination condition

If all the candidate solutions are taboo, the current uncoupling order is the best. And then the paper takes advantage of static wagon-allocation to find the optimal solution. Otherwise, algorism ends when iteration runs up to its maximum steps Nc.

7. Algorism solving steps

Tabu algorism searches about current solution based on the idea of greedy. And it is dependent on the original solution and parameters setting.

7.1. Generation of original solution

The paper firstly fixes the uncoupling order based on list sorting (LS) algorism because of the dependence on original solution. The uncoupling order complies with FAM (First Available Machine), which means to known π (i), the available yard engine will break up the first train according to the arrival time; while the marshalling order complies with LBM (Last Busy Machine), which means to known π (j) and enough T, the least available yard engine will marshal the lasttrain of π (j) that waits for marshalling. Finally, it will adjust the arrangement sequence of yard engines and marshalling time through analyzing the uncoupling order as Fig. 4

Fig.4

Generation of original solution algorithm flow.

Sorting steps are as follow,

Step 1. The humps break up I_i based on FAM mechanism, fixing the uncoupling order π (i);

Step 2. Yard engines on the tail of hump marshals J_j based on LBM mechanism, fixing the marshalling order π (j);

Step 3. Rearrange the marshalling order π (j) according to the uncoupling order of the needed vehicles that forms the train J_j and the non-decreasing arrangement is π′ (j);

Step 4. Try to put forward J_j of π′ (j) in order to marshal it as soon as possible.

7.2. Algorism solving steps

Tabu search algorism makes use of neighbor-hood selection method through putting forward the key trains to reduce the generation of invalid solution. Show as Fig. 5

Fig.5

Tabu algorism searches algorithm flow.

When there are no neighbors to exchange, the current optimal solution is lifted to expand the search room, reducing the dependence on original solution meanwhile. The steps are as follows,

Step 1. Construct a taboo list and initialize various parameters;

Step 2. Call LS algorism to obtain the original solutions. Set the current solutions and current optimal solutions as original solutions, and empty the taboo list;

Step 3. Judge whether the terminal conditions are satisfied. If they are satisfied, turn to step 9;

Step 4. Fix the set of key trains based on original solutions. If the set is empty, turn to step 9;

Step 5. Judge whether the operation $ψ (I_{π (i)}^{j})$ is forbidden. If it is taboo, $ψ (I_{π (i)}^{j + 1})$ will be conducted for J_j+1;

Step 6. Operate $ψ (I_{π (i)}^{j})$ on J_j and calculate the start and end time of uncoupling and marshalling;

Step 7. Calculate the values of estimate function based on according to the new time table of uncoupling and marshalling and record the current optimal solution;

Step 8. Update the taboo list and judge whether the taboo objectives in the list are satisfied with aspiration criterion. Remove the eligible objectives from the list and turn back to step 3;

Step 9. Output the current optimal solution.

8. Numerical example

The algorithm is programmed with Matlab language. To verity the algorism, a numerical example is as follows. The basic information of arrival trains is listed in Table 1.

Table 1
Information of arrival trains

I _i $t_{i}^{d}$ $t_{i}^{jt}$ p_i (a, b, c, d) I _i $t_{i}^{d}$ $t_{i}^{jt}$ p_i (a, b, c, d)

0 0 0 12,18,8,20 6 116 22 20,0,0,20

1 8 23 0,25,15,0 7 138 21 20,0,20,0

2 32 21 10,0,30,0 8 165 23 0,20,10,10

3 42 22 35,0,5,0 9 188 19 10,0,0,0

4 64 25 0,15,10,15 10 212 23 0,15,20,0

5 97 21 0,10,0,25 11 236 22 5,0,20,0

I _i	$t_{i}^{d}$	$t_{i}^{jt}$	p_i (a, b, c, d)	I _i	$t_{i}^{d}$	$t_{i}^{jt}$	p_i (a, b, c, d)
0	0	0	12,18,8,20	6	116	22	20,0,0,20
1	8	23	0,25,15,0	7	138	21	20,0,20,0
2	32	21	10,0,30,0	8	165	23	0,20,10,10
3	42	22	35,0,5,0	9	188	19	10,0,0,0
4	64	25	0,15,10,15	10	212	23	0,15,20,0
5	97	21	0,10,0,25	11	236	22	5,0,20,0

Note: the beginning of the period will be recorded as 0 in order to facilitate the calculation and the following arrival and departure time of trains will be converted into integer according to the standard.

This paper hypothesizes the coveted length of vehicles has the $l_{i}^{k} \sim U [1.2, 1.3]$ uniform distribution, and the load is subject to the uniform distribution of $g_{i}^{k} \sim U [80, 84]$ in order to verity the influence of full axis constraint. while the load constraint of J_j is g_j = [3240, 3360], among which g_2,6,10 = [0, 3340]; length constraint is l_j = [49, 51], among which l_2,6,10 = [0, 52]. If there is empty operation, it doesn’t matter with the group number to represent types of empty vehicles.

The key trains set includes

I_{i}^{2} = {3, 6, 7, 9, 11}

I_{i}^{6} = {7, 9, 11}

I_{i}^{6} = {8}

, which is obtained respectively according to the under axis trains {J₂, J₉, J₁₀} based on the given original solutions. The algorism fixes that Nc = 20, and draws the conclusion that the uncoupling order π (i) ={ 1, 3, 2, 4, 5, 7, 8, 6, 9, 10, 11 }, the maximum number of departure vehicles is 394 as well. The wagon-allocation plan is as follows,

Table 2

wagon-allocation plan

J _j	$t_{j}^{f}$	$t_{j}^{c}$	$t_{j}^{bz}$	Train formation	Full axis
1	116	95	21	b/41	3358
2	148	128	20	a/39	3245
3	172	150	22	c/40	50.2
4	202	178	24	c/5,d/35	3302
5	223	203	20	b/27,c/13	50.9
6	248	225	23	a/38	3116
7	271	251	20	d/40	3288
8	298	274	24	b/20,c/21	50.8
9	334	308	26	a/0,c/40,d/0	3276
10	364	342	22	a/35	2878

The numerical example was conducted 100 times on the Core i3@2.10GHz, RAM@2G computer. The algorithm efficiency diagram show as Fig. 6.

Fig.6

Algorithm efficiency diagram.

If the constraint is the 40 vehicles of a train, the feasible solutions are obtained. But if the constraint is the full axis, there are 12 times that the program can’t work out the feasible solutions. Because the load and converted length give randomly can’t content with the full axis constraint. Judging from all the factors above, the constraint whether is full axis or vehicle number has a great influence on wagon-allocation plan. For the examples with feasible solutions, the average number of iteration is 10 times, the computation time is 26s, and the average static allocation time is 2.1s, accounting for 80% of the total time, which indicates that the efficiency of static allocation will directly determine the convergence speed of the algorism.

9. Conclusion

This paper regards the kinds of technical operation in marshalling station as the production process based on the sequence theory and simplifies the complex process as the arrangement of break-up and marshalling order according to the site condition. As a result, it constructs the sequence model based on single sever system. Moreover, the paper comes up with neighborhood search method for key train forward interpolation to improve the optimization effect of TS algorithm through study on the neighborhood structure of the solutions. Algorism regulates the specific computation method for full axis constraint and calculate the objective function through static allocation for each generated solution. Finally, the examples test the effectiveness of the algorism by setting the converted length and load of vehicles as random distribution. The result indicates that the two different constraints affect the allocation plans. However, the paper doesn’t take factors such as arrival-departure track utilization and arrangement of train inspection staff due to simplification of the whole production process in the marshalling station. How to research on all the production process, enrich aided decision optimization theory of phase plans and achieve the coordinated optimization of marshalling station dispatching system remain to be further discussed.

Footnotes

Acknowledgments

This study is Supported by National Key R&D Program o-f China (2018YFB201401); Beijing Natural Science Foundation (J160003); National Natural Science Foundation of China (61403022); and the Fundamental Research Funds for the Central Universities (2017JBM030).

References

C.-G.

Wang , Study on wagon-flow allocating problem in a marshalling station by using calculating method on-table[J], Journal of the China Railway Society24(4) (2002), 1–5.

C.-G.

Wang , Research on the model and algorithm of dynamic wagon-flow allocating in a marshalling station[J], Journal of the China Railway Society26(1) (2004), 1–7.

Zhao ,

Q.-Y.

Peng ,

Wen , et al., Local neighborhood search algorithm for generalized dynamic wagon-flow allocation of railway technical stations[J], Journal of Southwest Jiaotong University45(3) (2010), 486–492.

Zhao ,

X.-S.

Han and

Q.-Y.

Peng , Lagrangian relaxation algorithm for integrated wagon-flow allocation and shunting locomotive scheduling at technical railway station [J], Journal of the China Railway Society33(11) (2011), 1–7.

Jing and

C.-G.

Wang , Model and algorithm of dynamic wagon-flow allocating in a marshalling yard under uncertaint conditions [J], Journal of the China Railway Society32(4) (2010), 8–12.

Xue ,

Wang and

Zhang , Optimization algorithm for wagon-flow allocation in marshalling station [J], Journal of Southwest Jiaotong University45(6) (2010), 1–6.

S.-W.

He ,

Song and

A.-Z.

Hu , Study on coordination of hard and soft optimization of marshalling station stage plan[J], Journal of the China Railway Society21(4) (1999), 1–8.

Jing ,

C.-G.

Wang ,

Xue and

Mu , Estimation method of rolling-cars time on marshalling yard[J], Journal of Southwest Jiaotong University44(6) (2009), 900–905.

S.-W.

He ,

Song and

S.S.

Chaudhry , An integrated dispatching model for rail yards operations[J], Computers & Operations Research30(7) (2003), 939–966.

10.

M.-H.

Wang and

Zhao , Optimal model and algorithm of stage plan of intelligent dispatching system for marshalling stations[J], Journal of the China Railway Society27(6) (2005), 1–9.

11.

Hui-Min and

An-Zhou , Comprehensive optimization of car flows joining at bidirectional marshalling station[J], Journal of the China Railway Society20(6) (1998), 16–21.

12.

Q.-Y.

Peng ,

Zhao and

X.-S.

Han , Model and algorithm for the generalized wagon-flow allocation problem of railway technical station[J], China Railway Science31(2) (2010), 108–114.

13.

W.-Q.

Li and

Wang ,

Du , et al., The model and algorithm of using shunting engines for railroad technical service station[J], Journal of Systems Engineering15(1) (2000), 38–43.

14.

Huang ,

Shan ,

Cheng and

Sun , TRec: An efficient recommendation system for hunting passengers with deep neural networks, Neural Computing and Applications (2018).

15.

S.-D.

Wang and

Zheng , Solving the scheduling problem of hump locomotive with ant colony optimization[J], China Railway Science28(3) (2007), 1–7.

16.

C.-G.

Wang , Network model of static wagon-flow allocation in a marshalling station[J], Journal of Transportation Engineering and Information1(2) (2003), 1–7.

17.

Glover , Future paths for integer programming and links to artificial intelligence[J], Computers and Operations Research13(5) (1986), 533–549.

18.

A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem[J], Computers and Operations Research38(6) (2010), 967–983.

19.

Tang , Modern Scheduling Theory[M]. Shanghai: Shanghai Science Popularization Press, 2003.