TSP_cheapest: Cheapest Insertion Algorithm for Solving the Traveling...

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

Cheapest Insertion Algorithm for Solving the Traveling Salesman Problem (TSP)

Description

This function solves the Traveling Salesman Problem (TSP) using the cheapest insertion heuristic. It generates a tour starting from either one city or all cities (iteratively) as possible starting points, and progressively inserts the remaining cities at the position that results in the least increase in distance.

Usage

TSP_cheapest(data, type = "one")

Arguments

data	A numeric matrix or data frame of coordinates where each row represents a city and each column represents the x and y coordinates (for a 2D TSP).
type	A character string specifying the type of starting city selection. If 'type = "one"', the starting city is randomly chosen. If 'type = "all"', the algorithm tests all possible starting cities and selects the best one.

Value

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

Examples

# Generate a random set of 5 cities
cities <- matrix(runif(10), ncol = 2)
# Solve TSP using cheapest insertion starting from one city
best_tour <- TSP_cheapest(cities, type = "one")
# Solve TSP using cheapest insertion testing all starting cities
best_tour_all <- TSP_cheapest(cities, type = "all")

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