Abstract
Abstract The mTSP is solved using an exact method and two heuristics, that balances the number of nodes per route. The first heuristic uses a nearest node approach and the second assigns the closest salesman. A comparison of heuristics with test-instances being in the Euclidean plane showed that the closest node approach delivers better solutions and a faster runtime. On average, the closest node solutions are approximately one percent better than the other heuristic. Furthermore, it is found that increasing the number of salesman or customers results in a distance growth for uniformly distributed nodes in an Euclidean grid plane. The distance growth is almost proportional to the square root of number of customers (nodes). In this context we reviewed the expected distance of two uniformly distributed random (real and integer) points. The minimum distance of a node to n uniformly distributed random (real and integer) points was derived and expressed as functional relationship. This gives theoretical underpinnings for - previously - empirical distance to salesmen growth insights.