基于运行网络配流的客专列车开行方案遗传优化研究

摘要

By the functions and characteristics of genetic algorithm, the optimization of the operation scheme for passenger dedicated line (PDL) train was described as the optimization of network flow distribution. The optimal network flow distribution was corresponded to the optimal train operation scheme. First, a cost-capacity network was built aimed at any train operation scheme. The optimal flow distribution scheme was described according to the minimum cost flow of the network, and the minimum cost was utilized as the individual fitness function. Then, allowed for lots of infeasible excellent individual genetic information generated by the restriction of break even passenger numbers, Collaborative Symmetric Groups Intersect Genetic Algorithm was designed to solve the problem of linear PDL and single direction train operation scheme, and the algorithm was further extended to network PDL. Research shows that the individual encoded by operation scheme can be described as a stepwise capacity restricted cost-capacity network and the individual fitness value is corresponded to the minimum cost flow of the network. In a non-excess capacity network, a feasible flow that violates the stepwise capacity constraints won't occur and the occurrence of fixed costs and negative costs can be avoided through a controlled network capacity.%借助于遗传算法的求解功能和特点,将客运专线旅客列车开行方案优化问题描述为对列车运行网络客流分配的寻优.最优的列车开行方案对应于最优的客流分配方案.首先,针对任意的列车开行方案,构建费用容量运行网络,并通过该网络的最小费用流描述最优客流分配方案,用运行网络中客流分配的最小费用作为个体适应值函数；而后,考虑到网络中列车保本定员限制所产生大量不可行个体的优良遗传信息,设计出求解直线型客运专线单方向旅客列车开行方案优化问题的协同对称群体交叉遗传算法,并进一步将其推广到网状客运专线上.研究发现:可以将开行方案编码的个体描述为含有阶跃容量限制的费用—容量网络,个体的适应值对应于该网络的最小费用流；在非能力过剩网络中,不会出现违反阶跃容量限制的可行流,并且可以通过控制网络容量,避免产生同定费用和负费用.