J. Hwang, C.S. Kang, K.R. Ryu, Y. Han, and H.R. Choi (Korea)
Planning and Scheduling, Crew Pairing Optimization, Tabu Search, Integer Programming
Methods based on integer programming have been shown to be very effective in solving various crew pairing optimization problems. However, their applicability is limited to problems with linear constraints and objective functions. Also, those methods often require an unacceptable amount of time and/or memory resources given problems of larger scale. Heuristic methods such as tabu search, on the other hand, can handle large-scaled problems without too much difficulty and can be applied to problems having any form of objective functions and constraints. However, tabu search often gets stuck at local optima when faced with complex search spaces. This paper presents a hybrid algorithm of tabu search and integer programming, which nicely combines the advantages of both methods. The hybrid algorithm has been success fully tested on a large-scaled crew pairing optimization problem for a real subway line.
Important Links:
Go Back
