| Simulated annealing and tabu search are two search methods that have been proposed for solving combinatorial optimization problems. Since their emergence, experiments have been conducted with them in solving many types of optimization problems and have been largely successful. Approaches combining the characteristics of the two methods have been proposed, but have not yet been widely evaluated for specific problems.; In this research, tabu search as applied to a dial-a-ride problem is first investigated. The potential of applying tabu search on a parameter space, rather than the solution space as commonly practiced, is explored. The dial-a-ride problem, derived from a hospital delivery problem, is solved via a heuristic in conjunction with tabu search. A parametric objective function is formulated and is used as the search region for tabu search.; The potential of integrating simulated annealing and tabu search is investigated by solving a class of vehicle routing problem, and a class of single machine scheduling problem. The vehicle routing problem belongs to the class of classical M-vehicle routing problem. The use of a probabilistic tabu search algorithm for the solution of this type of problem is tested.; A probabilistic tabu search approach is also designed to solve a class of the single machine absolute deviation from due date problem, in which earliness and tardiness are both penalized. Finally, some conclusions are drawn from this research and directions for future research are discussed.; The conclusions from this study can be summarized as follows: (1) Tabu search, as a "metaheuristic", has the flexibility to handle a variety of combinatorial problems over different search grounds. Not only can it be effective when applied to the solution space of a problem, as a metaheuristic, it also can be applied to other types of spaces, such as parameter space and guide other heuristics in the search for optimality. This is demonstrated by the application of a dial-a-ride problem. (2) Probabilistic tabu search is very effective and efficient for solving single machine scheduling problems when combined with a good starting heuristic. (3) Probabilistic tabu search provided mixed results for the vehicle routing problems. The efficiency and effectiveness can both be improved through better design of the parameters of the algorithm. Though more experiments need to be carried out to be conclusive, nevertheless, the experiments conducted in this research revealed that probabilistic tabu search is quite promising for solving vehicle routing problems. |
