技术站配流与调机运用综合问题的拉格朗日松弛算法  

Lagrangian Relaxation Algorithm for Integrated Wagon-flow Allocation and Shunting Locomotive Scheduling at Technical Railway Station

作　　者：赵军[1] 韩雪松[1] 彭其渊[1] 

机构地区：[1]西南交通大学交通运输与物流学院,四川成都610031

出　　处：《铁道学报》2011年第11期1-7,共7页Journal of the China Railway Society

基　　金：国家自然科学基金资助项目(60776827);2010年西南交通大学优秀博士学位论文培育项目

摘　　要：技术站调度问题中配流与调机运用是关系密切的两个基础问题。基于单机器调度和资源分配理论,构建单解单编技术站配流与调机运用综合问题的混合整数线性规划模型,同时确定出发列车的编组内容和调机的解编任务,使得出发列车满足列车编组要求,且车辆在站加权总停留时间最小。设计拉格朗日松弛算法松弛掉连接约束,将原问题分解为解体子问题、配流子问题和编组子问题,对偶问题采用传统次梯度优化算法求解。最后,采用既有文献算例对该算法的有效性进行测试,结果表明:与分支定界算法相比,该算法能够实现计算质量和时间的较好折中。Wagon-flow allocation and shunting locomotive scheduling are two closely-related issues in scheduling operation at technical railway stations.On the basis of the theory of single machine scheduling and resource allocation,the mixed integer linear programming model was constructed for integrated wagon-flow allocation and shunting locomotive scheduling at the railyard with single locomotive break-up and single locomotive make-up operations.Simultaneously the make-up of each departure train and the break-up（make-up） task of each shunting locomotive were determined so that each departure train satisfied the train make-up requirements and the total weighted time for wagons staying idle at railyard was minimized.The Lagrangian relaxation algorithm was proposed to relax the linked constraints and resolve the original issue into the break-up,wagon-flow allocation and make-up sub-issues.The dual problem was solved by the traditional subgradient algorithm.At last,by computation of instances from the existing literature and by comparison with the branch and bound algorithm,the proposed algorithm was proved to be able to achieve a preferable tradeoff between computation quality and computation time.

关 键 词：技术站 配流 调机运用 混合整数线性规划 拉格朗日松弛算法 

分 类 号：U292.16[交通运输工程—交通运输规划与管理]