A Heuristic for Solving the M-salesmen (M $>$ 1) Travelling Salesmen Tour Problem with Different Home Stations

Santosh Kumar OAM^1,*, Elias Munapo² and Trust Tawanda³

¹Department of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Vic 3000, Australia
²Department of Decision Sciences, North West University, Mafikeng 3725, South Africa
³Department of Statistics and Operations Research, National University of Science and Technology, Bulawayo, Zimbabwe
E-mail: Santosh.Kumarau@gmail.com; emunapo@gmail.com; trust.tawanda@nust.ac.za
*Corresponding Author

Received 11 March 2026; Accepted 11 April 2026

Abstract

This paper presents a heuristic for solving a M-salesmen problem, when M $>$ 1, and these M-salesmen have different home stations, from where their tour will begin and end. Once again, the index restricted shortest connected tree approach has been applied to identify two independent index restricted connected paths, which have been interpreted as equivalent to the required tours for M-salesmen. Situation of more than one salesman is a natural extension that can arise in all industrial and commercial situations where the salesman tours have applications.

Keywords: M-salesmen problem, index restricted path, different home station for each salesman, same home station for all salesmen.

1 Introduction

The traveling salesman problem (TSP) is a well-known classical problem in graph theory. It deals with determination of the salesman tour starting from a home city and after visiting all other cities once returns to the home city in minimum cost or time. The round path has many real-life applications in many industrial and business situations. Many of these applications have financial consequences. Due to these applications and financial implications, the TSP has attracted a lot of attention from researchers, see [1–7]. Many TSP approaches require excessive computational time, which in many cases is a function of the number of nodes in the network. For some approaches the computational load increases exponentially, and the approach does not remain meaningful to provide a solution in a reasonable time [8]. It is for this reason; the travelling salesman problem has been classified as a NP Hard problem, see [1, 2, 9]. However, the computational load for some recent approaches for the travelling salesman problem did not grow exponentially, and therefore, a question about NP Hard classification of the TSP has been raised in [4]. The question is: “Is the travelling salesman problem really NP Hard?”. A binary formulation to the TSP has been developed and solved in polynomial time in [3]. In [10] an equivalence has been established between the index restricted connected tree and the TSP. In these recent approaches, the computational load does not increase exponentially as a function of the number of cities involved in the salesman problem.

In many cases, a region to be covered by the salesman tour may be large or time required by the salesman to visit all stations may be excessive for one person to undertake a complete tour of all the cities. In that situation, a conventional TSP may not be the best answer, and a natural consequence will be to distribute the salesman’s work among more than one person. Hence a need arises for consideration of M-salesmen (M $>$ 1) travelling salesmen, which is addressed in this paper for M $=$ 2. The approach can be easily extended to M $>$ 2. For two salesmen, we need to find 2 independent routes for the 2-salesmen such that each place is visited once by any one person, and after visiting all cities by at least by one salesman, these 2-salesmen return to their respective home cities. The home-city may be a specific city for both salesmen, or it may be a different city for each salesman is a matter of the network configuration and characteristics of the situation. For example, if one deals with a large metropolitan city with several department stores and more than one warehouse, the delivery persons will be required to start and return to different warehouse, representing home cities for those salesmen. However, if there is only one warehouse, all delivery persons will commence their journey and return to the same warehouse, it will be a situation when both salesmen have the same city representing their home city.

In this paper, we consider 2-salesmen and a known different home city for each salesman. As pointed out above, a possible variant of the above situation will be that two-salesman may operate from only one city as their home city, and it will be investigated in some other publication.

Here, we consider that two-salesmen covering a given geographic area represented in the form of a network and salesperson start from two separate home cities and return to their home cities after visiting all stations such that all cities are visited by at least one salesmen and cities are distributed among these two salespersons in an equitable form. For example, if there are odd number of stations to be visited, it is natural that one salesman will end up getting one extra station compared to the other salesman, whereas when the number of visiting stations is even, both are given an equal number of visiting stations. Once again, we approach the two-salesmen problem as an index restricted connected tree considered earlier in [4, 11]. We attempt the problem of obtaining two separate index restricted connected trees of a graph, such that:

I. Each node is a member of one and only one tour, not both.

II. All nodes of the given network are distributed in two independent trees, which forms the required salesman tour.

III. The sum of two trees is minimum.

