Variation of TSP which needs to visit only a set of cities but can visit cities outside the set if necessary

Question

I need to solve a variation of TSP where nodes represent neighborhoods. Neighborhoods can be central or non-central. Starting from a non-central neighborhood I need to find the shortest path that visits all non-central neighborhoods exactly once and comes back to the starting point. Note that the shortest path may include one or more central neighborhoods if this helps to find a shorter path.

Input:

• A weighted undirected graph G, where nodes represent neighborhoods, and edges represent the distances (traveling costs) between neighborhoods.
• A list indicatng whether the neighborhoods are central or non-central.
• A starting neighborhood.

Output:

• The path that visits each of the non-central neighborhoods exactly once, while minimizing the total travel distance.
• The cost of such path

I'm looking for guidance or algorithms to efficiently solve the problem described above, considering the input and output specifications provided. Any assistance or insights would be greatly appreciated.

Answer 1

• LOOP over every pair of non central vertices
  • Find shortest path between pair
    • LOOP over central vertices in path
      • MARK vertex
• LOOP over central vertices
  • IF vertex unmarked REMOVE vertex
• APPLY standard TSP algorithm to reduced graph

Note that this algorithm will find the shortest path using neccessary central vertices, it may also use central vertices that could be avoided ( because they were marked in the shortest path between another pair of non central vertices )