Skip to content

rtwalz/node-tspsolver

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

15 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Build Status

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.
    })

About

Travelling salesman solver for nodejs

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages

  • C++ 64.4%
  • JavaScript 31.6%
  • Python 3.7%
  • C 0.3%