IV. The given network is reduced to node index restricted connected paths, which have alternative interpretation of salesman tours for the two salesmen.

The problem of developing two independent connected trees of a graph is discussed in Section 2. The paper has been organized into 7 sections. Section 2 presents two independent disconnected trees, which are required for finding two-salesmen tours, when each node is visited by one salesman and tour is of minimum length. Section 3 describes the reconstruction of the given network for finding two independent index restricted paths. The proposed heuristic is presented in Sections 4 and 5 deals with a few numerical illustrations to explain steps of the proposed heuristic. Section 6 presents a binary formulation of the 2-salesmen problem to illustrate that the binary modelling can become very complex and demanding for larger networks. Finally, the chapter is concluded in Section 7.

2 Two Independent Disconnected Trees of a Graph

The minimum connected tree of a network is a known graph theory problem, and several methods exist for obtaining the minimum connected tree of a given network, see [12]. However, an alternative approach to find the connected tree of a graph has been discussed in [13]. For an N Node network, a minimum connected tree is comprised of (N $-$ 1) number of links connecting all nodes without forming any loop. The authors in [13] viewed the connected tree problem as a dynamic program and initiated the search by selecting one link at a time from a known node and obtained the required minimum spanning tree of the given network in (N $-$ 1) iterations. After finding an initial link, idea is to add one link at a time such that the selected links form the shortest connected tree of the nodes formed by those selected links. Each iteration adds one more link and the search come to an end after (N-1) iterations. Here we are looking for two disconnected trees, each tree is built around the given specified node, representing the home city for these salespersons. Consider a network

G (N, L), where the node set is N = 1, 2, \dots, (N - 1), N .

The link set L has elements C_{i j}, where i, j = 1, 2, \dots, N, i \neq j .

Let the specified nodes representing the home cities for the 2-salesmen be represented by the nodes 1 and N. Since each tree is going to be independent of each other, the total number of links in the two independent trees will be given by (N $-$ 2). If the number N is even, each tree will have $\frac{(N - 2)}{2} = k$ , $number$ of links. However, if N is an odd number, we let $\frac{(N - 3)}{2} = k$ , number of links, where one of the two trees will have one link more in the tree compared to the other, i.e., one tree will have k number of links and the other will have $(k + 1) number$ of links. These two independent trees will be two disconnected trees and the required salesmen tours.

3 Reconstruction of the Given Network and Mathematical Support

In the reconstructed network, the node representing the home city is duplicated, i.e., the ‘n-node’ network is reconstructed as a network comprised of (n $+$ 2) number of nodes. Assuming the home cities are represented by nodes 1 and n, their duplicate nodes are represented by nodes 1^′ and n^′. The idea is to find an index restricted independent path between the nodes 1 and 1^′ and the other index restricted path between the nodes n and n^′. These two paths have no node common to them. The index of the nodes 1, 1^′, n, and n^′ is restricted to one, as the path will start from one of these nodes and it will end at the other node. The index of all other nodes on the path is restricted to 2. Each path will be comprised of (k $+$ 1) number of links when ‘n’ is even and when ‘n’ is odd, one tree will have one more link in the path compared to the other path. This idea has been discussed in detail in [10], where it has been established that the index restricted path between the home city and its duplicate is equivalent to the travelling salesman tour.

Shortest connected tree is obtained by the greedy approach by selecting the minimum links in such a way that the selected links never develop a sub cycle as discussed in [13]. The index restricted connected network was a modification of the shortest connected tree, where index of each node is less than or equal to 2, which has an alternative interpretation that it provides a path joining two nodes (starting and end nodes) passing through all other nodes of the given network [11]. Therefore, when a link connects the origin and the end node, it becomes a salesman tour, hence gives an upper bound to the salesman tour as discussed in [10]. However, Garg and Kumar in [13] obtained the shortest connected graph by initiating the search from any minimum link and after that in each iteration added one more link in such a way that every additional link forms a minimum connected network of the selected links. These two ideas have been applied to the M-salesman travelling salesmen problem and search becomes one directional as will be explained in the numerical illustrations.

