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

技术站调度问题中配流与调机运用是关系密切的两个基础问题。基于单机器调度和资源分配理论,构建单解单编技术站配流与调机运用综合问题的混合整数线性规划模型,同时确定出发列车的编组内容和调机的解编任务,使得出发列车满足列车编组要求,且车辆在站加权总停留时间最小。设计拉格朗日松弛算法松弛掉连接约束,将原问题分解为解体子问题、配流子问题和编组子问题,对偶问题采用传统次梯度优化算法求解。最后,采用既有文献算例对该算法的有效性进行测试,结果表明:与分支定界算法相比,该算法能够实现计算质量和时间的较好折中。

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

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(ma...