METASTRATEGY SIMULATED ANNEALING AND TABU SEARCH ALGORITHMS FOR COMBINATORIAL OPTIMIZATION PROBLEMS

Ibrahim  H.  OSMAN

This thesis deals with algorithms for combinatorial optimization problems related to location, resource allocation, routing and distribution systems. The capacitated clustering problem (CCP) is the problem in which a given set of weighted points is to be partitioned into subsets ("clusters") so that the total weight of points in each cluster is less than a given cluster capacity. The objective is to find the "center" of the cluster, and to minimize the total scatter (distance) of points from the center of the cluster to which they have been allocated. The generalized assignment problem (GAP) is the problem of finding a minimum cost assignment of a set of "Jobs" to a set of "agents" such that each job is assigned to exactly one agent and the total resource of each agent is not exceeded by the demands of the jobs assigned to him. The vehicle routing problem (VRP) involves the design of a set of minimum cost routes, originating and terminating at a central depot, so that the demands of all customers are supplied by the vehicles operating these routes. The total demand of the customers on each trip must not exceed the vehicle capacity. These problems are of practical importance in business applications, logistics and industrial management. Exact algorithms can solve only small size problems of this type. With this titration, it is important to have approximate algorithms, which can provide near optimal solutions for large‑sized problems in reasonable amount of computation time.

In this thesis, we design, develop and analyze empirically, metastrategy approximate (MA) algorithms for the above mentioned problems. A metastrategy algorithm guides and directs the operations of a subordinate method (such as local search) in order to enhance its performance and to avoid poor local optima. Recently, two MA algorithms have been proposed to solve difficult combinatorial optimization problems: Simulated annealing (SA), which is based on ideas from statistical mechanics; and tabu search (TS), which is based on the general tenets of intelligent problems solving.

A survey of exact and approximate methods for each of the above problems together with a review of the metastrategy TS and SA methodologies are given. The main contribution of this thesis is the development of the MA algorithms for solving combinatorial optimization problems. We investigate their performance and compare them against other available methods with respect to solution quality and computation time. We have developed the concept of an λ‑interchange neighborhood mechanism and used it in local search algorithms. A new cooling schedule for SA is established, which has out‑performed other cooling schedules in the literature. A new dynamic search strategy for (TS) produces better results than the classical approach for all the above problems. Also, we have designed a special data structure for the TS algorithm with which the computation time is more than halved. Computational results are presented for all the algorithms that have been developed. In cases where results for test problems are available (for example, the VRP), the new methods improve on all results reported in the literature.