Solving the Traveling Salesman Problem with Dynamic Programming

The Traveling Salesman Problem (TSP) asks for the shortest possible route through a collection of cities, with every city visited exactly once before returning to the starting point. It is a classic combinatorial optimisation problem and a useful case study for recursion, bitmasks, graph algorithms, and complexity analysis.

A straightforward search checks every possible ordering of the cities. That approach quickly becomes impractical because the number of tours grows factorially. Dynamic programming improves the situation by recognising that many different partial routes end in the same city after visiting the same subset of locations.

This exact method is relevant to delivery scheduling, warehouse collection, circuit-board drilling, robot navigation, and transport planning. For example, a courier operating between Sydney, Canberra, Melbourne, and regional depots can use the same mathematical model, even though real traffic, one-way streets, and delivery windows require additional constraints.

Approach	Exact result	Approximate time complexity	Typical use
Brute-force permutations	Yes	(O(n!))	Very small inputs
Dynamic programming	Yes	(O(n^2 2^n))	Small to medium inputs
Nearest neighbour	No	(O(n^2))	Fast initial route
Branch and bound	Yes, often faster in practice	Worst case (O(n!))	Moderate inputs with pruning
Minimum spanning tree approximation	No	Polynomial	Larger metric instances

Modelling The Route As A Graph

Represent each city as a vertex in a weighted graph. The edge from city (i) to city (j) stores the travel cost, such as distance, fuel usage, time, or a monetary price. These costs can form a complete graph, meaning every city has a direct cost to every other city, even if that cost represents a calculated road journey rather than a single road.

Let the cities be numbered from (0) to (n-1), with city (0) chosen as the starting point. A route must begin at city (0), visit all other cities once, and return to city (0). If the input is a distance matrix, distance[i][j] gives the cost of travelling from (i) to (j).

The usual textbook version assumes symmetric costs, where travelling from (i) to (j) costs the same as travelling back. Real Australian transport networks are often asymmetric: a route through Sydney may be affected by toll roads, bridges, or one-way streets, while long distances between Perth and Adelaide can make road and air logistics behave very differently. The dynamic programming recurrence still works when distance[i][j] and distance[j][i] differ.

Before running the algorithm, check whether the graph contains missing edges. A missing connection can be represented by infinity, but the implementation must ensure that an unreachable partial route is never extended as if it were valid.

Defining The Dynamic Programming State

The central idea is to store the best route for every visited subset and final city. Use a bitmask to represent the subset: bit (i) is set when city (i) has been visited. The state

[ dp[mask][j] ]

means the minimum cost of starting at city (0), visiting exactly the cities in mask, and finishing at city (j).

For example, with five cities, the mask 01101 indicates that cities (0), (2), and (3) have been visited, depending on the chosen bit ordering. Bitmasks are efficient because checking membership becomes a bitwise operation rather than a search through a list.

The base state is:

[ dp[1 << 0][0] = 0 ]

This says that the route has visited only the starting city and currently ends there at zero cost. Every other state initially has infinity as its value.

To extend a route, select an unvisited city (j). If the current route is represented by mask and ends at (i), then:

[ dp[mask ,|, (1 << j)][j]

\min\left( dp[mask ,|, (1 << j)][j], dp[mask][i] + distance[i][j] \right) ]

The new state records the same route plus its final move to (j). This is the optimal-substructure property: once the visited subset and final city are known, the earlier order only matters through the best cost already stored.

The final answer is obtained after all cities have been visited. The route must then return to the start:

[ \min_{j \ne 0} \left(dp[(1 << n)-1][j] + distance[j][0]\right) ]

The final return trip is easy to overlook. Without it, the algorithm solves a shortest Hamiltonian path rather than a closed tour.

Building The Recurrence In Code

A compact implementation uses a two-dimensional array with (2^n) rows and (n) columns. The number of rows comes from every possible subset of cities. In Python, a typical implementation looks like this:

