Tabu search and ejection chains - application to a node weighted version of the cardinality-constrained TSP

A tabu search method based on ejection chain procedures is used to solve the cardinality-constrained Traveling Salesman Problem (TSP), a special TSP problem that determines a node simple path that maximizes the sum of weights of nodes passed by, subject to lower and upper bounds on the inclusive nodes. Short term tabu search is found to improve the power of the ejection chain, while random restarting should be used conditionally rather than unconditionally to obtain optimal results. The method has also been used to seek a profitable column in a column generation procedure for solving fractional covering problems. Computational experiments confirm the importance of advanced ejection chain rules for deriving robust solutions to complicated problems.