# Genetic algorithm for travelling salesman problem with multiple salesmen

I am trying to produce a good genetic algorithm for the travelling salesman problem with multiple salesmen. In other words, assume we are given a graph $G$ with $n$ vertices and $k$ edges connecting them, each edge $i$ having a weight $c_i$. $G$ is symmetric, ie. all the edges can be traveled in both directions. We also have $m$ travelers. Assume also that all travelers start from the same, given, node. (this one node thus part of every subgraph, all others belong to unique graphs.) Assume that the optimal path, ie, the path with smallest sum of edge weights, for a given graph $H$ is $\sum H.$

The problem is that we need to find a partition of $G$ into $m$ subgraphs such that the sum $\sum_{j} (\sum G_j)$ is minimized.

I want to use a genetic algorithm to solve this. Here are the states I use:

1. Use Floyd-Warshall's Algorithm to discover the shortest paths from every node to every other node.
2. Denote the partition as $(a_1,a_2...a_n)$ where $a_i=j$, if $i$th node belongs to the $j$th subgraph. (This excludes the starting node) Generate $v$ partitions, assigning the nodes randomly. This leads to vector of partitions $P^* = (P_1,P_2...,P_v)$
3. Calculate the fitness of each partition. This means that we calculate, using the known shortest paths for every pair of nodes, the $\sum_{j=1}^m (\sum G_j), \ \forall P \in P^*$.
4. Using the fitness, select $\frac{v}{2}$ best partitions and breed them, ie. select two partitions $((a_1,a_2...a_n),(b_1,b_2...b_n))$ $v$ times, select randomly $\frac{n}{2}$ (denote these as $A$) of the elements of the first and generate new partition $(d)$, where $d_i =\begin{cases}a_i, & \text{if$a_i \in A$} \\b_i, & \text{if$a_i \notin A$} \\ \end{cases}$