a
b
c
d
x
y
z
AC
i
Randomize
About Traveling salesman problem calculator
Solve the traveling salesman problem online using the branch-and-bound method with detailed step-by-step solution. with complete, detailed, step-by-step description of solutions, that solves linear-programming problems up to 20×20 in size with coefficients of this type: decimal numbers and fractions.
To start the calculation, you need to first enter the problem dimensions in the input fields at the very top of the screen, and also choose the desired operation from the side menu.
A little below you will find an input window where you need to enter the coefficients, constraints, and right-hand-side values using the keyboard. The input control panel is also located here, which simplifies work with LP problems and contains the following control elements:
- The first element allows you to expand the input window. This can be especially useful when the tableau does not fit completely on the screen. If the table is still not fully visible after expanding the window, you can change the scale using the + / - buttons;
- The second element copies the current problem input to the memory buffer. This can be useful when you frequently solve the same LP problem or need to transfer data between operations;
- And the last element pastes the previously copied input, which allows you to restore problem data in just a few clicks instead of re-entering it manually;
And further down you will find a toolbar that allows you to customize the calculator and make it easier to work with. It is visually divided into three parts, each of which is responsible for the following functionality:
- The first part lets you select the number format used when displaying the solution result. You can also turn off step-by-step comments if you already understand the method and only need to check your own calculations, or hide the step-by-step solution entirely if you only need the final answer;
- The second part contains buttons that let you modify the input table dimensions, clear individual coefficients or the entire input, and the main button with an equal sign that takes you to the solution screen. All these buttons are duplicated by keyboard shortcuts. Hover over a button to see the corresponding key in a tooltip. You can also use the arrow keys to move the cursor between input fields;
- And the last part allows you to choose the number of digits after the decimal point for rounding non-integer results. A live preview shows how the rounded values will appear;
What is the Traveling salesman problem?
The Traveling Salesman Problem (TSP) is a classical NP-hard combinatorial optimization problem: given a complete weighted graph of n cities, find the shortest Hamiltonian cycle — a closed tour that visits every city exactly once and returns to the starting city. The total number of possible tours grows factorially with n, making exhaustive search impractical even for moderate sizes, so exact methods such as Branch and Bound are used to prune the search space.
How to solve the Traveling salesman problem with Branch and Bound?
Begin by reducing the cost matrix: subtract the row minimum from each row, then subtract the column minimum from each column; the sum of all reductions is the lower bound for the optimal tour. At each branching step, select a zero-cost edge (i, j) to either include or exclude. For the ACCEPT branch, remove row i and column j from the matrix, block the reverse edge (j, i) with infinity to prevent premature sub-tours, and reduce again. For the REJECT branch, set cost (i, j) to infinity and reduce. Compare the lower bounds of both branches and explore the more promising one first. Continue until a complete Hamiltonian cycle is identified.
Example of solving the Traveling salesman problem with Branch and Bound
We start solving the problem from the preliminary stage. To do this, look for the smallest values in the rows of the matrix (write them in the green column to the right of the matrix) and subtract them element by element, obtaining an intermediate matrix. Then, for the resulting matrix, we look for the smallest values in the columns (write them in the blue line below the matrix).
We find the sum of the smallest values in rows and columns and assign the resulting value to the cumulative variable D
D = 18
For the intermediate matrix, we subtract element by element the smallest value in the columns. Thus, in each row and column we get at least one zero. For each matrix zero, we calculate the sum of the smallest values in the rows and columns where the corresponding zeros are located, without taking into account the zeros themselves. The resulting values are written in parentheses.
We carry out the further solution with respect to zero with the largest estimate calculated at the previous stage.
The index under which this zero is located indicates a branch edge.
You need to check whether this edge should be added to the shared path or not.
Let's check how much the price of moving along the route without the current branching edge will increase. The verification is carried out by replacing the zero with the highest estimate by M (infinity), after which we carry out the reduction of the matrix.
The matrix is reduced by searching in the original matrix for the minimum values in each row and subtracting them element by element from all elements of the row. In the resulting matrix in each column, we determine the minimum value and subtract it element by element from all elements of the column.
We find the sum of the smallest values in rows and columns and thus determine how much the price of moving along the route without the current branching edge will increase.
H(2*,1*) = 6
Let's check how much the price of moving along the route increases if we add the current branch edge to the common path. And on the basis of this data, we decide to add a branch edge to the common path or it is more profitable to choose another path.
Verification is carried out by eliminating the i-th row and the j-th column from the matrix, where i, j is the index of the element with respect to which the decision is made.
In the resulting matrix, it is necessary to replace it with M (infinity), the element under the index inverse to the fact that it has an element with respect to which the decision is made.
Then we find the smallest values by the rows and columns of the matrix.
Then, for each matrix zero, we calculate the sum of the smallest values in the rows and columns where the corresponding zeros are located, without taking into account the zeros themselves.
The resulting values are written in parentheses.
We find the sum of the smallest values in rows and columns and thus determine the price of movement through the current branch edge.
H(2,1) = 0
Because H(2,1) <= H(2*,1*), then we include this edge in the general path.
We carry out the further solution with respect to zero with the largest estimate calculated at the previous stage.
The index under which this zero is located indicates a branch edge.
You need to check whether this edge should be added to the shared path or not.
Let's check how much the price of moving along the route without the current branching edge will increase. The verification is carried out by replacing the zero with the highest estimate by M (infinity), after which we carry out the reduction of the matrix.
The matrix is reduced by searching in the original matrix for the minimum values in each row and subtracting them element by element from all elements of the row. In the resulting matrix in each column, we determine the minimum value and subtract it element by element from all elements of the column.
We find the sum of the smallest values in rows and columns and thus determine how much the price of moving along the route without the current branching edge will increase.
H(1*,4*) = 9
Let's check how much the price of moving along the route increases if we add the current branch edge to the common path. And on the basis of this data, we decide to add a branch edge to the common path or it is more profitable to choose another path.
Verification is carried out by eliminating the i-th row and the j-th column from the matrix, where i, j is the index of the element with respect to which the decision is made.
In the resulting matrix, it is necessary to replace it with M (infinity), the element under the index inverse to the fact that it has an element with respect to which the decision is made.
Then we find the smallest values by the rows and columns of the matrix.
Then, for each matrix zero, we calculate the sum of the smallest values in the rows and columns where the corresponding zeros are located, without taking into account the zeros themselves.
The resulting values are written in parentheses.
We find the sum of the smallest values in rows and columns and thus determine the price of movement through the current branch edge.
H(1,4) = 7
Because H(1,4) <= H(1*,4*), then we include this edge in the general path.
Result:
The cost of the entire route:
D = 18 + 0 + 7 + 0 + 0 = 25
Route:
H(2,1) => H(1,4) => H(3,2) => H(4,3)
Frequently asked questions
What does the traveling salesman calculator find?
It finds the shortest possible route that visits every city exactly once and returns to the start, given a matrix of pairwise distances or costs.
How does the branch-and-bound method work here?
It builds a search tree and computes a lower bound on the tour length for each branch by reducing rows and columns of the cost matrix. Branches that cannot beat the best tour found so far are pruned, which avoids checking every permutation.
Why are the diagonal cells marked "M"?
The diagonal represents a city's distance to itself, which is never part of a tour. It is set to a very large value (M) so the algorithm never selects it.
Does the calculator always return the exact shortest tour?
Yes. Branch-and-bound is an exact method — it explores enough of the tree to guarantee the optimum, skipping only branches that provably cannot improve on the best known tour.