Introduction

The traveling salesman problem is one of the Np-hard problems in the field of operations research, which has been tried for years to find an efficient algorithm. But an algorithm that solves this problem in polynomial time has not been presented yet. The description of this issue is as follows:

“We have a number of cities and we know the cost of going directly from one to another. It is desirable to find the least expensive route that starts from one city and passes through all cities exactly once and returns to the starting city.”

The number of possible solutions to the traveling salesman problem is equal to 0.5(n-1)! for n>2 where n is the number of cities. In fact, this number is equal to the number of Hamiltonian cycles in a complete graph with n vertices. As the number of cities increases, the number of Hamiltonian paths increases exponentially, and finding the Hamiltonian path with the smallest travel length becomes very difficult and impossible.

There is no specific software to solve this problem. Also, due to the huge application of the traveling salesman problem, the need for an efficient solver for this problem is very necessary. Optimization City group has designed and implemented an online solver for the traveling salesman problem. In the following, we will review how to use this online solver.

Instructions of using online solver of the traveling salesman problem

The GUI of the online solver of the traveling salesman problem is as follows.

Problem input

To find the optimal solution to the traveling salesman problem, the required inputs are as follows:

n: the number of nodes in the graph.

dist: is the cost matrix of graph edges, which is a matrix with n+1 rows and n+1 columns.

Example

To teach how to use this solver, we use the following example. A weighted graph is given below. Determine the optimal solution of the traveling salesman problem for the weighted graph as follows.

Solution:

Entering information in the online solver of the traveling salesman problem is as follows. Note that leave a comma between each entry to separate the numbers. For edges that do not exist in the graph, we consider the weight of 999.

After entering the data, we click on the RUN button.

The result of running the algorithm is as follows.

In the output of the algorithm, it reports the Hamiltonian path with the minimum travel cost, and the total cost in this problem is equal to 147.