Minimum Spanning Tree Approach to Path Through K Specified Links

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

¹Department of Mathematical and Geospatial Sciences, School of Sciences, RMIT University, Melbourne, Australia
²School of Economics and Decision Sciences, North West University, Mafikeng Campus, Mafikeng, South Africa
³Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe
E-mail: santosh.kumarau@gmail.com; emunao@gmail.com; philimon.nyamugure@nust.ac.zw; trust.tawanda@nust.ac.zw; trustawanda@gmail.com
*Corresponding Author

Received 07 July 2023; Accepted 02 August 2023; Publication 30 September 2023

Abstract

This paper presents a minimum spanning tree approach to find a path through ‘k’ specified links. This problem has many real-life applications and unlike the shortest route, the path through specified links may have loops. The proposed method determines the route, which may either be an optimal or a near optimal path. It may also contain loops.

Keywords: Specified links, circuits, minimum spanning tree, partially minimum spanning tree.

1 Introduction

Determination of the shortest route between the origin and the destination nodes is a classical problem in graph theory, which pertains to search for the shortest route between the two given nodes ‘ $O$ ’ and ‘ $S$ ’ in a graph $G (N, L)$ , where $N$ denotes a set of nodes and $L$ is a set of links. Each link is associated with some weight indicating some real characteristics, such as cost of travel through that link, or time of travel etc. The two designated nodes denoted by ‘ $O$ ’ and ‘ $S$ ’, which belong to the set ‘ $N$ ’, are known as the origin and the destination nodes, respectively. The shortest route is required in many practical situations, and for their solution approaches, see Ahuja et al. [1], Bellman [4], Beckwith [3], Dantzig [7], Dijkstra [8], Garg and Kumar [9], Peart et al. [25], and Pollack and Weibenson [26]. A variation of the shortest route problem was pointed out by Kalaba [10]. He considered a need to find the path from the origin node to the destination node that must visit a set of specified nodes enroute before arriving to the destination node. When the set of specified nodes is a null set, the problem reduces to an ordinary shortest route problem, which has received extensive attention, as pointed out earlier, and for addition references, see, Mehlhorn and Sanders [20], Munapo, Jones and Kumar [22], Kumar et al. [13], Munapo et al. [23], and Zhan [30]. However, when the set of specified nodes is not a null set, the required route is such that it must pass through the set of specified nodes before arriving at the destination node. Such a route may have loops. Another extreme case of the k specified nodes is a well-known problem when the set of specified nodes contains all nodes. In some special cases, one is required to visit all nodes of the network and return to the origin node. This problem is also known as the travelling salesman problem, for which dynamic programming treatment was given by Bellman [5]. Kumar et al. [15–18] gave a minimum spanning tree approach. Once again, many approaches are available in the literature to deal with the travelling salesman problem, see Munapo and Kumar [24]. These two extreme cases deal with loop free paths and in all other cases loop is a possibility.

Complexity of the problem that requires determination of a path through $K$ specified nodes will depend on the number of specified nodes. Bellman and Kalaba [6], Saksena and Kumar [27], Sinha and Bajaj [28, 29] solved the general routing problem through the $K$ specified nodes by using the functional equation technique of dynamic programming. They assumed that $0 < k < n$ , where n is the number of nodes in the given network with non-negative distances for the links. This problem of a path through K specified nodes was reconsidered by Kumar et al. [14], and they used the minimum spanning tree approach developed by Munapo et al. [23] and Munapo [21].

In this paper, the routing problem with $K$ specified links has been considered and solved by using the minimum spanning tree (MST) approach, which was attempted earlier by Arora and Kumar [2] using the ring sum approach.

Detailed application of the path through $K$ specified links is presented in Section 2. Characteristics of the problem and a method to find the path through $K$ specified links has been discussed in Section 3. Some numerical illustrations have been presented in Section 4. Finally, the paper is concluded in Section 5.

2 Practical Applications of the Path Through K Specified Links

