TSP_B_and_B: Branch and Bound Algorithm for Solving the Traveling Salesman...

In vrunge/M2algorithmique: Example of an Rcpp package for M2 Data Science students

Branch and Bound Algorithm for Solving the Traveling Salesman Problem (TSP)

Description

This function implements the Branch and Bound algorithm to solve the Traveling Salesman Problem (TSP). It explores all possible tours but efficiently prunes branches that cannot lead to a better solution than the best one found so far by using a lower bound to eliminate suboptimal paths.

The algorithm starts from a root node (an empty path) and recursively explores all possible tours by adding unvisited cities one by one, while applying the bound function to prune branches of the search tree. Once all cities are visited, the function checks if the cost of the tour is better than the current best tour.

Usage

TSP_B_and_B(data)

Arguments

data	A numeric matrix or data frame where each row represents a city and each column represents its coordinates (for a 2D TSP).

Value

A list containing the following elements:

best_tour

A numeric vector representing the order of cities in the optimal tour. The class attribute is set to "TSP".

best_cost

The total cost of the optimal tour.

nb_call

The total number of recursive calls made during the algorithm execution.

Examples

# Generate a random set of cities
cities <- matrix(runif(10), ncol = 2)
# Solve TSP using Branch and Bound
result <- TSP_B_and_B(cities)
print(result$best_tour)
print(result$best_cost)

vrunge/M2algorithmique documentation built on April 5, 2025, 4:06 a.m.