TravelingSalesperson: Solver for Traveling Salesperson Problem

In rlemon: R Access to LEMON Graph Algorithms

Solver for Traveling Salesperson Problem

Description

Finds approximations for the travelling salesperson problem using approximation algorithms on graphs. NOTE: LEMON's TSP uses a complete graph in its backend, so expect less performance on sparse graphs.

Usage

TravelingSalesperson(
  arcSources,
  arcTargets,
  arcDistances,
  numNodes,
  defaultEdgeWeight = 999999,
  algorithm = "Christofides"
)

TravellingSalesperson(
  arcSources,
  arcTargets,
  arcDistances,
  numNodes,
  defaultEdgeWeight = 999999,
  algorithm = "Christofides"
)

Arguments

arcSources	Vector corresponding to the source nodes of a graph's edges
arcTargets	Vector corresponding to the destination nodes of a graph's edges
arcDistances	Vector corresponding to the distances of a graph's edges
numNodes	The number of nodes in the graph
defaultEdgeWeight	The default edge weight if an edge is not-specified (default value 999999)
algorithm	Choices of algorithm include "Christofides", "Greedy", "Insertion", "NearestNeighbor", and "Opt2". "Christofides" is the default.

Details

For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00618.html.

Value

A named list with 1) "node_order": the vector of visited nodes in order, and 2) "cost": the total tour cost.

rlemon documentation built on Feb. 16, 2023, 5:33 p.m.