Solver for Traveling Salesperson Problem

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.

Value

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

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.