TSP_farthest: Farthest Insertion Algorithm for Solving the Traveling...

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

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

Description

This function solves the Traveling Salesman Problem (TSP) using the farthest insertion heuristic. The algorithm starts from the farthest pair of cities and then iteratively inserts the next city at the position that increases the tour distance the least. The function can also test all possible starting cities if 'type = "all"', using the 'greedy_TSP_max_all' helper function.

Usage

TSP_farthest(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 chosen as the farthest city from an initial random selection. 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 farthest insertion starting from one city
best_tour <- TSP_farthest(cities, type = "one")
# Solve TSP using farthest insertion testing all starting cities
best_tour_all <- TSP_farthest(cities, type = "all")

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