Optimization model and algorithm for urban rail crew pairing problem with multiple depots
To solve the crew pairing problem for metro lines with multiple depots,this paper studies the optimization model and algorithm to satisfy the equivalences of attendance and leave duties at each depot,and meanwhile improve the work efficiency.By considering the constraints of attendance and leave,alternation,meals,and workload,a space-time network with respect to segments is firstly constructed,and a breadth-first search algorithm is designed to search the required feasible duty pool.Next,a set covering problem with additional constraints for the crew pairing problem is proposed,so as to minimize the total cost.To effectively solve the large-scale cases,a column-generation based algorithm is proposed.The proposed method is tested using the data from Nanchang metro line 1,and experimental results show that,the method can well satisfy the conservation constraints on the entering crews and outgoing crews for each depot.Compared with the existing plan,the obtained schedule by the proposed method reduces 2 crew duties,and the average connecting time for each segment is reduced by 1 minute and 17 seconds.This method can satisfy the requirements of crew pairing with multiple depots,and the work efficiency can also be improved,which can provide decision support for the metro operation in reality.
urban rail transitcrew pairingmultiple depotsattendance and leaveset covering modelcolumn generation
NETL
NSTL
万方数据
