node-tspsolver

Travelling salesman solver for nodejs

This solver uses Simulated Annealing with optional periodic reheating.

Initial solution is constructed using Nearest Neighbour heuristic.

Tour transformations used in the local search step: Stochastic 2-opt, translation and swapping.

The solver is implemented in C++ and doesn't use the nodejs main event loop for running, hence non-blocking.

Signature:

function solveTsp(costMatrix, roundtrip, options) returns a promise

Arguments:

costMatrix - 2d array of costs .. costMatrix[i][j] gives cost between ith and jth points

roundtrip - whether salesman needs to get back to starting point, ie point at index 0. If false, point at n - 1 is treated as the end point

options - {
    N - 'number of iterations' default: 1000000,
    T - 'Initial temperature' default: 100,
    lambda - 'Annealing parameter' default: 0.985,
    reheatInterval - 100000,
}

Install:

npm install node-tspsolver

NOTE:

Since this is a C++ addon, it requires node-gyp to be properly configured in your machine. Please go through the instructions provided in https://github.com/nodejs/node-gyp to properly set it up for your platform.

Examples:

var solver = require('node-tspsolver')

var costMatrix = [
    [0, 1, 3, 4],
    [1, 0, 2, 3],
    [3, 2, 0, 5],
    [4, 3, 5, 0]
]

solver
    .solveTsp(costMatrix, true, {})
    .then(function (result)) {
        console.log(result) // result is an array of indices specifying the route.
    })