铁路车流径路优化分布式算法

Distributed Algorithm for the Optimization of Railway Car Flow Routing

针对铁路车流径路优化的计算量随着路网中节点数和车流数的增加呈指数型增长的问题,引入分布式计算方法进行求解。对于任意一个固定顺序的车流排列,基于线路能力约束条件,构造车流径路优化模型。定义对该车流排列评价的函数,将车流径路优化问题分解成车流排列的评价计算问题和车流排列优化问题。设计分布式计算网络结构及网络程序流程。采用改进的禁忌搜索法,在服务器端完成车流排列空间的优化搜索,在不同的客户机端进行车流排列的评价计算,利用计算机网络将二者有机地结合起来,形成分布式算法。将车流排列优化问题归纳为旅行商问题,分析模型算法的复杂性。对算例进行计算表明:对构造的车流径路优化模型采用分布式算法进行求解可以节省大量时间,但存在对计算机网络配置要求高的问题。

Aimed at the problem that the computational complexity of car flow routing optimization increases exponentially with the amount of the node and the car flow in railway network, the distributed computing method is introduced in this paper. For a random car flow in fixed order, establishing a car flow routing optimization model with capacity limit in railway network and defining a function to evaluate the or der, the problem is decomposed into two parts： the evaluative function computing of car flow order and the car flow order permutation optimization. Distributed computing network and program flow chart are de signed. An improved tabu search algorithm run on the computer server is adopted to solve car flow order permutation optimization while the evaluative function computing is run on different client computers. Combined with computer network, the two parts are integrated systematically and the distributed compu- ting algorithm is accomplished. By inducing that the car flow order permutation optimization is traveling salesman problem, the computational complexity of the distributed computing algorithm is analyzed. Cases using this algorithm show remarkably that it is necessary and superior, but it needs a high request of corn puting environment.