The Cable-Trench Problem (CTP) is a common generalization of the Single-Source Shortest Paths Problem (SSSP) and the Minimum Spanning Tree Problem (MST): given an edge-weighted graph with a special root vertex and parameters τ , γ ≥ 0 , the goal is to find a spanning tree that minimizes the total edge costs plus the total cost of the paths from each vertex to the root, scaled by τ and γ , respectively. While it is well known that both SSSP and MST can be solved in polynomial time, CTP is NP -hard. We show that computing an approximate solution with factor less than 1.000475 is NP -hard, thus ruling out a polynomial-time approximation scheme, unless P = NP . We also consider the more general Steiner Cable-Trench Problem (SCTP), for which only a given subset of terminal vertices must be spanned by a solution. The tree might include non-terminal vertices, known as Steiner vertices, although only paths from terminals to the root are considered in the total cost. For this problem, we present a ( 2 . 88 + ϵ ) -approximation based on a counting argument, for any ϵ > 0 ; also, we give a simple parameterized algorithm with the number of terminals as parameter.

In the Star k-Hub Center (SkHC), given a connected edge-weighted graph G, a center c ε V(G) and integers k, r > 0, one wants to select a set of hubs H ⊆ V(G)\{c} of size k and an assignment from vertices to hubs. The goal is to find a solution in which the length of the longest path connecting each pair of vertices through the assigned hubs and the center is at most r. This problem appears in many areas, such as telecommunication, aviation and logistics, where hubs represent cross-docking centers that consolidate demand between pairs of clients, and the network has a centralized design. This paper investigates the parameterized complexity of the underlying graph connectivity problem. First, we note that finding a (1.25 - ε-approximation is W[2]-hard, for ε> 0, when the parameter is the number of hubs k. Moreover, we show that the problem is W[1]-hard even when parameterized by k plus the vertex cover number of the graph. While this rules out an algorithm parameterized by the treewidth tw of the graph, as a positive result, we present an efficient parameterized approximation scheme. Namely, for every ε> 0, we have a (1 + ε-approximation that runs in time 0*((tw/e)0(tw)).

The Cable-Trench Problem (CTP) is an optimization problem that generalizes both the Single-Destination Shortest Path Problem and the Minimum Spanning Tree Problem. Given an edge weighted graph with a special root vertex and parameters τ, γ ≥ 0, the objective is to find a rooted spanning tree that minimizes the weight of the tree, scaled by τ, plus the sum of the weights over all shortest paths from the root, scaled by γ. While each of the generalized problems are well-known to be polynomial-time solvable, CTP is NP-hard. In this paper, we show that even finding an approximation with factor of 1.000475 is NP-hard, thus ruling out the existence of a polynomial-time approximation scheme, unless P = NP.

The Double Routing Vehicle Problem with Multiple Stacks (DVRPMS) consists in a Double Traveling Salesman Problem with Multiple Stacks (DTSPMS) with multiple vehicles. Both problems appeared for the urgent need of optimizing intermodal transportation in the european context. Consolidated economies call for logistics studies, particularly on intermodal transportation, which consists of using different transport modes between a start point and an end point. In DVRPMS, the collecting region is usually connected to the delivery region by sea, and the cities that make up each of these regions are interconnected by land routes. In this paper, we propose three heuristics for the DVRPMS based on the Iterated Local Search (ILS), Simulated Annealing (SA) and Variable Neighborhood Descent (VND). The objective is to provide a route with near optimum cost in a timeframe that complies with the customer's needs. The heuristics were applied in known instances and compared to the exact method. Both ILS and SA algorithms showed to be satisfactory for small instances and open to improvement for large instances. The SA algorithm managed to find solutions better than the best known upperbound. The VND algorithm served more as a guide to the quality of the initial solution than as a provider of a good final solution.