Parallelisation of multiple travelling salesman problem without returning to the starting node

Vadim V. Romanuke

International Journal of Operational Research, 2025, vol. 53, issue 1, 1-34

Abstract: A method of heuristically solving the non-classic multiple travelling salesman problem is suggested, where a dramatic computational speedup is guaranteed. The salesmen covering the route must not return to the starting node in this problem. A specific genetic algorithm is the solver. To get the speedup, the nodes should be separable so that they could be divided into two or more groups. Every two adjacent groups are connected by a node called the isthmus. The respective subproblems are solved independently, in parallel, whereupon their subroutes are aggregated through the isthmuses. This shortens the aggregated route on average, although it may be slightly longer in specific cases. Such an accuracy loss is 1% to 2% in the worst case for a few hundred thousands to millions of nodes, but instead the saved computational time is counted in days, weeks, and months. The efficiency of such a parallelisation dramatically grows as more isthmuses as distinct node group separators are found. If two successive subroutes are covered by the same number of salesmen, the constraint of that every node can be visited only by one salesman is easily satisfied by correcting the subroutes at the isthmus.

Keywords: multiple travelling salesman problem; route length; genetic algorithm; parallelisation; isthmus; node group separability. (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=146110 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:53:y:2025:i:1:p:1-34

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().