单线列车调度问题的双向阻塞车间调度模型及其粒子群求解算法  

Bi-directional Blocking Job Shop Model and Particle Swarm Optimization Algorithm for Train Scheduling Problem on Single-track Lines

作　　者：张其亮[1,2] 陈永生[2] 

机构地区：[1]江苏科技大学电气与信息工程学院,张家港215600 [2]同济大学电子与信息工程学院,上海200331

出　　处：《计算机科学》2013年第12期276-281,共6页Computer Science

基　　金："十一五"国家科技支撑计划项目(115-04-YK-048)资助

摘　　要：针对单线列车调度问题的特点,以线路中列车的总运行时间最小为目标,建立了可以直观描述问题解空间的双向阻塞车间调度模型,并提出了一种有效的离散粒子群优化算法进行求解。该算法基于双向阻塞车间调度模型设计了排列编码形式,从而可确定列车的运行顺序,同时利用随机策略和运行时间最短优先策略选择列车运行轨道;算法在求解过程中,提出了列车冲突的检测和化解方法,并按照"调度-检测冲突-化解冲突"的步骤逐区段调度列车运行;最后,利用离散粒子群优化算法进行全局优化,得到问题的最优解。仿真实例表明,所得模型和算法能够高效地求解单线列车调度问题。According to the characteristics of the single-track lines train scheduling problem, a bi-directional blocking job shop scheduling （BDBJSS） model was built to describe its solution space and the discrete particle swarm optimiza- tion （DPSO） algorithm was proposed to solve it with the objects of makespan minimization. Based on the BDBJSS mo- del,permutation based encoding schemes were designed in DPSO algorithm for arranging the train sequences, and the random strategy and processing time shortest first strategy were put forward for selecting the running tracks. Also, the train conflict detection and resolution methods were proposed in the algorithm, which can schedule trains according to the steps of ＂scheduling-detecting conflicts-resolving conflicts＂. At last,DPSO algorithm was used for global optimiza- tion to get the best solution. Experiments results show that the model and algorithm can solve single-track lines train scheduling problem effectively.

关 键 词：双向阻塞车间调度 单线列车调度 离散粒子群优化算法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论] U292.41[自动化与计算机技术—计算机科学与技术]