论文标题
平衡多个旅行推销员的封闭式距离公式
Closed form distance formula for the balanced multiple travelling salesmen
论文作者
论文摘要
作为第一个贡献，MTSP是使用精确方法和两种启发式方法来求解的，其中每个路线的节点数量是平衡的。第一个启发式方法使用最近的节点方法，第二个启发式方法分配了最接近的车辆（推销员）。在欧几里得平面中的启发式方法与测试现场的比较显示出相似的溶液质量和运行时。平均而言，最近的节点解决方案约为百分之一。当不知道节点（客户），例如用于在线路由。虽然当必须多次使用一辆车辆为所有客户提供服务时，最接近的节点是可取的。第二个贡献是一个封闭式公式，描述了MTSP距离取决于车辆和客户数量。增加推销员的数量会导致欧几里得网格平面中均匀分布的节点的线性距离增长。距离增长几乎与客户数量的平方根成正比（节点）。这两个见解组合成单个公式。节点到$ n $均匀分布的随机（真实和整数）点的最小距离被得出并表示为功能关系，取决于车辆数量。这给出了理论上的基础，并且与以前的MTSP启发式方法相一致。因此，这允许计算所有预期的MTSP距离，而无需运行启发式方法。
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.
