TSP_nearest_Rcpp: TSP Nearest Insertion Algorithm (C++ Implementation)

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

TSP Nearest Insertion Algorithm (C++ Implementation)

Description

This function implements the **Nearest Insertion** heuristic approach for solving the Traveling Salesman Problem (TSP) in C++ and is exported to R using Rcpp. The algorithm builds the tour by inserting cities into the existing tour by selecting the nearest city to any city already in the tour.

The algorithm starts from a specified city and iteratively inserts cities one by one, choosing the nearest city to any city already in the tour. In "all" mode, the best tour is selected by testing all possible starting cities and computing the total distance for each tour.

Usage

TSP_nearest_Rcpp(data, type = "one")

Arguments

data	A numeric matrix or data frame where each row represents a city and each column represents the coordinates of that city (e.g., x and y coordinates in 2D space).
type	A character string specifying how the starting city is chosen. Options include: "one" (default): Randomly selects a single starting city. "all": Tests all cities as possible starting points and selects the best tour.

Details

The algorithm is a heuristic approach and does not guarantee the global optimal solution, but aims to find a good solution in a reasonable amount of time.

• Time Complexity: O(n³), where 'n' is the number of cities. The algorithm computes the best insertion for each city and tries every possible insertion position.

• Space Complexity: O(n²) due to the storage of the distance matrix.

The result is a tour with the shortest found distance, based on the starting point(s) and insertion method.

Value

A numeric vector representing the order of cities in the shortest found tour. The vector is assigned the class "TSP".

Examples

n <- 40
villes <- matrix(runif(2*n), n, 2)
TSP_nearest_Rcpp(villes, type = "one")

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