Heuristic strategies for large scale traveling salesman problem, applicable to the traveling sequence optimization of industrial robots

摘要

This research work presents an approach to problem of practical concern to the optimum guidance of robot of at least two degrees of freedom but which may also have direct application in any scientific field where optimum and near optimum solutions for the traveling salesman problem and the nonsupervised classification of objects (clustering) is needed. It is shown that the optimization of the traveling pattern of die attach machine constitutes TSP. Thereafter, the developed technique is applied to generate the traveling sequence of die attach machine where all faultless integrated circuits have been premapped at previous phase of the microelectronic assembly process and their x, y coordinates are available prior to die attach. Large scale solution of the tour construction problem where existing algorithms, although ingenious, encounter problems with storage and running time for cases with more than 100 cities. One new idea is to apply particular heuristic search strategy, using a priori knowledge. The effect of using a priori knowledge has indicated significant reduction in running time and memory requirements. The improved heuristic is then used to solve clustered TSP. A novel way of looking at set of sample points as formation of binary image, formed by the trace of each point, is introduced. That made possible the introduction of image processing techniques and the use of dedicated hardware (array processor) to extract important information related to the grouping of the sample points. A connectivity analysis software package is used to aid subsequent cluster analysis. Results of several examples from medium to very large scale are presented to illustrate the developed method and its possible strengths.