A genetic ant colony optimization based algorithm for solid multiple travelling salesmen problem in fuzzy rough environment

Research paper by Chiranjit Changdar, Rajat Kumar Pal, G. S. Mahapatra

Indexed on: 21 Mar '16Published on: 21 Mar '16Published in: Soft Computing


In this paper, a genetic-ant colony optimization algorithm has been presented to solve a solid multiple Travelling Salesmen Problem (mTSP) in fuzzy rough environment. In solid mTSP, a set of nodes (locations/cities) are given, and each of the cities must be visited exactly once by the salesmen such that all of them start and finish at a depot using different conveyance facility. A solid mTSP is an extension of mTSP where the travellers use different conveyance facilities for travelling from one city to another. To solve an mTSP, a hybrid algorithm has been developed based on the concept of two algorithms, namely genetic algorithm (GA) and ant colony optimization (ACO) based algorithm. Each salesman selects his/her route using ACO and the routes of different salesmen (to construct a complete solution) are controlled by the GA. Here, a set of simple ACO characteristics have further been modified by incorporating a special feature namely ‘refinement’. In this paper, we have utilized cyclic crossover and two-point’s mutation in the proposed algorithm to solve the problem. The travelling cost is considered as imprecise in nature (fuzzy-rough) and is reduced to its approximate crisp using fuzzy-rough expectation. Computational results with different data sets are presented and some sensitivity analysis has also been made.