It is well known that manufactured goods travel various distances from the factory where they were produced to their destination, the consumer. As an example, consider a department store with many outlets in a large cosmopolitan city. Each store sells, many household goods such as fridges, washing machines, dishwashers, etc. which usually are not collected by the buyers. These customers often request the delivery and installation of these bulky goods at their residences. Usually, each store will not hold separate inventory at the store but sold items from different outlets are delivered from a central warehouse to various homes. Each house is situated on a street, and these streets where delivery is scheduled on a particular day form the set of specified links. The warehouse is the origin node, and the delivery trucks depot is the destination, and the specified links are the delivery links on a particular day. This set of specified links change each day as customer set changes each day.

Similar situations can be identified in many other distribution cases, for example, farm goods are transported to different warehouses, manufactured goods are transported from the production plant to various warehouses, etc. This problem can be identified in various situations in various industries.

3 Characteristics of the Path Through k Specified Links

Since specified links are given, they must form a part of the path. The path containing the specified links may have circuits among the specified links or together with non-specified links. The specified links, on their own may form any configuration and one such set of specified links is shown in Figure 1.

Figure 1 Specified links.

Figure 1 display two specified links $(i, j)$ and $(k, l)$ , which is part of the given graph. In general, we may assume that the number of specified links is given by r, where $0 < r < n$ (the value of r in Figure 1 is 2). The spanning tree of the graph $G (N, L)$ will have a total number of $(n - 1)$ links, out of which r number of links have been specified. If these specified links do not form a circuit, we need $(n - r - 1)$ additional links to form a connected graph. Therefore, after selecting $(n - r - 1)$ additional links, one obtains a connected spanning tree of the network $G (N, L)$ . These additional $(n - r - 1)$ links can be selected by following Kruskal [11] steps, which can be slightly modified for our purpose. Since this tree has $r$ specified links and $(n - r - 1)$ selected links, it will not be a minimum spanning tree, we call this tree a partially minimum connected tree (PMST). In some cases, depending on the configuration of the specified links, this graph may have even circuits. After slight modification, the Kruskal [11] steps for the situation presented in this paper, will be:

Step 1: Arrange the remaining $(l - r)$ number of non-specified links in non-decreasing order of their weight.

Step 2. Pick the smallest link. Check if it forms a cycle with the selected links, which initially are the set of specified links. Remember, the specified links may have a cycle among them. In subsequent selections, one must check with the selected non-specified links and the given specified links. If the selected links do not form a cycle, include this link, else discard it.

Step 3: Repeat Step 2, with the next link until total number of links i.e., $(r)$ specified, and non-specified $(n - r - 1)$ totalling equal to $(n - 1)$ . If the specified links form a cycle, for each cycle, one additional link will be required to form a partially minimum connected graph.

3.1 Mathematical Model of the Shortest Path Through K Specified Links

We use the following notation to develop a mathematical model for the above problem.

Let $C_{i j}$ $=$ the link weight associated with the link $(i, j)$ , $i = 1, 2, \dots, n$ ; $j = 1, 2, \dots, n$ ; $i \neq j$ . Note that if there is no link from any $i$ to $j$ , that $C_{i j} = \infty$ or equivalently the corresponding variable $x_{i j} = 0$ . In general, the variables will be defined as given below:

x_{i j} = {\begin{matrix} 1, & if the link (ij) is used to form the path \\ 0, & if the link (ij) does not form the path \end{matrix}}

The model can be represented as:

M i n Z = \sum_{(i j) = 1}^{L} C_{i j} x_{i j}

Subject to:

