Approaches to the Travelling Salesman Problem Using Evolutionary Computing Algorithms
Jyh-Da Wei · InTech eBooks · 2008
Genetic algorithms and genetic local search are population based general-purpose search algorithms that have been examined to search efficiently for the near-optimal solutions to certain combinatorial optimization problems, such as the constraint satisfaction problem (Marchiori & Steenbeek, 2000), flowshop scheduling problem (Arroyo & Armentano, 2005), constraint minimum spanning tree problem (dMST) (Zeng & Wang, 2003), and travelling salesman problem (TSP) (Freisleben & Merz, 1996). Notably, these optimization problems usually have critical requirements that have forced researchers to develop new genetic operators. For example, for the dMST we have an upper bound on the node degrees and for the TSP we require that each city be visited exactly once. Previous results made use of specialized genetic operators to enhance the GA and GLS. Alternatively, we have presented another approach to the TSP using evolutionary computing algorithms, i.e., the priority-based encoding method in conjunction with greedy