View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Dynamic Programming solution to the TSP

4.0 | 3 ratings Rate this file 24 Downloads (last 30 days) File Size: 3.04 KB File ID: #31454 Version: 1.0

Dynamic Programming solution to the TSP



This function solves the Traveling Salesman Problem (TSP) using Dynamic programming (DP).

| Watch this File

File Information

The function is based on the paper by Held and Karp from 1962. The DP is guaranteed to provide the accurate (optimal) result to the TSP, but the time complexity of this algorithm is O(2^n n^2), which limits the use of this algorithm to 15 cities or less.

NOTE: For reasonable runtime, please do not try to calculate a tour of more than 13 cities. DP is not for large sets of cities.


This file inspired Travelling Salesman Problem By Dynamic Programming.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (14)
21 Feb 2017 Elad Kivelevitch


As the help states, if there are no inputs at all, a random set of 10 cities will be generated. I did not design this to work with only a Dmatrix. I also don't see an example Dmatrix defined in the help.

Here is an example of how to use this function:

cities = [0 0; 10 0; 10 10; 0 10];
Dmatrix = [0 10 14 10; 10 0 10 14; 14 10 0 10; 10 14 10 0]; %Costs are rounded to integers

[OptimalTour, MinCost] = tsp_dp1(cities);
[OptimalTour, MinCost] = tsp_dp1(cities, Dmatrix);

Comment only
07 Feb 2017 Jer Verme

Hi I am trying to use your code but when i enter the example Dmatrix and then the start of the matrix it doesn't work it gives "undifned function or variable cities"
if I leave cities out of the command it always gives me the route 1-2-3-1 how can I fix this?

07 Feb 2017 Jer Verme

27 Aug 2016 Elad Kivelevitch


Please type (in your Matlab prompt)
>> help tsp_dp1

As the help says, the first input is a list of city locations. This should be provided as a matrix that has n rows (n is the number of cities) and 2 or 3 columns. 2 columns for a 2D problem, 3D columns for a 3D problem. For example, three cities in 2D looks like this:

>> cities = [0 0; 100 0; 0 100];

You can leave the second input argument empty. In that case, the Dmatrix will be calculated automatically by the function using the default Euclidean norm. In other words, for the cities matrix defined above:

>> [OptimalTour,mincost]=tsp_dp1(cities)

Will give you the solution.

If you want a non-default Dmatrix, for example, if the cost is non Euclidean, and/or asymmetric, you can specify it as an n-by-n matrix. This would mean n rows and n columns. Again, n is the number of cities. To avoid travel from each city to itself, put inf on the diagonal.

An example for the Dmatrix for 3 cities is:

>> Dmatrix = [inf 100 100; 100 inf 144; 100 144 inf];

Then to calculate the solution do:

>> [OptimalTour,mincost]=tsp_dp1(cities, Dmatrix)

I hope this helps you get started.


Comment only
27 Aug 2016 Della Tambunan

I did not understand how to input dmatrix and cities. how to make that listing program? can you help me?

Comment only
08 Apr 2016 JAVAD

JAVAD (view profile)


Comment only
07 May 2015 zhang zhaozhi


Comment only
17 Nov 2012 Thanapan

19 May 2012 Leonardo BOrges

Cool i need this solutions for my study academic, thak you

Comment only
22 Feb 2012 Vahid

Vahid (view profile)


Comment only
22 Feb 2012 Elad Kivelevitch

As I said, I haven't tested it for an asymmetric TSP. You will need to pass a list of cities with n rows and 2 columns. This list will not be used in calculating the Dmatrix, but will be used for knowing the number of cities.

You know, it's a MATLAB code that you could modify and try to run your own versions...

Comment only
22 Feb 2012 Vahid

Vahid (view profile)

If I put an assymetric Dmatrix, what should I put as the cities coordinates?

Comment only
14 Feb 2012 Elad Kivelevitch

Correct. Just a symmetric TSP and only for a limited number of cities.

However, now that I think about it, I have no idea what happens if you use an asymmetric Dmatrix. Maybe it will work. Try it sometime.

Comment only
14 Feb 2012 Vahid

Vahid (view profile)

Thanks for the code. Is is only working for symmetric TSP?

Comment only

Contact us