A Branch-and-Price Algorithm for Solving the Railroad Blocking Problem

The railroad blocking problem is one of the most important planning problem in freight railways. By solving this problem, once can minimize volume of switching process and total cost of delivering the commodities. This paper presents a method based on branch and price algorithm for solving the railroad blocking problem. This algorithm is a combination form of branch-and-bound and column generation algorithms. Branch and price is a variant of branch and bound, with bounds provided by solving linear programs using column generation at nodes of the branch and bound tree. In branch and price algorithm, re-optimize column generation algorithm in each of branches. Because the bound provided by the LP relaxation is weak, we suggest cuts to strengthen it and show the effect of adding them on the column generation procedure. Implementation of this algorithm has been done by Java programming language. To analyze the quality of the algorithm, some simulated problems with different size generated and are solved by CPLEX software. The results of our algorithm compared with CPLEX’s results. The comparison shows the efficiency and accuracy the purpose algorithm.

کلیدواژه ها:

Railroad Blocking Problem ، Branch and Price Algorithm ، Column Generation ، Dantzig-Wolfe algorithm ، Optimization