Efficient tabu search implementations for asymmetric traveling salesman problems

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.