Steiner travelling salesman problem

The Steiner traveling salesman problem (Steiner TSP, or STSP) is an extension of the traveling salesman problem, one of the fundamental combinatorial optimization problems. Given a list of cities, some of which are required, and the lengths of the roads between them, the goal is to find the shortest possible walk that visits each required city and then returns to the origin city. As we are looking for a walk, vertices can be visited more than once, and edges may be traversed more than once.