tsp_pilot_example.R

#' get next best pilot stop using nearest neighbor
#'
#' @param tour 
#' @param dima 
#'
#' @return
#' @export
get_best_pilot_stop <- function(tour, dima) {
  stops <- 1:nrow(dima)
  potential_stops <- stops[-tour]
  if (length(potential_stops) == 0) {
    stop("nothing to complete!")
  }
  best_cost <- Inf
  best_stop <- NA
  for (stop in potential_stops) {
    temp_tour <- c(tour, stop)
    nn_tour <- complete_nn(temp_tour, dima)
    cost <- get_tour_cost(nn_tour, dima)
    if (cost < best_cost) {
      best_cost <- cost
      best_stop <- stop
    }
  }
  return (best_stop)
}

#' get tour cost
#'
#' @param tour the tour
#' @param dima the dima
#'
#' @return
#' @export
get_tour_cost <- function(tour, dima) {
  cur_pos <- tour[1];
  tot_dist <- 0;
  for (i in 2:length(tour)) {
    tot_dist <- tot_dist + dima[cur_pos, tour[i]]
    cur_pos <- tour[i]
  }
  return(tot_dist)
}

#' complete the tour using nearest neighbor
#'
#' @param temp_tour 
#' @param dima 
#'
#' @return
#' @export
complete_nn <- function(temp_tour, dima) {
  while (length(temp_tour) < nrow(dima)) {
    next_stop <- get_best_nn_stop(temp_tour, dima)
    temp_tour <- c(temp_tour, next_stop)
  }
  # return to start
  temp_tour <- c(temp_tour, temp_tour[1])
  return (temp_tour)
}

#' get next best greedy stop using nearest neighbor
#'
#' @param temp_tour 
#' @param dima 
#'
#' @return
#' @export
get_best_nn_stop <- function(temp_tour, dima) {
  stops <- 1:nrow(dima)
  potential_stops <- stops[-temp_tour]
  cur_pos <- tail(temp_tour, 1)
  best_id <- which.min(dima[cur_pos, potential_stops])
  best_next <- potential_stops[best_id]
  return(best_next)
}

#' build best tour using pilot method based on NN-heuristic for tour-completion
#'
#' @param dima 
#'
#' @return
#' @export
get_nn_based_pilot_tsp <- function(dima) {
  # start at 1
  tour <- c(1)
  cat("starting at: ", tour, "\n")
  while (length(tour) < nrow(dima)) {
    next_stop <- get_best_pilot_stop(tour, dima)
    cat("next best pilot stop is: ", next_stop, "\n")
    tour <- c(tour, next_stop)
  }
  # return to start
  tour <- c(tour, tour[1])
  return(tour)
}

# generate the best TSP tour using the pilot method and the nearest neighbor
# heuristic to complete the tour
dima <- matrix(c(0,5,3,19,7,13,0,1,18,6,12,4,0,14,6,11,9,8,0,10,23,11,7,21,0), 
               byrow = T, nrow = 5)
tour <- get_nn_based_pilot_tsp(dima)
cat("tour is: ", tour)

Generate a TSP solution based on a given distance matrix applying pilot method and using nearest neighbor for greedy tour completion and total cost-estimation method.