$\sum_{(1, j)} x_{(1, j)} = 1$ (Indicates that one link will be used from the origin node 1.

$\sum_{(j, n)} x_{(j, n)} = 1$ (Indicates that one link will be used to reach the destination node n.

$x_{(i j) S} = 1$ , For each specified links $s$ , where $s = 1, 2, \dots r$ . These links must be included in the required path.

For nodes, other than the origin and the destination, and those which are free of the specified links, must satisfy the following:

$\sum_{i} x_{i j} = 0$ or 2, means that the shortest path passing through specified links will either not pass through a node or will enter form one link and leave that node from the other link.

For nodes from where specified links emanate or end, must satisfy:

$\sum_{i} x_{i j} = 2$ or 4, means that in addition to the specified link, either three or one more link will be emanating from this node as part of the path.

Several constraints have two values on the RHS like 0 or 2 and 2 or 4. These constraints will require further modification. It is explained below:

For example, consider the constraint:

$\sum_{i} x_{i j} = 2$ or 4, which can be modified as

$\sum_{i} x_{i j} = 2 y_{1} + 4 y_{2}, y_{1} + y_{2} = 1, y_{1}, y_{2} = 0$ or 1.

This will result in a large cumbersome model; hence some special approach is desirable, which is discussed in the Section 3.2.

3.2 Further Clarification of the Modified Selection Process

The nodes forming the specified links are $(i, j)$ and $(k, l)$ in Figure 1, however, when r disconnected specified links are given, the number of nodes associated with the specified links will be at most equal to 2r. For example, in Figure 1, node index of the nodes associated with the specified links will be equal to 4. This node index can be less than 2r, when these specified links are not disconnected, for example, as shown in illustrative examples in Section 4.2, where the specified links form a circuit. In the final connected graph, all nodes will have node index $>$ = 1. The total index value of all nodes will be $\geq 2 (n - 1)$ . By the application of the index balancing theorem, we try to attain balance among the index of all nodes, which varies depending on the configuration of the specified links. For the illustrative example 4.1, node index will be equal to 2, except the origin and the destination node, and this index can be more than 2 i.e. 4. For developing a path joining the origin to the destination, passing through all nodes associated with the specified links, one may be forced to add more links. The node index for the nodes associated with the specified links will be 2 or 4 but not 3. The index value 4 indicates formation of a cycle.

Note that the node index balancing theorem is not applicable to the specified links, as they are never to be removed from the final graph. For the graph in Figure 1, the index will be equal to 2 or 4 but not three. For the node of the specified link, one link will be the given specified link i.e., the link $(i, j)$ at nodes $i$ and $j$ and the link $(k, l)$ for the nodes $k$ and $l$ . The index at the origin and destination node will be 1. All other links that are not member of the path can be removed from the system.

The index balancing theorem discussed by Munapo et al., [23] states that, “adding the same constant to all arcs emanating from the same node does not change the relative merit of any selected arc in the PMST (Partial Minimum Spanning Tree) obtained by the greedy approach. Since the PMST is known, the index for each node is also known, and therefore, high, and low index nodes can be easily identified. The balancing index commences its balancing task by adding constants and bringing index of high index nodes low and taking index of low index node to the required level.” Since the presence of the specified links is not based on any selection, the index balancing theorem in not necessarily applicable to these links.

When required path cannot be established by the application of the node balancing theorem, additional links may have to be added but these additional links develop circuits and make node index of some nodes more than 2 to 4, an even number. All unnecessary links not on the path can be removed.

4 Numerical Illustrations

In this section, we discuss two numerical illustrations with different configurations of the specified links.

4.1 Illustration 1

Let us consider the network N(10, 21) as shown in Figure 2, where O is the origin node and 9 is the destination node. The link weights are indicated on the links.

Figure 2 Given connected graph and arc distances.

Let the set of specified links be {(1,2), (3,4), (5,6)}. Since these links are specified, they will remain part of PMST in the remaining analysis. Here onwards we will show these specified links with the letter ‘S’ to indicate that they are specified links. They must form a part of the path to be identified. This is shown in Figure 3.

Figure 3 Network with three specified nodes forming a disconnected set.

4.1.1 Mathematical model of the above problem

For the above 10 node 21 links network, we define 21 variables. These are binary variables, associated with the links as follows:

$x_{i j}$	$= 1, if the link joining nodes (i, j) is part of the path,$
	$else it is zero .$

Using the above, a mathematical model can be developed as given below.

M i n Z = x_{01 +} 10 x_{03} + 6 x_{05} + 3 x_{07} + \dots + 5 x_{29} + 2 x_{49} + 8 x_{69} + 5 x_{89}

Subject to

(1) Constraints for the origin and the destination nodes:

$x_{01 +} x_{03} + x_{05} + x_{07} = 1$ (Origin node)

$x_{29} + x_{49} + x_{69} + x_{89} = 1$ (Destination node)

(2) Constraints representing nodes free of specified links

Nodes 7 and 8 are the only two nodes in this category. The constraints for these two nodes are given below for nodes 7 and 8, respectively:

$x_{07} + x_{57} + x_{67} + x_{78} = 0$ or 2 and $x_{78} + x_{68} + x_{89} = 0$ or 2

These two constraints can be replaced by the following two sets of constraints, given below:

x_{07} + x_{57} + x_{67} + x_{78} = 0 y_{1} + 2 y_{2}

y_{1} + y_{2} = 1, y_{1}, y_{2} a r e z e r o o r 1

Similarly, we rewrite the constraint representing the node 8 as follows:

x_{78} + x_{68} + x_{89} = 0 y_{3} + 2 y_{4}

y_{3} + y_{4} = 1, y_{3}, y_{4} a r e z e r o o r 1 v a r i a b l e s

(3) The third set of constraints will arise from the nodes that start or end at the specified links. In this category, there are 6 nodes, which are: 1, 2, 3, 4, 5, and 6. These constraints are given by:

Node 1:

x_{01} + x_{13} + x_{12} = 2 y_{5} + 4 y_{6}

y_{5} + y_{6} = 1, y_{5}, y_{6} a r e 0 o r 1 .

Node 2:

x_{12} + x_{32} + x_{42} + x_{25} = 2 y_{7} + 4 y_{8}

y_{7} + y_{8} = 1, y_{7}, y_{8} a r e z e r o o r 1 .

Node 3:

x_{03} + x_{31} + x_{32} + x_{34} + x_{36} + x_{35} = 2 y_{9} + 4 y_{10}

y_{9} + y_{10} = 1, y_{9}, y_{10} a r e z e r o o r 1 .

Node 4:

x_{34} + x_{24} + x_{46} + x_{49} = 2 y_{11} + 4 y_{12}

y_{11} + y_{12} = 1, y_{11}, y_{12} a r e z e r o o r 1 .

Node 5:

x_{05} + x_{57} + x_{56} + x_{53} = 2 y_{13} + 4 y_{14}

y_{13} + y_{14} = 1, y_{13}, y_{14} a r e z e r o o r 1 .

Node 6:

x_{56} + x_{36} + x_{76} + x_{68} + x_{46} + x_{69} = 2 y_{15} + 4 y_{16}

y_{15} + y_{16} = 1, y_{15}, y_{16} a r e z e r o o r 1 .

(4) Conditions on the specified links

x_{12} = x_{34} = x_{56} = 1

(5) Conditions on variables

All other

x_{i j} = 0 or 1 for all ij that correspond to a link

y_{1}, \dots, y_{16} = 1 or 0 .

In the above 10 node networks; the PMST will be comprised of 9 links, as the specified links are free of a circuit. Since the specified links are 3, we need to select 6 more links to make an PMST of the network in Figure 3. The above network is comprised of 21 links, 3 of them are specified. The remaining 18 links are arranged in non-decreasing order as given below, where equal weights are just arranged in the order of the first node of that link.

Figure 4 MST of the given graph.

Links in non-decreasing order (weight, link) are:{1(0,1) $_{1}$ , 1(2,3) $_{2}$ , 1(3,6) $_{3}$ , 2(2,4) $_{4}$ , 2(4,9) $_{5}$ , 2(5,7) $_{6}$ , 3(0,7) $_{7}$ , 3(6,8) $_{8}$ , 4(3,5) $_{9}$ , 5(2,9) $_{10}$ , 5(4,6) $_{11}$ , 5(8,9) $_{12}$ , 6(0,5) $_{13}$ , 6(6,7) $_{14}$ , 8(6,9) $_{15}$ , 8(7,8) $_{16}$ , 10(0,3) $_{17}$ , 10(1,3) $_{18}$ }; and the specified links are: {10 (1,2), 4(3,4), 3(5,6)}.

First three links {(0,1), (2,3), (3,6)} can be selected for the PMST but the next link (2,4) forms a loop, hence is not included. Next two links (4,9) and (5,7) are included in the PMST. Finally, the link (6,8) is included in the PMST. This PMST is shown in Figure 4.

Note from Figure 4, we are looking for a path from nodes 0 to 9 passing through the specified links (1,2), (3,4) and (5,6). Links (5,7) and (6,8) can be removed as they are not necessary for a path from O to 9. After removing these two links, nodes 3 and 5 have node index of 3 and 1, which is not even. Hence by adding the link (3,5), index of all nodes will be balanced, and the path becomes:

$Path : O \to 1 \to 2 \to 3 \to 6 \to 5 \to 3 \to 4 \to 9$

Forming a path with a loop $3 \to 6 \to 5 \to 3$

Total cost $=$ 1 $+$ 10(S) $+$ 1 $+$ 1 $+$ 3S $+$ 4 $+$ 4S $+$ 2 $=$ 26.

The path through the specified links is comprised of a loop, which is typical in a path through specified links.

4.2 Numerical Illustration 2

Let us reconsider the network N(10, 21) in Figure 2 with a slightly different configuration of the specified links as shown in Figure 5.

Figure 5 Network with specified nodes forming a disconnected set.

The set of specified links are 5, and they are: {(1,2), (2,4), (3,4), (5,6), (5,7), (6,7)}. To form a PMST, we need to select $9 - 6 = 3$ more links. The non-specified 14 links are arranged in non-decreasing order as given below:

{1(0,1) $_{1}$ , 1(2,3) $_{2}$ , 1(3,6) $_{3}$ , 2(4,9) $_{4}$ , 3(0,7) $_{5}$ , 3(6,8) $_{6}$ , 4(3,5) $_{7}$ , 5(2,9) $_{8}$ , 5(8,9) $_{9}$ , 6(0,5) $_{10}$ , 8(6,9) $_{11}$ , 8(7,8) $_{12}$ , 10(0,3) $_{13}$ , 10(1,3) $_{14}$ }

Note the number of specified links are 6, therefore normally we need 3 more links to form a partially minimum shortest connected graph. These three links are: {(0,1), (3,6), (4,9)}. However, 3 specified links {(5,6), (5,7) and (6,7)} are forming a loop, and therefore the 9 links do not form a connected graph. The next link to be selected is (6,8) forming PMCG, with a loop. It is shown in Figure 6.

Figure 6 PMST of the graph in Figure 5.

Note all index order are balanced, except the node 8 and node 6, with index value 1 and 5. Since the link (6,8) can be removed, and it will bring index of all nodes in balance and hence the path can be traced as follows:

$0 \to 1 \to 2 \to 4 \to 3 \to 6 \to 7 \to 5 \to 6 \to 4 \to 9, w i t h a l o o p 5 \to 6 \to 7 \to 5$ . Total cost will be $=$ 1 $+$ 10 $+$ 2 $+$ 4 $+$ 1 $+$ 3 $+$ 2 $+$ 6 $+$ 5 $+$ 2 $=$ 36 units.

4.3 Advantages Associated with the Proposed Approach

A closely related, but independent, problem is to find the path between two given nodes designated as the origin and the destination node, which must pass through a given set of specified nodes. This problem has been attempted by using different approaches, see Kalaba [10], Arora and Kumar [2] and Kumar and Arora [12] where the Computational complexity increases rapidly as number of specified nodes become more and more. However, the same problem was reconsidered by Kumar et al. [14] by the spanning tree approach and the computational complexity was independent on the number of specified nodes. In reliability context, similar problem was attempted by Kumar et al. [15]. The spanning tree approach has been successfully applied to the travelling salesman problem, where Kumar et al. [19] established equivalence between the travelling salesman route and the minimum spanning tree. This was the motivation, and the spanning tree approach was applied to find path through specified links.

5 Concluding Remarks

5.1 In this paper, we considered the routing problem through k specified links. A similar problem through k specified links was also considered by (Arora and Kumar [2]) using the ring-sum approach.

5.2 It is easy to see that the approach discussed in this paper, can easily establish lower and upper bound on path length. For example, the lower bound on the path length is the unconstrained path and upper bound is the length of path one gets by the approach discussed in this paper.

5.3 It is desirable to establish a procedure of moving the bounds and thus establishing optimality of the solution.

5.4 Computational complexity does not increase with increase in the number of specified links.

5.5 Certain practical real-life situations have been identified, where there is a need for a path between the origin and the destination node must pass through a set of specified nodes and links. It will be subject matter for our future communication.

References

[1] R. K. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan, Faster algorithms for the shortest path problem, Journal of the Association of Computing Machinery, Vol. 37, pp. 213–223, 1990.

[2] H. Arora, and S. Kumar, Path through k-specified edges in a liner graph, Opsearch, Vol. 30, No. 2, pp. 163–173, 1993.

[3] R.E. Beckwith, Dynamic programming and network routing: An introduction to the technique of functional equations, Dynamic programming workshop, Boulder, Colorado. 1961.

[4] R. E. Bellman, On a routing problem, Quarterly of Applied mathematics, Vol. 16, No. 1, pp. 87–90, 1958.

[5] R. E. Bellman, Dynamic programming treatment of travelling salesman problems, J of ACM, Vol. 9, pp. 61–63, 1962.

[6] R. E. Bellman, and R. Kalaba, On the Kth Best policies, J of Society Industrial and Applied Mathematics, Vol. 8, No. 4, pp. 582–588, 1960.

[7] G. B. Dantzig, Discrete variable extremum problems, Opns. Res. Vol. 5, pp. 266–276, 1957.

[8] E. J. Dijkstra, A note on two problems in connection with graphs, Numerische Mathematik. 1: 269–271, 1959, doi: 10.1007/BF01386390.S2CID123284777.

[9] R.C. Garg, and S. Kumar, Shortest connected graph through dynamic programming, Maths Magazine, Vol. 41, No. 4, pp. 170–173, 1968.

[10] R. Kalaba, On some communicating network problems, DOI: 10.1090/psapm/010/0122573, 1959.

[11] J. B. Kruskal, On the shortest spanning tree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc., 7, pp. 48–50, 1956.

[12] S. Kumar, and H. Arora, K shortest paths and paths through R-specified edges in a protean network, ASOR Bulletin, Vol. 14, No. 2, pp. 3–8, 1995.

[13] S. Kumar, E. Munapo, O. Ncube, C. Saguke, and P. Nyamugure, A minimum weight labelling method for determination of a shortest route in a non-directed network, Int J Syst. Assur. Eng. Manag. DOI 10.1007/s13198-012-0140-7, Springer, ISSN 0975-6809, Vol. 4, No. 1, pp. 13–18, 2013.

[14] S. Kumar, E. Munapo, M. Leasoana, and P. Nyamugure, A minimum spanning tree approximation to the routing problem through ‘K’ specified nodes, Journal of Economics, Vol. 5, No. 3, pp. 307–312, 2014.

[15] S. Kumar, E. Munapo, M. Leasoana, and P. Nyamugure, Is the travelling salesman problem actually NP Hard? Chapter 3 in Engineering and Technology, Recent Innovations and Research, Editor Ashok Mathani, International Research Publication House, ISBN 798-93-86138-06-4, pp. 37–58, 2016.

[16] S. Kumar, E. Munapo, M. Lesaoana, and P. Nyamugure, A minimum spanning tree based approach to the travelling salesman tour, Opsearch, Vol. 55, No. 1, pp. 150–164, 2018a. {DOI: 10.1007/s12597-017-0318-5, pp. 1–15, 2017}.

[17] S. Kumar, E. Munapo, M. Lesaoana, and P. Nyamugure, Some innovations in OR Methodology: Linear Optimization, Lambert Academic Publishing, ISBN: 978-613-7-38007-9, 2018b.

[18] S. Kumar, E. Munapo, C. Sigauke, M. Al-Rabeeah, The minimum spanning tree with index $<$ =2 is equivalent to the minimum travelling salesman tour, Chapter 8, Mathematics in Engineering Sciences: Novel Theories, Technologies and Applications, ISBN 9781351266321, Editor, Mange Ram, CRC Press (http://www.crcpress.com), pp. 227–243, 2019.

[19] S. Kumar, E. Munapo, M. Lesaoana, and P. Nyamugure, P. Dickgale, Link-weight modification for network optimization: Is it a tool, philosophy, or an art? Chapter 11 in Recent Advances in Mathematics for Engineering, CRC Book, Ed. Mange Ram, CRC Press, (http://www.crcpress.com), pp. 227–243, 2020.

[20] K. Mehlhorn, P. Sanders, Chapter 10: Shortest Paths, Algorithms and Data Structures: The Basic Toolbox. Springer. DOI: 10.1007/978-3-540-77978-0, ISBN 978-3-540-77977-2008.

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

[22] E. Munapo, BC Jones, and S. Kumar, A minimum incoming weight label method and its application to CPM network, ORiON, Vol. 24, 2008, South African Journal of OR.

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

[24] E. Munapo, and S. Kumar, Linear Integer programming: Theory, Applications, Recent Developments, De Gruyter Publication, ISBN 978-3-11-070292-7, 2022.

[25] R.M. Peart, R. Randolf, and T.E. Bartlet, The shortest route problem, Opns. Res., Vol. 8, pp. 866–868, 1960.

[26] M. Pollack, and W. Weibenson, Solution of the shortest route problem – A review, Opns. Res., Vol. 8, pp. 224–230, 1960.

[27] J.P. Saksena, and S. Kumar, The routing problem with ‘K’ specified nodes, Opns. Res., Vol. 14, No. 5, pp. 909–913, 1966.

[28] S.M. Sinha, and C.P. Bajaj, The maximum capacity route through a set of specified nodes, Cahiers du Centre d’Etudes de Recherche Operationnelle, Vol. 11, pp. 133–138, 1969.

[29] S.M. Sinha, and CP. Bajaj, The maximum capacity route through a set of specified nodes, Opsearch, Vol. 7, pp. 96–114, 1970.

[30] F.B. Zhan, Three fastest shortest path algorithms on real road networks: Data structures and procedures, Journal of the Geographic Information and Decision Analysis, Vol. 1, No. 1, pp. 70–82, 1997.

Biographies

Santosh Kumar OAM received PhD degree from Delhi University in 1968. He is author and co-author of over 200 papers and 4 books in the field of Operations Research. His contributions in the field of OR have been recognised 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 the 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).

Elias Munapo holds 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 Programme, University of KwaZulu-Natal (UKZN). He is a Professional Natural Scientist certified by the South African Council for Natural Scientific Professions (SACNASP), 2012; and NRF rated in South Africa. He has published/co-published over 120 articles and two books. He has also edited/co-edited 7 books and is a guest editor of Applied Sciences, Algorithms and Next Energy journals which are under MDPI. He has supervised/co-supervised eleven doctoral students and over 30 students at Master level. He is 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 is part of the team preparing to host ICO 2026 at Johannesburg.

Philimon Nyamugure has a BSc (Hons) 1998, MSc – 2002; Post Graduate Diploma in Higher Education, 2013, all from NUST; PhD in Statistics, University of Limpopo, 2017. He joined NUST in 2003 and was Chairperson for the Departments of Applied Mathematics (2009–2013) and Chairman, Department of Statistics and Operations Research (2013–2019). Became Executive Dean of the Faculty of Applied Science from 2020 to date. A University Senator from 2009 and Councillor from 2020 up to date. He received an award for the best PhD presenter in the School of Mathematical and Computer Sciences, University of Limpopo. Best Senior presenter, Faculty of Applied Sciences, and in 2017 Fulbright Research Award for African Scholars. Involved in several community engagement programmes including National University of Science and Technology Schools Enrichment Programme (NUSTSEP). He is currently an Executive Dean and a Professor at NUST.

Trust Tawanda received the bachelor’s degree in Operations Research and Statistics and the master’s degree in Operations Research and Statistics from the National University of Science and Technology (NUST), Zimbabwe, in 2013 and 2017 respectively, and is currently a student for the Doctor of Philosophy degree in Operations Research, NUST, Zimbabwe. He is currently working as a Lecturer at the Department of Statistics and Operations Research, Faculty of Applied Sciences, NUST. His research areas include maximum flow, shortest paths, transportation, travelling salesman and assignment problems. He has published papers and book chapters.