This thesis deals with the no-depot minmax Multiple Traveling Salesmen Problem
(MTSP), which can be formulated as follows. Given a set of n cities and k salesmen,find k disjoint tours (one for each salesmen) such that each city belongs to exactly one
tour and the length of the longest of k tours is minimized. The no-depot assumption
means that the salesmen do not start from and return to one fixed depot. The no-depot model can be applied in designing patrolling routes, as well as in business
situations, especially where salesmen work from home or the company has no central
office. This model can be also applied to the job scheduling problem with n jobs and
k identical machines.
Despite its potential applicability to a number of important situations, the research literature on the no-depot minmax k-TSP has been limited, with no reports
on computational experiments. The previously published results included the proof
of NP-hardness of the problem of interest, which motivates using heuristics for its
solution. This thesis proposes several construction heuristic algorithms, including
greedy algorithms, cluster first and route second algorithms, and route first and cluster second algorithms. As a local search method for a single tour, 2-opt search and
Lin-Kernighan were used, and for a local search method between multiple tours,
relocation and exchange (edge heuristics) were used. Furthermore, to prevent the
drawback of trapping in the local minima, the simulated annealing method is used. Extensive computational experiments were carried out using TSPLIB instances.
Among construction algorithms, route first and cluster second algorithms including
removing two edges method performed best. In terms of running time, clustering
first and routing second algorithms took shorter time on large-scale instances. The
simulated annealing could produce better solutions than the descent method, but did
not always perform well in terms of average solution. To evaluate the performance
of the proposed heuristic methods, their solutions were compared with the optimal
solutions obtained using a mixed-integer programming formulation of the problem.
For small-scale problems, heuristic solutions were equal to the optimal solution output
by CPLEX.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/5825 |
| Date | 17 September 2007 |
| Creators | Na, Byungsoo |
| Contributors | Butenko, Sergiy |
| Publisher | Texas A&M University |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Thesis, text |
| Format | 430027 bytes, electronic, application/pdf, born digital |
Page generated in 0.1352 seconds