基于车次径路约束下的客运径路生成算法优化

针对目前客票径路计算中径路信息与实际旅客出行径路之间存在的差异性,从分析径路生成的计算模型出发,结合铁路通票业务背景,提出一种车次约束机制下的径路生成计算方法。算法以选择性集中存储为径路存取方式,实现径路公共信息的全路共享与车站特殊径路的分布式存取,有效压缩径路信息存储空间,提高径路选择效率;以车站-车次邻接表为基本数据结构,将铁路路网图改进为列车约束下的列车可达图,保证车站生成个性化径路的合理性和有效性;算法摒弃原有径路计算只计算本站至全路各个结算站间最短K路径的方法,分车站特殊径路计算和公共径路计算两步实现径路的计算,从根本上保证径路计算的有效性,解决通票径路与列车走行径路不符问题,实现了对现有径路生成算法的优化。

Optimization on Route Computation Algorithm Based on Train-Route Restriction

Because there is the inconsistency between the pass ticket routes provided by the current ticketing and reservation system and the real traveling routes being got by passengers,this paper,firstly according to the background of rail pass and combining the analysis about current route-computation model,presents a new method which is based on train-route restriction to design pass route algorithm.This new method takes hierarchical storage structure as its storage strategy,which fulfills the distributed storage about the share routes and the private routes to effectively compress the storage space and improve route selection efficiency.The method takes station-train adjacency list as its basic data structure and rebuilds the rail-net with the restriction of train routes,to make the got-route data validity and rationality.The route algorithm is designed as two steps computation: the special-route computation step and the common-route computation step,which is instead of the wholly K-shortest-path route computation,in order to improve the algorithm.So it radically solves the conflict between pass-ticket route and train route,and implements the optimization on route computation.