Research And Application Of Route Searching Based On Heuristic Algorithm In CBI System

With the current China railway strategy,China has achieved many magnificent accomplishments in its railway development.All those achievements have something to do with the development of Chinese Train Control System(CTCS),in which Computer Based Interlocking(CBI)system,ensures trains and shunts' safe operation in railway stations by route control method.In the route control,first step is to search a reasonable route.So route searching module is very important in the CBI system.The traditional route searching method is to use the way of searching static route table whose transplantability is not so good or to use the way of traversing topological structure of station that is a little inefficient and costs more running memory.And the module is put in CBI system's interlocking machine.In the thesis,the following scheme is proposed for the route search module.The layout graph of station signal is modelled into topological graph structure by graph theory,and then use heuristic searching algorithm to find a reasonable route dynamically.After doing so then the route search module is put in CBI system's operation machine.In that way,there are three advantages.Firstly,if there is any change of station,just providing new station's data rather than getting a new interlocking route table and that means the way has better transplantability and expansibility.Secondly,Comparing with method of traversing topological structure of station,heuristic search algorithm is more efficient.Last but not least,by putting route searching module in operation machine,interlocking machine's programming can be simplified,thereby its reliability is also improved.In order to achieve the effects mentioned above,the following researches were done.First of all,present research status and development trend in the area of CBI system and route searching were introduced.By analyzing CBI system's route control function and its route searching module,the current problem is get and the research direction had been determined.Then,combing with the actual situation of the layout graph of station,the layout graph was modelled into directed acyclic graph with weight by using graph theory finally.Next,graph searching's fundamental theory was introduced.Combining with the route searching's characteristics,two route search processes respectively based greedy strategy and A*algorithm were proposed.Their distinction,connection,advantages and disadvantages were also analyzed.Besides,a test platform was established and it gave proof that route searching based on A*algorithm had a better searching effect than traditional way that traverse station graph.Finally,combined with the CTCS-3 simulation and application platform,the route searching based A*algorithm was applied into the CBI system,and achieved good route searching effect,which proved the effectiveness and availability of the algorithm.