| dc.description.abstract | Combinatorial optimization problems are widely used to model various
managerial problems including scheduling, location, routing etc. Many of
these problems are known to be NP-hard. Therefore, heuristics and metaheuristics are often used to find good quality solutions to these problems
given modest execution times. In this dissertation, the traveling salesman
problem (TSP) is chosen as a representative combinatorial optimization
problem arising in managerial situations.
Tabu search is the most widely used metaheuristic to solve NP-hard
problems. A review of the literature on the application of tabu search on
the TSP shows that the literature has focused only on relatively small sized
symmetric TSP instances described on complete graphs. Further, there is
no literature on preprocessing methods for TSPs to speed up solution times
for the instance. Practical problems, like those faced by carrier and parcel
delivery companies, are known to be much larger, asymmetric, and defined
on very sparse graphs. This dissertation therefore addresses implementation
issues for tabu search implementations that would handle the demands of
such TSPs arising in practice.
The following are the major contributions of this dissertation. They
have been validated through extensive computational experiments.
(1) An efficient tabu search implementation has been developed to handle
sparse and asymmetric TSPs. This implementation exploits the sparsity
of the instance and allows the solving of instances that are seven
times the size of the largest instances seen to be solved in the literature
within reasonable time.
(2) Three preprocessing schemes have been constructed for the TSP. These
schemes reduce the density of the graph underlying a TSP instance,
which allows tabu search implementations like in (1) to solve large TSP
instances in reasonable time without compromising on the solution
quality.
(3) Three methods to construct sets of good quality diverse initial solutions
have been constructed for multi-start tabu search implementations for
the TSP. | en |
