Title: A multi-objective chemical reaction optimisation algorithm for multi-objective travelling salesman problem

Authors: Samira Bouzoubia; Abdesslem Layeb; Salim Chikhi

Addresses: MISC Laboratory, Department of Fundamental Computer Science and its Applications, Constantine 2 University, Route Ain El Bey, Constantine 25017, Algeria ' MISC Laboratory, Department of Fundamental Computer Science and its Applications, Constantine 2 University, Route Ain El Bey, Constantine 25017, Algeria ' MISC Laboratory, Department of Fundamental Computer Science and its Applications, Constantine 2 University, Route Ain El Bey, Constantine 25017, Algeria

Abstract: The multi-objective travelling salesman problem (MOTSP) is a well-known combinatorial optimisation problem that belongs to the class of NP-hard problems. The MOTSP plays an important role in computing theory and in many real life applications. Unfortunately, finding efficient MOTSP solutions is still a challenging problem. That is why several methods were proposed to deal with this problem. This paper proposes a new multi-objective chemical reaction optimisation (MOCRO) algorithm to solve MOTSP. To maintain the diversity of the solutions, MOCRO uses a non-dominated sorting procedure proposed in NSGA2. Two new variants of MOCRO are proposed to deal the MOTSP. The first is MOCRO based on amount of domination (MOCRO-Dom), while the second is MOCRO based on weighted sum (MOCRO-WS). The experimental results have shown the superior performance of MOCRO-Dom and MOCRO-WS compared to NSGA2. Moreover, a comparative study between MOCRO-Dom and MOCRO-WS and the impact of the major parameters on the performance has been investigated.

Keywords: multi-objective CRO; chemical reaction optimisation; multi-objective optimisation; bio-inspired computation; multi-objective TSP; travelling salesman problem; MOTSP; non-dominated sorting.

DOI: 10.1504/IJICA.2014.066498

International Journal of Innovative Computing and Applications, 2014 Vol.6 No.2, pp.87 - 101

Received: 24 Jun 2014
Accepted: 29 Oct 2014
Published online: 31 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article