When we start from the home nodes, we select the minimum link from this node, thus when we have two home nodes, one link at each starting home city with index equal to 1 can be selected. However, the origin node has index restriction 1, therefore, it is saturated with respect to its index restricted to 1. The only possibility is to consider another node of the recently selected link. However, the node we just added a link is also saturated by the index restriction, which is $<=$ 2, and it results in only one choice, i.e., add one link to the node of the latest added link. Each selection saturates one node and creates a new node where a new link can be added. Therefore, following the method in [13, 14] for the M-salesman tour, we have only one option open to us and method discussed in the next section is based on this idea, which becomes a single direction search. Details are discussed in Section 4.

4 Method for Finding Two Independent Index Restricted Paths

We have assumed that the two home stations are represented by the nodes 1 and N from where the two-salesmen will start and end their tours. Along with the duplicated nodes, all links emanating from the home city are also duplicated. Among the duplicated links, only one link has an interpretation as the other link is a virtual link. Therefore, when a selected link is from a set of duplicated links, the other link is set equal to infinity. It ensures that a link and its duplicate are not basic (member of the index restricted path) at the same time. In the reconstructed network, number of nodes will be increased by two, and the number of links is increased by the number of links emanating from nodes representing the home cities. Total number of links forming paths joining the nodes 1 and 1^′ and the path joining the nodes N and N’ will be given by N in a N node network.

The two independent connected paths joining the nodes 1 and 1^′ and the other path joining nodes N and N^′ will become two independent tours when nodes 1 and 1^′ is over imposed and similarly the path joining nodes N and N^′ will form the second salesman tour, when nodes N and N^′ are over imposed. These two tours will be two disconnected tours for the two salesmen.

4.1 Steps for Obtaining Two Disconnected Trees are as Follows

Step 0: The initial step:

