University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Distance Growth Insights for Balanced Node mTSPs

Garn, Wolfgang (2019) Distance Growth Insights for Balanced Node mTSPs In: The Operational Research Society Annual Conference OR61, 2019-09-03-2019-09-05, Canterbury, Kent, UK.

OR61-Logistics-Garn-mTSP.pdf - Version of Record

Download (829kB) | Preview


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.

Item Type: Conference or Workshop Item (Conference Paper)
Divisions : Faculty of Arts and Social Sciences > Surrey Business School
Authors :
Date : 30 June 2019
DOI : 10.13140/RG.2.2.10041.93288
Related URLs :
Additional Information : Reference for presentation is 0R61A344
Depositing User : Diane Maxfield
Date Deposited : 24 Sep 2019 10:39
Last Modified : 24 Sep 2019 10:39

Actions (login required)

View Item View Item


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