In this paper, we consider a combinatorial optimization problem in a graph G(V, E) where V represents the node set and E denotes the edge set. V is partitioned into two subsets V 1 and V 2, which denote the “Steiner” node set and “Target” node set respectively. Similarly, E is partitioned into sets of E 1 and E 2, where E 1 is the set of edges that join two Steiner nodes, and E 2 is the set of edges that join one Steiner node and one target node. No edges exist between two target nodes. The problem is to select a non-empty Steiner set S ⊂ V 1 such that each target node must be linked to exactly one selected Steiner node. Meanwhile, all selected (active) Steiner nodes must be connected to form a Hamiltonian tour of minimum connection cost which is called Traveling Salesman (TSP) tour. The objective of the problem is to minimize the total costs (which we will describe in detail subsequently).
