Minimization of the Total Traveling Distance and Maximum Distance by Using a Transformed-Based Encoding EDA to Solve the Multiple Traveling Salesmen Problem

Abstract EN

Estimation of distribution algorithms (EDAs) have been used to solve numerous hard problems.

However, their use with in-group optimization problems has not been discussed extensively in the literature.

A well-known in-group optimization problem is the multiple traveling salesmen problem (mTSP), which involves simultaneous assignment and sequencing procedures and are shown in different forms.

This paper presents a new algorithm, named EDAMLA, which is based on self-guided genetic algorithm with a minimum loading assignment (MLA) rule.

This strategy uses the transformed-based encoding approach instead of direct encoding.

The solution space of the proposed method is only n!.

We compare the proposed algorithm against the optimal direct encoding technique, the two-part encoding genetic algorithm, and, in experiments on 34 TSP instances drawn from the TSPLIB, find that its solution space is n!n-1m-1.

The scale of the experiments exceeded that presented in prior studies.

The results show that the proposed algorithm was superior to the two-part encoding genetic algorithm in terms of minimizing the total traveling distance.

Notably, the proposed algorithm did not cause a longer traveling distance when the number of salesmen was increased from 3 to 10.

The results suggest that EDA researchers should employ the MLA rule instead of direct encoding in their proposed algorithms.