A genetic algorithm for TSP with backhauls based on conventional heuristics

Date

2007

Author

Önder, İlter

Metadata

Show full item record

A genetic algorithm using conventional heuristics as operators is considered in this study for the traveling salesman problem with backhauls (TSPB). Properties of a crossover operator (Nearest Neighbor Crossover, NNX) based on the nearest neighbor heuristic and the idea of using more than two parents are investigated in a series of experiments. Different parent selection and replacement strategies and generation of multiple children are tried as well. Conventional improvement heuristics are also used as mutation operators. It has been observed that 2-edge exchange and node insertion heuristics work well with NNX using only two parents. The best settings among different alternatives experimented are applied on traveling salesman problem with backhauls (TSPB). TSPB is a problem in which there are two groups of customers. The aim is to minimize the distance traveled visiting all the cities, where the second group can be visited only after all cities in the first group are already visited. The approach we propose shows very good performance on randomly generated TSPB instances.

Subject Keywords

Information Technology .

URI

http://etd.lib.metu.edu.tr/upload/12608726/index.pdf
https://hdl.handle.net/11511/17008

Collections

Graduate School of Informatics, Theses