A DATA GUIDED LEXI-SERACH APPROACH FOR TIME DEPENDENT TRAVELLING SALEMSMAN PROBLEM

T. A simple lexi-search algorithm that uses path representation method for the time dependent traveling salesman problem TDTSP is proposed, to obtain exact optimal solution to the problem. Then a data-guided lexi search algorithm is presented. First, the cost matrix of the problem is transposed depending on the variance of rows and columns, and then the simple lexi-search algorithm is applied. It is shown that this minor preprocessing of the data before the simple lexi-search algorithm is applied improves the computational time substantially. The efficiency of our algorithms to the problem against two existing algorithms has been examined for some TSPLIB and random instances of various sizes. The results show remarkably better performance of our algorithms, especially our dataguided algorithm.