2020/01/21 by Wolfgang Garn, Garn, Wolfgang
Computer Science · Engineering · Social Sciences · #90C09 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #I.2.11 #I.2.9 #Transportation Planning and Optimization #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods #acm:90C09 #cs.DS #msc:90C09
paper · pdf · doi:10.48550/arxiv.2001.07749
10 pages, 11 figures, 3 tables, 2 algorithms
openalex publication_date 2020/01/21 · arxiv created 2020/01/30 · arxiv updated 2020/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.