|
|
|
| Threshold Constraint Based DepthFirstSearch for BranchBound Algorithm Solving Asymmetric Traveling Salesman Problems |
| ZHU Yi, YANG Gen-ke, PAN Chang-chun |
(School of Electronic, Information and Electrical Engineering,
Shanghai Jiaotong University, Shanghai 200240, China) |
|
|
|
|
Abstract An integration approach based on heuristic strategies and branchbound algorithm was proposed for solving asymmetric traveling salesman problem. In this method, associated with each node of the branchdecision tree, a parametric solution of the relaxed assignment problem and a feasible solution obtained by patching algorithm are used to tighten the lower and upper bound. A hueristic strategy that conbines the threshold constraint based depthfirstsearch and weighted random breadthsearch is adopted to seek the optimal solution. Therefore, a feasible solution that is very close to the optimal solution can be found in comparatively short time. The computational results on data in the TSPLIB and a hot strip scheduling simulation show the efficiency of the proposed algorithm.
|
|
Received: 21 October 2007
Published: 28 October 2008
|
|
|
|
Corresponding Authors:
YANG Gen-ke
|
|
|
|
| No related articles found! |
|
|
|
|
