TSP_cheapest_Rcpp: TSP Cheapest Insertion Algorithm (C++ Implementation)

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

TSP Cheapest Insertion Algorithm (C++ Implementation)

Description

This function implements the Cheapest 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 in the position that minimizes the increase in tour length.

The algorithm starts from a specified city and iteratively inserts cities one by one, choosing the insertion position that results in the cheapest (minimum) increase in the total distance at each step. In "all" mode, the best tour is selected by testing all possible starting cities and computing the total distance for each tour.

Usage

TSP_cheapest_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_cheapest_Rcpp(villes, type = "one")

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