Traveling Salesman problem using Branch-and-Bound technique.

 Algorithm:

Algorithm TSPBranchAndBound(distances)

{

 n := size(distances)

 best_cost := infinity

 best_path := null

 queue := [(0, [0], set([0]))] // (cost, path, visited)

 while queue is not empty do

 cost, path, visited := pop(queue)

 if length(path) = n then

 cost += distances[path[-1], 0]

 if cost < best_cost then

 best_cost := cost

 best_path := path

 else

 for i in range(n) do

 if i not in visited then

 new_path := path + [i]

new_visited := visited.union(set([i]))

 new_cost := cost + distances[path[-1], i]

 for j in range(n) do

 if j not in new_visited then

 new_cost += np.min(distances[j, list(new_visited)])

 if new_cost < best_cost then

 push(queue, (new_cost, new_path, new_visited))

 return best_path, best_cost

}

Source Code:

import numpy as np

def tsp_branch_and_bound(distances):

 n = distances.shape[0]

 # Initialize variables

 best_cost = np.inf

 best_path = None

 # Initialize priority queue with starting node as root

 queue = [(0, [0], set([0]))] # (cost, path, visited)

 while queue:

 # Pop node with lowest cost from queue

 cost, path, visited = queue.pop(0)

 # Check if path is complete

 if len(path) == n:

 # Add cost of returning to starting node

 cost += distances[path[-1], 0]

 # Check if this path is better than previous best

 if cost < best_cost:

 best_cost = cost

 best_path = path

else:

 # Add children to queue

 for i in range(n):

 if i not in visited:

 new_path = path + [i]

new_visited = visited.union(set([i]))

# Calculate lower bound on cost of this path

new_cost = cost + distances[path[-1], i]

for j in range(n):

 if j not in new_visited:

 new_cost += np.min(distances[j, list(new_visited)])

 # Add child node to queue

if new_cost < best_cost:

 queue.append((new_cost, new_path, new_visited))

 # Return best path and cost

 return best_path, best_cost

distances = np.array([[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20,

25, 30, 0]])

path, cost = tsp_branch_and_bound(distances)

print("Best path:", path)

print("Best cost:", cost)