A hybrid column generation approach for solving rolling stock assignment optimization model of urban rail transit

作者：He Bisheng^*; Song Rui; He Shiwei; Li Jin

来源：China Railway Science, 2014, 35(1): 122-129.

DOI：10.3969/j.issn.1001-4632.2014.01.19

• Assignment problems
• Branch-and-price algorithms
• Column generation
• Degenerate problems
• Neighborhood search algorithms
• Optimization modeling
• Total operation costs
• Urban rail transit

An urban rail transit rolling stock assignment network with no fixed operational section is proposed, in which the nodes are the transport tasks for the rolling stock and anti depot nodes, and the arc connects the two transport task nodes or the transport task node with anti depot node. Urban rail transit rolling stock assignment mathematical model aims to minimize the total operation cost with the relevant requirements. A hybrid column generation algorithm is designed to solve the model. The algorithm combines the branch-and-price algorithm with the large scale neighborhood search algorithm. The large scale neighborhood search algorithm is adopted to update a newly acquired initial integer solution. The integer solution is implemented as the new columns into the column generation algorithm to avoid the degenerate problem. Meanwhile, the newly acquired integer solution can update the upper bound of the branch-and-price search tree. Therefore, a more powerful upper bound is used to the branch-and-price search tree to speed up the algorithm process. Numerical results show that our approach can solve large-scale rolling stock assignment problems, and result in more effective solutions.

• 出版日期2014
• 单位北京交通大学