A hybrid interactive random-key genetic algorithm for a symmetric multi-objective traveling salesman problem

The symmetric multi-objective traveling salesman problem (mo-TSP) is considered in this research, with solution approaches drawn from genetic algorithms and incorporating interactive user input. Initial research deals with development of a hybrid (memetic) random-key genetic algorithm (RKGA) for a symmetric single objective TSP. Then, the research is extended to a multi-objective TSP to find (approximate) weakly Pareto optimal solutions since in fact simultaneous minimization of several competing objective functions are required. Finally, a methodology is developed to incorporate user preferences interactively in terms of classification of objective functions into several classes and specification of bounds on "indifference trade-offs" with a RKGA hybridized by local search, in order to find preferred (approximate) weakly Pareto optimal solutions and a preferred (approximate) Pareto optimal solution to a symmetric mo-TSP. The random keys representation used in this research ensures that feasible tours are constructed during the application of genetic operators while the genetic algorithm approach combined with local search enhances the ability to find good solutions. Experiments are conducted using Euclidean TSP examples taken from a well-known online library to confirm the quality of the proposed approaches.