Parallelisation of multiple travelling salesman problem without returning to the starting node

A method of heuristically solving the non-classic multiple travelling salesman problem is suggested, where a dramatic computational speedup is guaranteed. The salesmen covering the route must not return to the starting node in this problem. A specific genetic algorithm is the solver. To get the speedup, the nodes should be separable so that they could be divided into two or more groups. Every two adjacent groups are connected by a node called the isthmus. The respective subproblems are solved independently, in parallel, whereupon their subroutes are aggregated through the isthmuses. This shortens the aggregated route on average, although it may be slightly longer in specific cases. Such an accuracy loss is 1% to 2% in the worst case for a few hundred thousands to millions of nodes, but instead the saved computational time is counted in days, weeks, and months. The efficiency of such a parallelisation dramatically grows as more isthmuses as distinct node group separators are found. If two successive subroutes are covered by the same number of salesmen, the constraint of that every node can be visited only by one salesman is easily satisfied by correcting the subroutes at the isthmus.