Scientific Program > Talks by Speaker > Wang Mengke

Cumulative travelling salesman problem (CTSP) is a variant of classical travelling salesman problem (TSP) in which the objective is to minimize the sum of arrival times at customers, instead of the total travelling time. The cumulative objective arises in such important applications as humanitarian relief supply, data retrieval, and home delivery services. The CTSP is surprisingly different from the TSP: the small local changes in a tour can produce highly non-local changes. For this NP-hard combinatorial optimization problem, many papers have explored local search heuristics which combine several classical simple heuristics (usually 5 or 6!). Surprisingly, the experimental analyses and comparisons of simple heuristics for the CTSP have been neglected in the literature, especially when compared with the extensive efforts devoted to analysis of heuristics for the TSP. This paper provides detailed analyses and comparisons among various simple heuristics. Extensive computational experiments are performed on a set of instances ranging from 10 to 1000 cities, to evaluate the trade-off between the running time and solution quality. Several new heuristics based on dynamic programming paradigm are also analysed and compared with classical heuristics.