MODIFIED DOUBLING UP ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM

摘要

This paper presents a modified Doubling up algorithm for the TravelingrnSalesperson Problem based on dynamic programming. The main difference of our modelrncompared with the previous ones lies in that we are concentrated on the most promisingrnsubpath from initial stage in order to decrease the computational effort. It can be applied inrnanother TSP version, but also offers much flexibility in taking advantage of special structures.rnIn this paper, we applied the Modified doubling up procedure to the special structure of TravelingrnSalesperson Problem. Preliminary numerical results show that this algorithm generates high-qualityrnsolutions compared to well-known heuristic methods, and that it can be a very promising alternative forrnfinding a solution to the TSP.