A comparison of operators for solving time dependent traveling salesman problems using genetic algorithms
LEONARD J. TESTA, Albert Esterline, Gerry Vernon Dozier, Abdollah Homaifar · 2000
This paper describes which genetic operators can best solve time dependent traveling salesman problems (TDTSPs) containing up to 50 cities. We first provide an overview of the TDTSP and illustrate its relation to other scheduling and routing problems. Next we describe a genetic algorithm that implements eight common genetic operators, plus Julstrom's adaptive operator probability and Goldberg's population re-initialization mechanisms. We present the results of 280 experiments and show that one combination of these operators and mechanisms outperforms a well-known dynamic programming heuristic. An analysis of the test results indicates that hybrid solutions incorporating solution techniques for both scheduling and the traveling salesman problems may generate better results than either technique alone.