TravelingSalesperson {rlemon}

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.