def travelling_salesman(distance):
    n = len(distance)
    infinity = float("inf")
    dp = [[infinity] * n for _ in range(1 << n)]

    dp[1][0] = 0

    for mask in range(1 << n):
        for last in range(n):
            current = dp[mask][last]

            if current == infinity:
                continue

            for nxt in range(n):
                if mask & (1 << nxt):
                    continue

                new_mask = mask | (1 << nxt)
                candidate = current + distance[last][nxt]

                if candidate < dp[new_mask][nxt]:
                    dp[new_mask][nxt] = candidate

    full_mask = (1 << n) - 1
    return min(
        dp[full_mask][last] + distance[last][0]
        for last in range(1, n)
    )

The outer loop visits every subset, the next loop considers each possible final city, and the inner loop tries each unvisited destination. Since there are (2^n) masks, (n) possible final cities, and up to (n) transitions per state, the time complexity is (O(n^2 2^n)). The memory complexity is (O(n2^n)).

For readers moving between languages, the same bitmask operations are available in C programming, where a flat array can reduce allocation overhead. In C, use a sufficiently wide unsigned integer for masks; a standard 32-bit mask cannot represent more than 32 cities, and shifting beyond the type width creates incorrect results.

Recovering The Actual Tour

The cost alone may be enough for a mathematical exercise, but routing applications usually need the sequence of cities. Add a second array called parent, where parent[mask][j] stores the city immediately before (j) in the best route for that state.

Whenever a transition improves dp[new_mask][nxt], assign:

parent[new_mask][nxt] = last

After filling the dynamic programming array, choose the final city that minimises the complete cost, including the return to city (0). Then repeatedly remove the current city from the mask and follow the stored parent pointer. Reverse the collected sequence to obtain the forward route.

A useful detail is that the starting city should not be selected as an intermediate destination. It belongs in the initial mask and appears again only when the completed route returns home. If the application treats routes that differ only by rotation as identical, fixing city (0) as the start removes duplicate representations.

Route reconstruction also helps with debugging. For a small four-city example, compare the recovered order against every permutation by brute force. Testing tiny cases can expose incorrect bit operations, a missing return edge, or a parent pointer that was updated at the wrong time.

Choosing Exact And Practical Methods

Held–Karp dynamic programming is exact, but its exponential growth still limits the input size. Doubling the number of cities does far more than double the memory: the subset count itself doubles for every additional city. It is generally suitable for educational examples and small operational batches, while larger commercial routing systems use specialised solvers, integer programming, branch and bound, or approximation algorithms.

For a large delivery network in Brisbane or Melbourne, a practical system may first cluster stops by suburb, depot, or delivery window. It can then solve smaller TSP instances inside each cluster. A nearest-neighbour route can provide a quick initial solution, while 2-opt or 3-opt local search improves it by replacing pairs or triples of edges.

Machine learning may help estimate travel time, demand, or service duration, but it does not replace the combinatorial optimiser. A traffic model can produce a more realistic cost matrix, while the TSP algorithm chooses a route using those predicted costs. Background material on machine learning is useful when building that prediction layer.

Practical Implementation Recommendations

• Fix one city as the starting point to remove equivalent cyclic rotations.
• Use kilometres, minutes, fuel cost, or dollars consistently across every edge.
• Represent unreachable connections with infinity and skip invalid transitions.
• Test the dynamic program against brute force for small graphs.
• Store parent pointers when the application needs the actual route.
• Consider heuristics or clustering once the number of cities makes (2^n) memory impractical.

Real logistics also contains constraints that the basic TSP model ignores. Australian delivery operations may need vehicle capacity, driver breaks, school-zone restrictions, toll preferences, or time windows for customers. A route through Perth’s widely separated suburbs has different operational costs from a compact inner-Melbourne route, even when both contain the same number of stops. Those requirements lead to variants such as the vehicle routing problem, capacitated TSP, and time-window routing.

Dynamic programming remains valuable because it makes the core trade-off visible. It converts repeated subproblems into reusable states, gives an exact answer for manageable input sizes, and provides a foundation for understanding more advanced optimisation methods. Once the state representation and transition are correct, the same reasoning transfers to many subset-based problems beyond travelling routes.