  As a first contribution the mTSP is solved using an exact method and two
heuristics, where the number of nodes per route is balanced. The first
heuristic uses a nearest node approach and the second assigns the closest
vehicle (salesman). A comparison of heuristics with test-instances being in the
Euclidean plane showed similar solution quality and runtime. On average, the
nearest node solutions are approximately one percent better. The closest
vehicle heuristic is especially important when the nodes (customers) are not
known in advance, e.g. for online routing. Whilst the nearest node is
preferable when one vehicle has to be used multiple times to service all
customers. The second contribution is a closed form formula that describes the
mTSP distance dependent on the number of vehicles and customers. Increasing the
number of salesman results in an approximately linear distance growth for
uniformly distributed nodes in a Euclidean grid plane. The distance growth is
almost proportional to the square root of number of customers (nodes). These
two insights are combined in a single formula. The minimum distance of a node
to $n$ uniformly distributed random (real and integer) points was derived and
expressed as functional relationship dependent on the number of vehicles. This
gives theoretical underpinnings and is in agreement with the distances found
via the previous mTSP heuristics. Hence, this allows to compute all expected
mTSP distances without the need of running the heuristics.
