The cable trench problem: combining the shortest path and minimum spanning tree problems
Let G=(V,E) be a connected graph with specified vertex v0?V, length l(e)?0 for each e?E, and positive parameters ? and ?. The cable-trench problem (CTP) is to find a spanning tree T such that ?l?(T)+?l?(T) is minimized where l?(T) is the total length of the spanning tree T and l?(T) is the total path length in T from v0 to all other vertices of V. Since all vertices must be connected to v0 and only edges from E are allowed, the solution will not be a Steiner tree. Consider the ratio R=?/?. For R large enough the solution will be a minimum spanning tree and for R small enough the solution will be a shortest path. In this paper, the CTP will be shown to be NP-complete. A mathematical formulation for the CTP will be provided for specific values of ? and ?. Also, a heuristic will be discussed that will solve the CTP for all values of R. Both the shortest path and the minimum spanning tree problems are universally discussed in operations research and management science textbooks. Since the late 1950s, efficient algorithms have been known for both of these problems. In this paper, the cable-trench problem is defined which combines the shortest path problem and the minimum spanning tree problem to create a problem that is shown to be NP-complete. In other words, two easy problems are combined to get a more realistic problem that is difficult to solve. Examples are used to illustrate an efficient and effective heuristic solution procedure for the cable-trench problem.
shortest path minimum spanning tree heuristics networks graph theory np-completeness