A Branch and Bound Algorithm for the Exact Solution of the Problem of EMU Circulation Scheduling in Railway Network

This paper is concerned with the scheduling of Electrical Multiple Units (EMUs) under the condition of their utilization on one sector or within several interacting sectors. Based on the introduction of the train connection graph which describes the possible connection relationship between trains, the integer programming model of EMU circulation planning is constructed. In order to analyzing the resolution of the model, a heuristic which shares the characteristics with the existing methods is introduced first. This method consists of two stages: one is a greedy strategy to construct a feasible circulation plan fragment, and another is to apply a stochastic disturbance to it to generate a whole feasible solution or get a new feasible solution. Then, an exact branch and bound method which is based on graph designing is proposed. Due to the complexity, the lower bound is computed through a polynomial approximation algorithm which is a modification from the one solving the degree constraint minimum 1-tree problem. Then, a branching strategy is designed to cope with the maintenance constraints. Finally, we report extensive computational results on a railway corridor in which the sectors possess the basic feature of railway networks.