Question

Identify five different variants of Traveling Salesman Problems (TSP) by performing a quick literature review. Briefly define each of these. Explain the differences between Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP). (some useful databases: Sciencedirect, Springerlink, Taylor and Francis)

Answer 1

The 5 different types of traveling salesman problem are stated below=

MAX TSP= In place of minimizing the traveling cost, the main focus of Mac TSP remains on looking for a tour in which the total cost of edges is the greatest. The MAX TSP can be formed as a TSP in which each edge cost is substituted with the additive inverse.

Bottleneck TSP= Here the focus remains on finding out a tour which has a minimum cost for the edge having the largest cost and it can be represented as a TSP with exponentially large edge costs

TSP with multiple visits (TSPM)=This is the method in which the focus remains on routing a salesman in such a manner that all the notes are visited at least one tie and at the same time, the total travel distance is maximized. In order to represent it, we have to replace edge cists with the shortest path distance.

Messenger problem= This is also termed as a wandering salesman problem. Here the focus is on to look for the Hamiltonian path having minimum cost from a certain node u to node v in G. This problem can be formulated by including a large negative cost for the edge.

m-salesmen TSP= Let us consider m salesman is situated at node 1, we have to reduce the distance covered by every salesman I in which each node is covered by every salesman in a subset Yi of G minimum of one time before returning to node 1.

Differences=

VRP can be seen as combinatorial optimization and integer programming problem in which the focus remains on finding out the optimal number of routes for the fleet of vehicles to navigate so that delivery can be made to a certain combination of customers.

In the case of TSP, on the basis of a given combination of cities and distances between various cities, the main focus is to look for the shortest possible route which visits each city at least once and return to the starting point.