WCSE

Using Parallel Clonal Selection Algorithm to Solve Multi Travelling Salesperson Problem

Abstract— This research focuses on creating a parallel Clonal Selection Algorithm (CSA), a parallel metaheuristic algorithm that used to solve the multi-Travelling Salesperson Problem (mTSP). CSA is an algorithm based on population and used in computational intelligent, including optimisation problem. After we identify the parallel potential for CSA and we construct a parallel algorithm with MPJExpress, a Message Passing Interface (MPI) library in the Java programming language. This code is verified by experiments with several datasets. We found that best cost will be reduced in line with the number of generation performed. The number of salesperson will improve the best cost achieved. The best cost is obtained with the lowest number of salesperson (2). The number of PEs is not significant in reducing the best cost. The best cost is obtained with the 2 processing elements. The execution time for the parallel version is greater than the serial time. This is because the experiments use the same execution environment. We need to explore other parallel potentials in this algorithm. This paper also shows that the best cost is obtained with the lowest number of salesperson. Furthermore, it is suggested that this proposed algorithm be used for all versions of the Vehicle Routing Problem (VRP) in future research.

Index Terms— clonal selection algorithm (CSA), parallel clonal selection algorithm, multi-travelling salesperson problem (mTSP), MPJExpres.

Ayi Purbasari
Informatics Department, Pasundan University, INDONESIA

[Download]

Cite: Ayi Purbasari, "Using Parallel Clonal Selection Algorithm to Solve Multi Travelling Salesperson Problem," Proceedings of 2016 6th International Workshop on Computer Science and Engineering, pp. 1-6, Tokyo, 17-19 June, 2016.