Solving a class of time -dependent combinatorial optimization problems with abstraction, transformation and simulated annealing

While the operations research community has been working on combinatorial optimization problems for over half a century, most of the problems considered so far have constant event costs. This dissertation is dedicated to efficient solutions to a class of real-world combinatorial optimization problems whose event costs are time-dependent. A class of time-dependent problems is first identified and abstracted into a mathematical model. Based on some critical observation on the model, a problem transformation algorithm is proposed to significantly shrink the solution space while maintaining equivalency to the original problem. This problem transformation can benefit any solution strategies for this class of problems. Since the class of problems is NP-hard, a comprehensive literature survey is conducted for the prevailing meta-heuristics for solving NP-hard problems, including local optimization, genetic algorithms, simulated annealing, and tabu search. Simulated annealing is adopted as the base of this research\u27s solution strategy due to its proven convergence to global optimum when its temperature is reduced slowly enough. Comprehensive experiments are conducted to study the sensitivity of the simulated annealing algorithm to the values and strategy of its multiple parameters including initial temperature, cooling schedule, stopping criteria for the same temperature, and stopping criteria for the algorithm. More than 70 problem instances are generated to evaluate the relative performance of the proposed simulated annealing algorithm against repeated random solutions and one of the published genetic algorithms for the same problem. The size of the problem instances ranges from 4 to 200. Considered performance categories include both solution quality and running time. Experiments show that the proposed simulated annealing algorithm outperforms the published genetic algorithm by a factor of 5% to 116% while reducing the latter\u27s running time by a factor of 2 to 145