Solving train formation problem using simulated annealing algorithm in a simplex framework

The train formation plan (TFP) determines the train services and their frequencies and assigns the demands. The TFP models are often formulated as a capacitated service network design problem, and the optimal solution is normally difficult to find. In this paper, a hybrid algorithm of the Simplex method and simulated annealing is proposed for the TFP problem. The basic idea of the proposed algorithm is to use a simulated annealing algorithm to explore the solution space, where the revised Simplex method evaluates, selects, and implements the moves. In the proposed algorithm, the neighborhood structure is based on the pivoting rules of the Simplex method that provides an efficient method to reach the neighbors of the current solution. A state‐of‐the‐art method is applied for parameters tuning by using the design of experiments approach. To evaluate the proposed model and the solution method, 25 test problems have been simulated and solved. The results show the efficiency and the effectiveness of the proposed approach. The proposed approach is implemented to develop the TFP in the Iranian railway as a case study. It is possible to save significant time and cost through solving the TFP problem by using the proposed algorithm and developing the efficient TFP plan in the railway networks. Copyright © 2012 John Wiley & Sons, Ltd.