1. Consider that the given network is represented by $G (N, L)$ , where N is the node set and L is the link set. From the given network, reconstruct a new network denoted by $G^{'} (N^{'}, L^{'})$ where the node set has two more nodes representing duplicate of the home city for the two salesman and the link set has all given links and duplicated links emanating from the home stations for the two salesmen. It means in addition to nodes 1 and N, we have two more nodes, i.e., nodes 1^′ and N^′. Similarly, number of links will be added by the duplicate links from nodes 1 and N.

2. Check the number of nodes in the network $G^{'} (N^{'}, L^{'})$ and find the number of links in the two independent index restricted paths joining the nodes 1 and 1^′ and the nodes N and N’. Let this number be represented by 2K, when the number of nodes in the given network $G (N, L)$ , is even; i.e., (N/2) $=$ K and when it is odd, the total number of links will be (2K $+$ 1), one set will end up getting one extra link at the end, i.e., one path will have K links and the other will have (K $+$ 1) number of links, when $K = \frac{(N - 1)}{2}$ .

3. Introduce a link counter r, which initially has a zero value initially, i.e., r $=$ 0.

Step 1: The two home cities are known, let us assume they are represented by nodes 1 and N. In general, they can be any two specified nodes. Let us represent the two corresponding paths between the nodes 1 and 1^′ and between the nodes N and N^′ by $P_{1}^{K}$ and $P_{N}^{K}$ , respectively. The subscripts 1 and N represent the path from node 1 to 1^′ and the path from N to N^′ respectively. K is the number of selected links on each of these two paths.

Initially there is no link, only nodes are included, i.e., the nodes representing home cities, which are the nodes 1 and N, being home stations for the wo salesmen. Node sets of the two index restricted paths be represented by ${N_{1}} and {N_{N}} and the link sets be represented by {L_{1}} and {L_{N}}$ , respectively.

These paths will have links such that:

${P_{1}^{K}} \cap {P_{N}^{K}} = {N_{1}} \cap {N_{N}} = {L_{1}} \cap {L_{N}} = \emptyset$
$(No common link or a node)$	(1)
$2 K = (N) for even N, and 2 K = (N + 1) for odd N .$	(2)

The condition (1) represents that nodes and links are not common in two paths, and the condition (2) will decide when to stop adding more links to the paths.

Note that we are looking for an index restricted path with index $<=$ 2. This gives only one choice from the starting node; we move to nearest node in the feasible direction. If search comes to an end, we use the index balancing theorem to explore other possible directions.

Step 2: Initially each tree contains a node and no link. Iteration one will select one link for each path, as follows:

For the tree $T_{1}^{1} {\min_{1, j \neq {N_{1} \cup N_{T}}} (C_{1 j})}$ and tree $T_{N}^{1} {\min_{N, i \neq {N_{1} \cup N_{T}}}$ $(C_{i N})} .$ Let these two trees be:

$T_{1}^{r = 1} = {C_{1 l}} and T_{n}^{r = 1} T_{N} {C_{l N}}$ , which are the minimum links.

Set the counter r $=$ r $+$ 1, and if r $+$ 1 $<$ K, go to step 3, when r $+$ 1 $=$ k, go to Step 4.

Step 3: Add one more link to each tree by adding a min with respect to the nodes of the selected link in the trees $T_{1}^{1}$ and the tree $T_{N}^{1}$ forming the trees $T_{1}^{2}$ and $T_{N}^{2}$ as given by the Equation (3).

T^{2} = {\min_{1, j, j \neq {N_{1} \cup N_{T}}} (C_{l j} + T_{1}^{1}); \min_{i N, i, i \neq {N_{1} \cup N_{T}}} (C_{i N} + T_{N}^{1})}

(3)

In general, the iterative equation will be represented by (4), given below:

T^{K} = {\min_{feasible i and j} (C_{i j} + T_{1}^{K - 1}); \min_{fasible i, j} (C_{i j} + T_{N}^{K - 1})}

(4)

Each iteration results in adding one more link to each existing two trees. For a network with even number of nodes, the iteration will end when K $=$ (N)/2 and for N being odd, the iteration will end when K $=$ (N-1)/2 and one remaining link will be added to one of the trees which corresponds to a minimum.

Repeat the step given by Equation (4) and obtain $T_{1}^{K}, T_{N}^{K}$ for the network with even number of nodes. For the odd number of nodes, the last remaining link will either be added to $T_{1}^{K}$ or $T_{N}^{K}$ which corresponds to the minimum.

Step 4: Find the number of links in the sets $T_{1}$ and $T_{N}$ . If this number is less than $(n_{1} - 1)$ , find the minimum link to join the existing link in the set to form a minimum connected tree.

5 Numerical Illustrations

5.1 Illustration 1

For an Illustration of the formulation discussed in Section 4, where the two salesmen start from the nodes 1 and 6. Let us label them as salesman 1 and 2. Since number of nodes N $=$ 6, the number of nodes in the reconstructed network will be N $+$ 2, i.e. 8. It means the total number of links forming two paths will be equal to 6. Each node will be visited either by the salesman 1 or by the salesman 2 but not by both. Network is given in Figure 1 and the link weights are given in Table 1.

Figure 1 Six node networks.

Table 1 Link weights, $C_{i j}, i, j = 1, 2, 3, 4, 5, 6$

$C_{i j}$	1	2	3	4	5	6
1	–	11	9	9	15	16
2	11	–	14	10	10	15
3	9	14	–	6	13	11
4	9	10	6	–	9	10
5	15	10	13	9	–	8
6	16	15	11	10	8	–

The reconstructed network will become a network as shown in Figure 2, where five links have been duplicated (in red) from node 1^′. Similarly, reconstruction will also have five more duplicated links from the node 6^′. However, these five links are not shown in Figure 2, as it will make Figure 2 unwieldy. Link-length data for the reconstructed network in Figure 2 will be as shown in Table 2.

Figure 2 Reconstructed network of Figure 1

Table 2 Reconstructed 8-node network after adding two nodes and link

$C_{i j}$	1	1^′	2	3	4	5	6	6^′
1	–	0	11	9	9	15	16	16
1^′	0	–	11	9	9	15	16	16
2	11	11	–	14	10	10	15	15
3	9	9	14	–	6	13	11	11
4	9	9	10	6	–	9	10	10
5	15	15	10	13	9	–	8	8
6	16	16	15	11	10	8	–	0
6’	16	16	15	11	10	8	0	–

Initially, the index restricted path has no links, but it has only two nodes representing the home stations for the two salesmen, i.e.,

P_{0 links} {nodes 1, 6}

Iteration 1 Now we will add a link from node 1 and a link from node 6. Arranging links from nodes 1 and 6 in increasing order, we have:

From node 1: $\min_{j \neq 6} {9 (c_{13})$ ,9 $(c_{14}), 11 (c_{12}), 15 (c_{15})}$ and

from node 6: $\min_{i \neq 1} {8 (c_{56})$ , 10 $(c_{46})$ , 11 $(c_{36})$ , 15( $c_{26})}$

$P_{links = 2} = [T_{1} {9 C_{13}} o r {9 C_{14}}, T_{6} = {8 C_{56}}] = [(9 C_{13}, 8 C_{56})}]$ or $[(9 C_{14}, 8 C_{56})}]$

