Branch And Bound Assignment Problem
In high-speed railway network, Electrical Multiple Units (EMU) are the main tools used for the passenger transportation.They are significantly cost equipment, because not only is their acquisition or construction expensive but also they need power supply and regular maintenance.Through the analysis of the studies concerning EMU circulation plan, it can be seen that the problem could be transformed into some classic optimization problems, and due to the complexity of these problems, most of the existing solution generation methods belong to the range of probability based searching heuristics.
In Section 5, the exact branch and bound algorithm for solving the problem is outlined, and the details of the algorithm such as the calculation of the approximate lower bound and the branching strategy is illustrated.The algorithm is based on the graph theory and could be able to deal with the problems of practical size within a reasonable time. In Section 2, we describe the details of the EMU circulation scheduling problem we study.Furthermore, we propose a heuristic, which shares the characteristics with the existing methods and is based on local search strategy. In Section 3, we introduce the concept of the train connection graph, based on which the model of EMU circulation scheduling in high-speed railway network is constructed.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.Empty movements and shunting operations are considered and the robustness is introduced by selectively avoiding empty train movements and these operations.Cadarso and Marín  presents a model to study the robust determining of the best sequence for each rolling stock in the train network. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.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.However, the EMUs are scheduled within several linked sectors and some complicated constraints such as the EMU maintenance constraints must be taken into account; therefore, more applicable methods should be developed for solving the construction of the EMU circulation plan.Zhao and Tomii  transformed the original problem into the Traveling Salesperson Problem and introduced a probability based local search algorithm, whose key points are about the connection of the trains and the generation of the maintenance arcs.  transformed the original problem into a multiple Traveling Salesperson Problem with replenishment and designed a hierarchical optimization heuristic algorithm.  designed a simulated annealing algorithm by introducing the penalty function and 3-opt neighborhood structure, which is based on the circular permutation of all trains.  introduces the optimized EMU connection graph, based on which the improved particle swarm optimization algorithm is designed for solving the problem.