A hybrid heuristic algorithm for single and multi-objective imprecise traveling salesman problems

摘要

Normally, Travelling salesman problems (TSPs) are formulated with deterministic parameters and either total cost or time is minimized. In real life TSPs, the travel costs and times are not defined precisely and represented by fuzzy or rough data. Very often, in addition to single objective cost or time, both total cost and time are also minimized. These uncertain problem are difficult to optimize. In this paper, some TSPs are formulated as linear programming's problems with imprecise data and there cost, time, or both are minimized by a hybrid heuristic algorithm combining Ant colony optimization (ACO) and Genetic algorithm (GA). Here, hybrid algorithm consumes less resources such as CPU time, then the single heuristic methods. Developed algorithm is capable of solving both single and multi-objective constrained large TSPs with crisp, fuzzy and rough data. In the algorithm, different types of crossovers (multi-point crossover, order crossover, partially mapped crossover) and mutations (single point, multi point) are randomly used. Performance of the algorithm is tested against standard test problems from TSPLIB. Proposed TSPs are solved with proposed and existing algorithms and results are compared. Both the problems and algorithm are illustrated with numerical examples. Some sensitivity analyses are also presented.