期刊
SOFT COMPUTING
卷 19, 期 3, 页码 585-596出版社
SPRINGER
DOI: 10.1007/s00500-014-1279-8
关键词
Traveling salesman problem; Max-Min ant system; Four vertices and three lines inequality
资金
- NSFC [51205129]
- Fundamental Research Funds for the Central Universities [12MS48]
The objective of traveling salesman problem (TSP) is to find the optimal Hamiltonian circuit (OHC). It has been proven to be NP complete inmost cases. The hybrid Max-Min ant system (MMA) integrated with a four vertices and three lines inequality is introduced to search the OHC. The four vertices and three lines inequality is taken as the constraints of the local optimal Hamiltonian paths (LOHP), including four vertices and three lines and all the LOHPs in the OHC conform to the inequality. At first, the MMA is used to search the approximate OHCs. Then, the local paths of adjacent four vertices in the approximate OHCs are converted into the LOHPs with the four vertices and three lines inequality to get the better approximation. The hybrid Max-Min ant system (HMMA) is tested with tens of TSP instances. The results show that the better approximations are computed with the HMMA than those with the MMA under the same preconditions.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据