Since the (1,3) or (1,4) has been selected, the consequence will be changed to:

That duplicate link-lengths will be changed to:

$C_{i j}$	1	$1^{'}$	2	3	4	5	6	$6^{'}$
1^′	0	$-$	11	$\infty$	9	15	16	16

$C_{i j}$	1	1^′	2	3	4	5	6	6^′
1^′	0	-	11	9	$\infty$	15	16	16

And similarly, since the link (5,6) has been selected, it will change the last row:

$C_{i j}$	1	1^′	2	3	4	5	6	6^′
6^′	16	16	15	11	10	$\infty$	0	–

Iteration 2

Note that nodes 1 and 6 for two paths to be determined will have an index restricted to 1, for the minimum connected path, we need to investigate links either from nodes 3 and 5, for the alternative 1 or links from nodes 4 and 5, for the alternative 2.

Alternative 1: Links in increasing order from node 3: ${6 c_{34},}$

Alternative 2: Links in increasing order from node 4: ${6 c_{43}}$

Iteration 2: Path from the node $1 = \min_{3} {9 (1, 3) + 6 (3, 4)}$ or $\min_{4} {9 (1, 4) + 6 (4, 3)} = 15 {(1, 3), (3, 4)}$ or $(1, 4), (4, 3)}$

The path for the salesman starting from node 6, we need to find links in increasing order reaching the node 5, which are: 15 $c_{52}$

T_{6} = \min_{5 or 6} {8 (6, 5) + 15 (5, 2)} = 23 {(6, 5), (5, 2)} .

Hence two independent minimum connected paths are: $T_{1} = 15 {(1, 3), (3, 4)}$ , or ${(1, 4), (4, 3)}$ and $T_{6} = 23 (6, 5), (5, 2)}$ .

P_{links = 4} = [T_{1} {15 {(1, 3), (3, 4),} or {(1, 4), (4, 3)} and

T_{6} {23 {(6, 5), (5, 2)}}}] .

Iteration 3: Since the two paths have 4 links, the next link must take us to destination node 1^′ and 6^′.

The required salesmen tours are: For salesman $1 - > 4 - > 3 - > 1^{'}$ or $1 - > 3 - > 4 - > 1^{'}$ and cost will be $9 + 6 + 9 = 24$ .

