Optimization method of Tabu Search algorithm for urban rail transit crew scheduling scheme
DENG Lianbo
XIE Ziruo
GAN Shuhuai
ZHANG Ying
REN Shaokun
Abstract：Considering the widespread adoption of rotation crew regulations and the mixing of day shifts and day-and-night shifts in urban rail transit,this study addresses the crew scheduling scheme to reduce service costs and improve efficiency. Firstly,by analyzing the elements of the urban rail transit crew scheduling scheme and considering requirements such as crew segment duration,connection time,and locations,a multi-objective 0-1 integer programming model is established. This model aims to minimize comprehensive index such as the number of crew members and total connection time. Secondly,a Tabu Search(TS) algorithm is designed to solve this model,using the First-In-First-Out (FIFO) principle for initial solution assignment and four neighborhood transformation strategies to enhance solution diversity. A multi-neighborhood structure-based Tabu Search Algorithm is constructed to optimize the crew sched-uling scheme. Finally,the proposed method is validated using the crew scheduling scheme of Guangzhou Metro Line 7. Results demonstrate that the optimized scheme reduces the number of crew segments and total connection time by 20％ and 4.94％,respectively,compared to the actual operation scheme. The number of trains on duty in each crew segment increases from 8.2 to 10.3,and the effective driving time increases from 5.4 to 5.8 hours. All indicators of the optimization plan are significantly improved,provid-ing theoretical and methodological support for urban rail transit crew planning.
Keywords：urban rail transittrain crew schedulingmulti-objective 0-1 integer programmingTabu Search Algorithmmulti-neighborhood transformation
Publication Date：2024-08-28
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：8( 164-171 )