Crew scheduling optimization considering time cost for metro loop lines with multiple relief points

To realize the flexible optimization of large-scale crew scheduling problem in the context of a metro loop line with multiple relief points, a normalized set covering model considering duty number, unnecessary working time and deadhead time is established. The problem is then decomposed by the DW decomposition. An FMD-BP algorithm based on the branch and price framework is proposed, which integrates the Ryan and Foster branching strategy and a multi-start shortest path algorithm well. Case analysis shows that the algorithm proves efficient in solving the proposed model. Allowing deadheads can help lower duty number and total cost, and considering deadhead cost in the model can help reduce deadhead time and further the reduction of total cost. Ideal duty number and work efficiency can be achieved by adjusting parameters in the time cost function. For the test loop line, the holistic scheduling results prove better than when the inner and outer loops are scheduled separately in terms of the total cost, and duty number when prohibiting deadheads, and total deadhead and unnecessary working time when allowing deadheads. Moreover, the holistic scheduling, while allowing deadheads and considering deadhead cost, proves to achieve the best scheduling plans for the test metro loop line.