Tour for the salesman 2 will be $T_{6} = 6 \to 5 \to 2 \to 6^{'}$ and its cost will be $8 + 10 + 15 = 33$ .

It means the salesman starting from the node 1 will visit the node 4, from 4 will visit the node 3 and from the node 3 will return to the home city 1 or from 1 visit 3, from 3 visit 4 and from 4 visit 1.

Similarly, the salesman starting from the node 6 will visit the node 5 and from 5 visit the node 2 and return home to node 6. These two independent tours are shown in Figure 3.

Figure 3 Two independent tours for the two salesmen are shown in red.

5.2 Illustration 2

Consider the network with odd number of nodes given in Figure 4 and link lengths as given in Table 3.

Consider a 7-node network, where once again nodes 1 and 7 will be duplicated and all links emanating from these nodes will also be duplicated. Thus, the total number of nodes in the reconstructed network will be 9 and number of links will increase by 6 as only three links emanate from node 1 and three links from node 7. Link data is given in Table 3 and that of the reconstructed network will be as given in Table 4.

Figure 4 7 node network.

Table 3 Link length data

i\j	1	2	3	4	5	6	7
1	–	10	$\infty$	1	5	$\infty$	$\infty$
2	10	–	9	$\infty$	8	10	$\infty$
3	$\infty$	9	–	3	$\infty$	4	$\infty$
4	1	$\infty$	3	–	$\infty$	5	4
5	5	8	$\infty$	$\infty$	–	7	3
6	$\infty$	10	4	5	7	–	8
7	$\infty$	$\infty$	$\infty$	4	3	8	–

Table 4 Link data for the reconstructed network

i\j	1	1^′	2	3	4	5	6	7	7^′
1	–	0	10	$\infty$	1	5	$\infty$	$\infty$	$\infty$
1^′	0	–	10	$\infty$	1	5	$\infty$	$\infty$	$\infty$
2	10	10	–	9	$\infty$	8	10	$\infty$	$\infty$
3	$\infty$	$\infty$	9	–	3	$\infty$	4	$\infty$	$\infty$
4	1	1	$\infty$	3	–	$\infty$	5	4	4
5	5	5	8	$\infty$	$\infty$	–	7	3	3
6	$\infty$	$\infty$	10	4	5	7	–	8	8
7	$\infty$	$\infty$	$\infty$	$\infty$	4	3	8	–	0
7’	$\infty$	$\infty$	$\infty$	$\infty$	4	3	8	0	–

Note that the number of nodes is odd in this illustration. One salesman will visit 2 cities and the other will visit 3 cities, two cities 1 and 7 being their home cities. It is not known who will visit 2 and who will visit 3 cities. Let us once again call home cities as the nodes 1 and 7 and represent their trees by $T_{1}$ and $T_{7}$ , and Paths by $P_{1}$ and $P_{7}$ . Initially, $P_{0} = {1, 7}$ . No link has been selected.

Iteration 1: The minimum link from node 1 is link (1,4) of length 1. The minimum link from node 7 is link (7,5) of length 3.

Iteration one gives:

P_{2} = [{T_{1} = 1 (c_{1, 4}), T_{7} = 3 (c_{7, 5})}]

Iteration 2: The minimum link from node 4 is the link (4,3), i.e., 3 $c_{43}$ , resulting in $T_{1} = 1 c_{14} + 3 c_{43} = 4 {c_{14}, c_{43}}$ .

T_{7} = {3 c_{75} + 7 c_{56}} = 10 {(7, 5), (5, 6)}

Therefore, we have

P_{4} = [{T_{1} = 4 {(1, 4), (4, 3)} T_{7} = 10 {(7, 5), (5, 6)}}]

Now we need minimum from node 3, which is link (3,2), length 9 and the minimum from 6, is the link (6,7^′) of length 8. Therefore,

P_{6} = [{T_{1} = 13 {(1, 4), (4, 3), (3, 2)}; {T_{7} = 18 (7, 5), (5, 6), (6, 7^{'})}}]

The final link will be added to the tour 1 and the required tour will be:

P_{7} = [{T_{1} = 20 {(1, 4), (4, 3), (3, 2), (2, 1^{'})};

{T_{7} = 18 (7, 5), (5, 6), (6, 7^{'})}}]

Two independent paths will be:

From $1 - > 4 - > 3 - > 2 - > 1^{'}$ and from $7 - > 5 - > 6 - > 7^{'}$ . And their total lengths will be 20 and 18 respectively. The two tours will be $1 - > 4 - > 3 - > 2 - > 1$ and $7 - > 5 - > 6 - > 7$ .

6 Binary Model for the 2-salesman Model

A binary model for one salesman problem has been presented in [15]. For convenience and easy to understand difficulties, we develop a binary model for the illustration 5.1 discussed above.

Since the two home stations are represented by nodes 1 and 6, it means that one round route will start and fineish from node 1 and the other will start and finish at node 6. Each salesman will return to home city after visiting two stations. Each link in the network is represented by a variable $x_{i j} = {\begin{matrix} 1 \\ 0 \end{matrix} 1 if the link is included in the salesman tour, else it is 0$ .

The mathematical model will be:

The Objective function will have 14 terms, i.e. excluding the link joining the two home cities for the two salesmen i.e., $C_{16}$ . It will be given by:

Min Z = 11 x_{12} + 9 x_{13} + \dots + 16 x_{15} + \dots + 8 x_{56}

(5)

For the salesman tour, each node will have index 2, i.e., one link to enter that node and another link to exist that node.

However, note that links entering node 6 will not be forming the part of the tour for the salesman 1 and similarly the links starting from node 1 will not form the part of the tour for the 2nd salesman. This will give rise to 6 constraints as follows:

\begin{matrix} Node 1 : x_{12} + x_{13} + x_{14} + x_{15} = 2 \\ Node 2 : x_{12} + x_{23} + x_{24} + x_{25} + x_{26} = 2 \\ Node 3 : x_{13} + x_{23} + x_{34} + x_{35} + x_{36} = 2 \\ Node 4 : x_{14} + x_{24} + x_{34} + x_{45} + x_{46} = 2 \\ Node 5 : x_{15} + x_{25} + x_{35} + x_{45} + x_{56} = 2 \\ Node 6 : x_{26} + x_{36} + x_{46} + x_{56} = 2 \end{matrix}

(6)

Each tour will be comprised of 3 links, i.e., the home city and two more nodes will be visited by these two salesmen. This constraint for the salesman 1 will be given by:

x_{12} + x_{13} + x_{14} + x_{15} + x_{23} + x_{24} + x_{25} + x_{34} + x_{35} + x_{45} = 3

(7)

Similarly for the salesman 2, the constraint will be:

x_{23} + x_{24} + x_{25} + x_{26} + x_{34} + x_{35} + x_{36} + x_{45} + x_{46} + x_{56} = 3

(8)

A constraint for the total number of links in two tours will be

$x_{12}$	$+ x_{13} + x_{14} + x_{15} + x_{23} + x_{24} + x_{25} + x_{26} + x_{34}$
	$+ x_{35} + x_{36} + x_{45} + x_{46} + x_{56} = 6$

And all $x_{i j}$ will be 0 or 1.

An intermediate node cannot belong to both tours, will be reflected by the following two link paths:

Node 2: x_{12} + x_{26} \leq 1

Node 3: x_{13} + x_{36} \leq 1

Node 4: x_{14} + x_{46} \leq 1

Node 5: x_{15} + x_{56} \leq 1

Similarly, three link paths will have to satisfy the following constraints:

\begin{matrix} x_{12} + x_{23} + x_{36} \leq 2 \\ x_{12} + x_{24} + x_{46} \leq 2 \\ x_{12} + x_{25} + x_{56} \leq 2 \\ x_{13} + x_{34} + x_{46} \leq 2 \\ x_{13} + x_{35} + x_{56} \leq 2 \\ x_{14} + x_{45} + x_{56} \leq 2 \end{matrix}

(9)

Since an intermediate node cannot belong to both tours, the binary model will become very unwieldy for larger networks, and it is not going to be a viable method to find 2-salesmen tours.

7 Concluding Remarks

The proposed heuristic is simple and will be able to identify two salesmen tours when their home stations are represented by different cities. This approach can easily manage larger networks. The binary approach becomes clumsy with increase in the number of nodes in the network.

It is still a challenge to have two-salesmen tours when they have the same station as their home city. Further the case for M-salesmen when M $>$ 2 remains a challenge, and they will be investigated in subsequent publication.

Coding for this approach will allow experiments on lager networks and for measuring efficiency associated with this approach.

References

[1] D.L. Applegate, R.E. Bixby, V. Chvatal, W.J. Cook, The travelling salesman problem: A computational study, Princeton University Press, 2011.

[2] E. Alanzi, M. Menai, Solving the travelling salesman problem with machine, Artificial Intelligence Review, 58:267, https://doi.org/10.1007/s10462-025-11267-x, 2025

[3] E. Munapo, Development of a dummy guided formulation and exact solution method for TSP, Eastern-European Journal of Enterprise Technologies, pp12–19, 2020.

[4] S. Kumar, E. Munapo, Innovative ways of developing and using specific purpose alternatives for solving some hard combinatorial network routing and ordered optimization problems, Applied Math, 4, pp. 791–805, https://doi.org/10.3390/appliedmath4020042, 2024.

[5] T. Tawanda, P. Nyamgure, S. Kumar, E. Munapo, Modified TANYAKUMU labelling method to solve equality generalized travelling salesman problem, Proc. of the 5th International conference on Intelligent Computing and Optimization 2022 (IOC2022) Eds., Vasant P et al., Lecture notes in Network Systems, Vol. 569, pp. 926–935, 2022 Springer Nature.

[6] T. Tawanda, P. Nyamgure, S. Kumar, and E. Munapo, A labelling method for the travelling salesman Problem, Applied Sciences Vol. 13, 6417 (http://doi.org/10.3390/app13116417), 2023.

[7] T. Tawanda, S. Kumar, E. Munapo, P. Nyamgure, Specified Number of nodes Travelling salesman Problem, Springer Book Chapter in: Advances in Mathematics for Engineering Sciences, (Editor) Mange Ram, Shristi Kharola, and Akshay Kumar, IBBN 978-3-031-95692-8, Switzerland, pp. 47–63, 2025.

[8] R. E. Bellman, S.E. Dreyfus, Applied Dynamic Programming, Princeton University Press, 1962.

[9] G.L. Nemhauser, L.A. Wolsey, Integer and combinatorial optimization, Inter Science series in Discrete Mathematics and optimization, John Wiley & Sons, 1988.

[10] S. Kumar, E. Munapo, C. Siguake, and M. Al-Rabeeah, The minimum spanning tree with node index $<=$ 2 is equivalent to the travelling salesman tour, Chapter 8 in Mathematics in Engineering Sciences: Noval Theories, Technologies and Applications, ISBN9781351266321, Editor Mange Ram, CRC Press Series (https://www.crcpress.com), pp. 227–244, 2019.

[11] E. Munapo, S. Kumar, M. Leasoana, P. Nyamugure, P. A minimum spanning tree with node index $<=$ 2, ASOR Bulletin, Vol. 34, Issue 1, pp. 1–14, (www.asor.org.au), 2016.

[12] J.B. Kruskal, on the shortest spanning subtree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc. 7, 48–50, 1956.

[13] R.C. Garg, and S. Kumar, The shortest connected graph through dynamic programming technique, Mathematics Magazine, Vol. 41, No. 4, pp. 170–173, 1968.

[14] S. Kumar, E. Munapo, M. Lesaoana, P. Nyamgurem A minimum spanning tree-based heuristic for the travelling salesman tour Opsearch, 55, 150–164, 2018.

[15] E. Munapo, S. Kumar, P. Nyamugure, T. Tawanda, Network Optimization: An introduction to the Network Reconstruction Approach, River publication, ISBN 978-87-7004-742-5, 2025.

Biographies

Santosh Kumar OAM received MSc (Mathematics) from Vikram University and PhD (Operations Research) from Delhi University. He is author and co-author of over 220 papers and 5 books in the field of Operations Research. His contributions in the field of OR have been recognized in the form of ‘Ren Pots’ award from the Australian Society for operations Research (ASOR) in 2009 and a recognition award from the South African OR Society as a non-member of the society and a non-resident of South Africa in 2011. He was the President of the Asia Pacific Operations Research societies (1995–97), where ASOR was a member along with 7 other countries in the region. He is currently an Honorary Professor at RMIT University, Melbourne. He is a Fellow of the Institute of Mathematics and its Applications, UK. On 14th June 2021, he was awarded a medal of the Order of Australia (OAM).

Late Professor Elias Munapo (11-11-1970–26-04-2026) had a BSc. (Hons) Applied Mathematics (1997), MSc. Operations Research (2002) and a PhD Operations Research (2010), all from the National University of science and Technology (N.U.S.T.), Zimbabwe, a certificate in outcomes-based assessment in Higher Education and Open distance learning, University of South Africa (UNISA), certificate in University Education Induction Program, University of KwaZulu-Natal (UKZN). He was a Professional Natural Scientist certified by the South African Council for Natural Scientific Professions (SACNASP), 2012; and NRF rated in South Africa. He published/co-published over 150 articles and three books. He edited/co-edited 7 books and was a guest editor of Applied Sciences, Algorithms and Next Energy journals which are under MDPI. He supervised/co-supervised eleven doctoral students and over 30 students at Master level. He was a member of the Operations Research Society of South Africa, Executive Committee Member 2012–13, South African Council for Natural Scientific Professions (SACNASP) as a Certified Natural Scientist, European Conference on Operational Research (EURO) and the International Federation of Operations Research Societies (IFORS), and a member of the International Conference on Optimization (ICO) and was part of the team preparing to host ICO 2026 at Johannesburg.

Trust Tawanda is a seasoned academic and researcher with a strong background in Operations Research and Statistics. He holds a Bachelor of Science (Hons) in Operations Research and Statistics (2013), a Master of Science in Operations Research and Statistics (2017), and a PhD in Operations Research (2024) from the National University of Science and Technology (NUST) in Zimbabwe. Currently, he is pursuing a Post Graduate Diploma in Higher and Tertiary Education (PGDHTE) at Great Zimbabwe University (GZU).

As an Associate Professor in the Department of Statistics and Operations Research at NUST’s Faculty of Applied Sciences, he teaches and conducts research in his areas of expertise, which include network optimization problems, transportation problems, travelling salesman problems, and assignment problems. He has a notable publication record, with papers and book chapters to his credit. His academic journey and research endeavours demonstrate his commitment to advancing knowledge in Operations Research.