Keywords

1 Introduction

With the rapid development of railway transportation, computer based interlocking system (CBI) has been widely used in signal control field. It mainly deals with the interlocking relationship between switch, signal and track circuit, and improves the efficiency of transportation on the premise of ensuring safety [1]. A basic function of computer based interlocking system is to find strictly correct and available route for train dispatch, to avoid train collisions and derailments [2]. Route search, literally, is searching the target route according to the start signal and the end signal given [3]. Recent interlocking systems mainly adopt one of the implementation styles: called as route-list based style and route-search based style. The former one contains a set of static data consisted by all possible routes which are generated previously. The latter one, contrarily, is embedded by real-time route-search process other than data copies [2]. In this paper, we mainly discuss the latter one.

In view of the similarity between the railway yard and the directed graph, the railway network will be modeled as a directed graph for route search. And in order to improve efficiency, the artificial intelligence theory is applied in the computer interlocking system. A method combining the idea of heuristic search and depth-first traversal has been put forward, to improve the existing route search method.

2 Railway Yard Model

2.1 Layout of Railway Yard

In a railway yard, signal equipment mainly includes signal, switch, track circuit and so on. Each equipt has a circuit to output its real-time status (busy or idle) and acts according to the operation command. A typical railway yard is shown in Fig. 1. This is a throat area in down direction.

Fig. 1
figure 1

Layout of railway yard

Full size image

According to the physical connect among signal equipment, whole station network can be abstracted as a directed weighted Graph G(V,E). V is the set of nodes, \( {\text{V}} = \left\{ {{\text{ v}}_{1} ,{\text{ v}}_{2} ,{\text{ v}}_{3} ,{\text{ v}}_{4} , \ldots ,{\text{ v}}_{\text{i}} } \right\} \). E is the set of connections between two nodes, \( {\text{E}} = \left\{ {{\text{ e}}_{1} ,{\text{e}}_{2} ,{\text{e}}_{3} ,{\text{e}}_{4} , \ldots ,{\text{e}}_{\text{i}} } \right\} \) [4].

2.2 The Directed Graph Model of Railway Yard

The signal equipments, signal, switch, track circuit without switch (NoSwitch for short), and intruded-limit insulated joints (CX for short), have been chose as nodes in the railway-yard directed graph. The physical connects among these signal equipments are regarded as edges. The railway-yard directed graph can generated automatically according to the coordinates of signal equipment in the layout of railway yard. The railway-yard directed graph for testing is shown in Fig. 2.

Fig. 2
figure 2

Railway-yard directed graph

Full size image

2.3 Data Storage Structure

There are two data storage structures for directed graph, adjacency list and adjacency matrix. The adjacency list is a popular choice because its structure is very compact in the representation of a sparse graph. Hence adjacency list is chose to storage railway-yard directed graph.

For a directed graph, a inverse adjacency list is necessary. The adjacency is used to record the out-degree of node, while the inverse adjacency list is used to record the in-degree of node. The storage structure of adjacency list is defined in Fig. 3. And the additional node information of node is shown in Table 1. Note that if one node don’t have subsequent node, it’s a dead node [5]. It is important in programming.

Fig. 3
figure 3

Storage structure of adjacency list

Full size image
Table 1 Additional node information
Full size table

3 Route Search Algorithm on Heuristic Strategy

For a directed acyclic graph, there are generally two ways for traversal: depth-first search (DFS) and breadth-first search (BFS) [6]. Depth-first traversal is similar to DLR in binary tree [7]. It is the common choice in railway-yard route search. The process of DFS is stated as follows:

  • Visit the starting point u, and set visited flag.

  • Then visit every adjacent node v of u, if v is not visited, v will be the new starting point u, and turn to step 1(This is a recursion process). If not, backtrack.

In brief, DFS visits nodes as deep as possible. The pseudo code is described in Fig. 4.

Fig. 4
figure 4

Pseudo code of DFS

Full size image

However, DFS is a blind algorithm. In order to improve efficiency, a new search method combining the depth-first traversal with heuristic strategy has been put forward.

Heuristic search uses the characteristics of the problem itself to control search direction. It gives priority to visit the most promising node which is in the optimal route, making it close to the optimal solution, and getting high search efficiency. In fact, when switch node is visited in search process and its frog open direction is in accordance with the search direction, judge the two adjacency node which is more promising to get the target node by the calculation of evaluation function. Evaluation function is a real function used to estimate the node importance. It is got according to the practical experience and experiment optimization. Considering that the effects of longitudinal linear distance change is more than that of horizontal linear distance change, hence weighted Manhattan Distance has been chosen as the evaluation function h(v). The function is stated as following. Note that Vi is the arbitrary node in the search process. Its coordinates are (x i , y i ). The Vj is the target node. The coordinates are (x i , y i ).

$$ {\text{h}}(v_{i} ) = \left| {x_{i} - x_{j} } \right| + 2*\left| {y_{i} - y_{j} } \right| $$
(1)

In addition, railway-yard route search is an actual problem. Therefore there are some constraints according to the relevant regulation, stated as bellow:

  • In order to avoid detour route, only search along the same direction of siding is allowed. In this way, we won’t find a detour route. This principle isn’t used in spared route search.

  • The change point must be specified in spared route search.

The entire route search process has been described in detail in the flowchart in Fig. 5.

Fig. 5
figure 5

Flowchart of route search algorithm

Full size image

4 Experiment and Analysis

Before testing, the first step is to generate the table of route node pair [8]. All possible route node pair is ruled in Table 2.

Table 2 Route node pair
Full size table

This method is used before train dispatch. Hence it will give CBI all involved signal equipment in the target route. If the route searched satisfies the interlocking relationship, it will display in the form of white light band. We choose X as the start signal and SIII as the terminal signal. Search the incoming route to IIIG. Test result is shown in Fig. 6. We choose D11 as the start signal and D13 as the terminal signal. Shunting route test result is shown in (Fig. 7).

Fig. 6
figure 6

Test result of incoming route

Full size image
Fig. 7
figure 7

Test result of shunting route

Full size image

5 Conclusion

Because of the heuristic information, it makes more intelligent in judging the search direct. Effectively reduces the number of search times. Meanwhile, the application of evaluation function only in switch node improves the search efficiency. Hence, the Route search algorithm based on heuristic strategy has a great advantage in the simplicity of time redundancy and programming.