Affiliations: [a]
Bohichberia High School (H.S.), Bohichberia, Purba Medinipur, West Bengal, India
| [b]
Department of Mathematics, Mahishadal Raj College, Mahishadal Purba-Medinipur, West Bengal, India
| [c]
Department of Applied Mathematics with Oceanology and Computer Programming Vidyasagar University, Midnapore, West Bengal, India
Correspondence:
[*]
Corresponding author. Aditi Khanra, Bohichberia High School (H.S.), Bohichberia, Purba Medinipur-721649, West Bengal, India. Tel.: +91 9474978166; E-mail: [email protected].
Abstract: 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.
Keywords: Ant Colony Optimization, Genetic algorithm, travel cost, travel time
