University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Closed form distance formula for the balanced multiple travelling salesmen

Garn, Wolfgang (2020) Closed form distance formula for the balanced multiple travelling salesmen arXiv.

[img]
Preview
Text
2001.07749(1).pdf - Author's Original

Download (453kB) | Preview

Abstract

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.

Item Type: Article
Divisions : Faculty of Arts and Social Sciences > Surrey Business School
Authors :
NameEmailORCID
Garn, WolfgangW.Garn@surrey.ac.uk
Date : 30 January 2020
OA Location : https://arxiv.org/abs/2001.07749
Uncontrolled Keywords : multiple travelling salesman problem, local search algorithm, greedy heuristic, exact method Euclidean plane distances, distance relationship
Depositing User : James Marshall
Date Deposited : 05 Jun 2020 13:07
Last Modified : 05 Jun 2020 13:07
URI: http://epubs.surrey.ac.uk/id/eprint/857090

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year


Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800