A Hybrid Method to Search the Optimal Hamiltonian Circuit

Abstract:

The objective of the well-known travelling salesman problem (TSP) is to search the optimal Hamiltonian circuit (OHC) in a tourist map. Finding the OHC becomes hard once the number of the cities and routes in the tourist map are large. The four vertices and three lines inequality was introduced as the constraints of the local optimal Hamiltonian paths (LOHPs) included in the OHC. The chaotic depth-priority algorithm was designed by adding the computation process with the chaotic operator to verify the rationality of the LOHPs generated with the depth-priority algorithm under the inequality constraints. A lot of non-LOHPs are abandoned in the search process and the search space of the OHC is reduced greatly. The method was verified with an example and it can be applied to the network optimization, path planning, task scheduling, assembly sequence planning etc.

• Periodical: Advanced Materials Research (Volumes 605-607)
• Pages: 2149-2154
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.605-607.2149
• Online since: December 2012
• Authors: Yong Wang, Wei He, De Tian
• Keywords: Chaotic Operator, Depth-Priority Algorithm, Four Vertices and Three Lines Inequality, Optimal Hamiltonian Circuit, Traveling Salesman Problem (TSP)

References

[1] A. Rodríguez and R. Ruiz: Computers & Operations Research Vol. 39(2012), pp.1566-1576.

[2] S. J. Hu, J. Ko, L. Wey, H. A. ElMaraghy et al: CIRP Annals-Manufacturing Technology Vol. 60(2011), pp.715-733.

[3] C. Del Valle, M. Toro et al: A Scheduling Approach to Assembly Sequence Planning. Proceedings of the 5th IEEE International Symposium on Assembly and Task Planning, Besanpon, France, 10-11, July, 2003, pp.103-108.

DOI: 10.1109/isatp.2003.1217195

[4] L. Gouveia and S. Vob: European Journal of Operational Research Vol. 83(1995), pp.69-82.

[5] E. D. Klerk and C. Dobre: Discrete Applied Mathematics Vol. 159(2011), pp.1815-1826.

[6] B. Bontoux, C. Artigues and D. Feillet: Computers & Operations Research Vol. 37(2010), pp.1844-1852.

DOI: 10.1016/j.cor.2009.05.004

[7] H. Ghaziri and I. H. Osman: Computers & Industrial Engineering Vol. 44(2003), pp.267-281.

[8] Y. Q. Xu, M. Sun and Guo M S: Activation Function of Wavelet Chaotic Neural Networks. 2010 International Conference on Computing, Control and Industrial Engineering, Wuhan, China, 5-6 June, 2010, pp.408-411.

DOI: 10.1109/ccie.2010.108

[9] Y. H. Liu: Applied Mathematics and Computation Vol. 216(2010), pp.125-137.

[10] Zhou Y R: IEEE Transactions on Evolutionary Computation Vol. 13(2009), pp.1083-1092.

[11] W. N. Chen, J. Zhang, H. S. H. Chung, W. L. Zhong, W. G. Wu and Y. H. Shi: IEEE Transactions on Evolutionary Computation Vol. 14(2010), pp.278-300.

[12] Y. Wang and J. H. Liu: Robotics and Computer-Integrated Manufacturing Vol. 26(2010), pp.212-222.