蚁群算法在调机运用计划中的应用

Solving the Scheduling Problem of Hump Locomotive with Ant Colony Optimization

编组站调机运用计划为具有不同开工、完工时间窗口的单机调度问题,优化目标是最小化晚点列车的数量。为解决这一NPC问题,建立单机调度数学模型,采用蚁群算法求解。设计的算法步骤是,将调机运用问题描述成适合蚁群算法的形式,并进行初始化,考虑迭代过程中信息素对未来决策的影响程度,定义与问题相适应的转移概率,进而确定选择策略来平衡已有方案的利用和搜索空间的选择,采用2-opt方式的局部搜索策略来避免“早熟”或者“停滞”现象,同时在蚂蚁经过的路径上进行信息素更新,实现对该优化问题的有效求解。以某编组站有12列到达列车和少量暂存列车解体编组出12列出发列车为例,利用设计的蚁群算法步骤,求得到达列车的解体次序和出发列车的编组次序,验证了该算法在编组站的改编能力无法满足车流配送情况下实现合理安排调机的有效性。

The scheduling problem of hump locomotive in marshalling station can be described as a single machine scheduling problem with distinct due window and the object of optimization is minimizing the total number of weighted tardy trains. To solve this NPC problem, a mathematical model is developed and ant colony optimization （ACO） is utilized. After deducing the problem to the formulation suitable for ACO and considering the influence of pheromone in iterations, a new transition probability is defined, and then a rational transition strategy is selected to balance the exploitation of good solution and the exploration of the search space. To avoid precocity and stagnation in the algorithm, the local search strategy is 2-opt. Af- ter the pheromone trail information is updated according to the distribution of the best solutions, the effi- cient solution of this optimization will be got. To validate the efficiency and performance of this algorithm when the capacity of classification in marshalling station is limited, an instance of scheduling problem of hump locomotive including 12 inbound trains, little cars on hand and 12 outbound trains is demonstrated and the sequence of hump engine is resolved by ACO.