Study And Application Of An Algorithm Of Selling Tickets In Reason For Last Trains On Rail Transit Network

During interchange in station in a city rail transit,each line's last train time schedule does not couple with each other,the embarrassment situation is always happened that passengers bought tickets but can not catch up the last train when they interchanged in one station.With the growing scale of city rail trainsit network,the trend of transfer paths will becomec complication more and more,the similar situation will become more frequence.To solve the reachable predicting problem about last train of city rail transit network in night when passengers interchanged,a technical idea about the solution of reachable selling ticket in reason of last train in night has been proposed,and a solving algorithm for the optimal reachable multi-paths of last trains in night is designed and implemented.The reachable multi-path of last train in night can be predicted by the algorithm,therefor,selling tickets in reason of last train in night of rail transit from ticket vendor machine and semi-automatic ticket vending machine can be effectively supported.The primary research work of author in this thesis is as the followings:1) For the topology structure of Shanghai city rail transit network at present,author of this thesis participated in the study of an information non-losing simplified modeling method,and has programmed to achieve its data structure of the adjacency list,so that it is easily to be processed by computer.2) Research on and analyze the features of the last train time schedulec in night,the corresponding process approach has been proposed for the tends of the last train in night on cycle line and shared line with common stations of going back garage.3) Based on the simplified modeling and the idea of the shortest path and deviation paths,the algorithm for searching 2^th path and 3^th path has been studied and implemented.4) The multi-paths are solved by replacing of different lines' keyless station pairs and between keyless station and key staion pair based on the simplified modeling.5) The study result has been showed through touch screen,and the application solution has been also given that can be used for ticket vendor machines.Based on the studied result of this thesis,an optimal reachable multi-path quering system for last train in night of Shanghai rail transit has been designed and implemented by the author,and it is awarded the third prize of national university outstanding display item on 2009 Shanghai International Industrial Exposition.