NCKU Team Wins the 2nd Place Award in INFORMS Railway Problem Solving Competition
The purpose of this competition is to draw the public attention by offering high-value awards, USD$3,750, for the top 3 teams in the final list. This year there are 54 teams from 15 countries registered for the 2019 competition and 12 of them, mostly composed of professors or doctoral students from several renowned universities worldwide, have submitted their final reports.
The competition problem, a hard integrated train blocking and shipment path optimization problem, seeks optimal shipment paths, train paths, and shipment-to-train assignment that satisfy the arc capacity, node capacities (rail cars and tracks) of minimum costs containing travel costs, train accumulation costs, and classification costs. To make an optimal decision, one requires experiences and skills of decent mathematical modeling, logic reasoning, and algorithmic design and implementation.
The NCKU team has proposed several innovative techniques and solution methods, mostly based on the linear integer programming models. First, they recognized this problem is a special multicommodity network design problem, whose solution serves as a warm start to the original problem. To further converge it to a better solution, they generate good routings based on the K-th shortest path algorithm, and use them as candidate paths to be selected by two new mixed integer linear programs. The proposed linear mathematical models are a breakthrough, compared with the nonlinear models in literature, for solving the problem. In addition, they came up with an innovative idea which estimates the penalties to the constraint violation by solving an inverse shortest path problem, which helps to generate solutions of better qualities. The computational experiments indicate the three proposed solution methods have their own advantages over different scenarios and can calculate nearly optimal solutions in a very short time. Finally, the NCKU team has won the 2nd place award, after an oral presentation on Oct.20, 2019, in INFORMS 2019 conference at Seattle.
The NCKU team includes three 2nd-year master students Tsung-Han Wang, Yen-Wei Chen, and Yen-Tzu Yueh from the Department of Industrial and Information Management of NCKU, under the supervision of Prof. I-Lin Wang. This problem solving competition has been held annually since 2010, and the team lead by Prof. I-Lin Wang has participated it and received the awards for 7 times straightly. Prof. I-Lin Wang gave the credits to the hard-working students, who have been fully devoted themselves to the competition for an entire month with intensive works of daily meeting, model designing, and algorithm implementation. Receiving this award helps the team members to gain more confidence and broaden their views. As a result, NCKU team has also demonstrated their competitiveness and strength in conducting challenging research topics.