tsp_route_finder

pub package License: MIT

A fast, dependency-free Traveling Salesman Problem (TSP) solver for Dart and Flutter. Give it a list of stops and it tells you the order to visit them so the total distance is as short as possible. It works for delivery routes, field-sales visits, pickup planning and trip itineraries.

Features

  • Optimal routes for small inputs. Up to 12 stops are solved exactly by default (Held–Karp dynamic programming), and up to 16 on request.
  • Near-optimal routes for large inputs. Nearest neighbor followed by 2-opt and Or-opt local search. 1,000 stops take about 0.1 s.
  • Round trips or one-way routes, with an optional fixed final stop.
  • GPS coordinates or your own costs. Distance defaults to haversine (great-circle) km. You can also pass a custom distance function or a distance matrix, for example road distances or driving times from Google Distance Matrix, OSRM or Mapbox. Asymmetric matrices (one-way streets, traffic) are supported.
  • Pure Dart, no dependencies. Runs on Android, iOS, web, Windows, macOS, Linux and the server, and works alongside google_maps_flutter, flutter_map or any other map package.

New in 0.1.0

  • Much better routes. About 16% shorter than 0.0.x on typical inputs, and guaranteed optimal for small ones.
  • TspRouteFinder.solve. New main entry point that returns a TspResult with route, closedRoute, totalDistance, isOptimal, strategy and reorder().
  • TspRouteFinder.solveMatrix. Optimize with real road distances or travel times, including asymmetric costs.
  • One-way routes. Use returnToStart: false, and optionally set a fixed last stop with endIndex.
  • Custom distance functions, through the distance: parameter.
  • Choice of algorithm with TspStrategy, plus an optional timeLimit.
  • TspLocation with distanceTo(), and the haversineDistance() and TspRouteFinder.routeDistance() helpers.
  • No Flutter dependency. The package is now pure Dart, so it also runs on servers, CLIs and web/WASM.
  • Fully documented, with a runnable example, tests and a benchmark.
  • Backwards compatible. The 0.0.3 API still works (deprecated). See Migrating from 0.0.x.

Algorithms

TspStrategy Algorithm Route quality Speed Max stops Use when
auto (default) exact up to 12 stops, optimized above Optimal / near-optimal Fast Unlimited You're not sure. This is the right choice almost always.
exact Held–Karp dynamic programming, O(n²·2ⁿ) Optimal (guaranteed) ~14 ms for 16 stops 16 You need the provably shortest route.
optimized Nearest neighbor + 2-opt + Or-opt local search Near-optimal (≈0.3% from optimal on 10–12 stops) ~0.1 s for 1,000 stops Thousands Large inputs. Supports timeLimit.
nearestNeighbor Greedy: always go to the closest unvisited stop ~10–20% longer than optimal Fastest, O(n²) Thousands Quick previews; the behaviour of v0.0.x.

All strategies support round trips, one-way routes and fixed end stops, and work with symmetric or asymmetric distances.

Route quality

Average results on random stops around Cairo, from benchmark/benchmark.dart:

Stops Nearest neighbor (v0.0.x) Optimized (v0.1.0) Optimal Time
10 189.5 km 168.2 km 167.9 km < 1 ms
12 199.8 km 180.9 km 180.4 km < 1 ms
100 537.4 km 449.1 km (−16%) – < 1 ms
500 1160.9 km 975.5 km (−16%) – 24 ms
1000 1638.4 km 1374.2 km (−16%) – 105 ms

Installation

dart pub add tsp_route_finder
# or
flutter pub add tsp_route_finder

Usage

import 'package:tsp_route_finder/tsp_route_finder.dart';

const stops = [
  TspLocation(latitude: 30.0454, longitude: 31.2332, name: 'Cairo'),
  TspLocation(latitude: 30.7865, longitude: 31.0012, name: 'Tanta'),
  TspLocation(latitude: 31.0407, longitude: 31.3804, name: 'Mansoura'),
  TspLocation(latitude: 24.0895, longitude: 32.8993, name: 'Aswan'),
  TspLocation(latitude: 31.2009, longitude: 29.9278, name: 'Alexandria'),
];

final result = TspRouteFinder.solve(stops, startIndex: 0);

print(result.route);          // [0, 3, 4, 1, 2]: indices in visiting order
print(result.closedRoute);    // [0, 3, 4, 1, 2, 0]: handy for a polyline
print(result.totalDistance);  // total km, including the way back
print(result.isOptimal);      // true: small inputs are solved exactly
print(result.reorder(stops)); // your objects, in visiting order

One-way routes

// Start at the warehouse, end wherever is shortest.
TspRouteFinder.solve(stops, startIndex: 0, returnToStart: false);

// Start at the warehouse and finish at the driver's home (index 3).
TspRouteFinder.solve(stops, startIndex: 0, endIndex: 3, returnToStart: false);

Road distances or travel times

Straight-line distance is a good approximation, but if you have real road costs, pass them as a matrix where matrix[i][j] is the cost from i to j:

final minutes = [
  [0, 12, 30, 25],
  [14, 0, 18, 22],
  [28, 20, 0, 9],
  [26, 21, 11, 0],
];
final result = TspRouteFinder.solveMatrix(minutes);

Or plug in any cost function:

TspRouteFinder.solve(stops, distance: (a, b) => myCost(a, b));

Choosing an algorithm

See the Algorithms table above for details.

// Guaranteed shortest route (up to 16 stops).
TspRouteFinder.solve(stops, strategy: TspStrategy.exact);

// Large input, stop improving after 200 ms.
TspRouteFinder.solve(
  manyStops,
  strategy: TspStrategy.optimized,
  timeLimit: const Duration(milliseconds: 200),
);

Flutter tips

  • Draw the route with result.closedRoute.map((i) => LatLng(stops[i].latitude, stops[i].longitude)).
  • For thousands of stops, run the solver off the UI thread: await Isolate.run(() => TspRouteFinder.solve(stops)) (or compute(...)).

Migrating from 0.0.x

The 0.0.3 API still works, but it is deprecated and will be removed in 1.0.0:

0.0.3 0.1.0
CitiesLocations(cityName: …, latitude: …, longitude: …) TspLocation(name: …, latitude: …, longitude: …)
await TspPackage.calculateTspRoute(locations: l, startingLocationIndex: s) TspRouteFinder.solve(l, startIndex: s).route
calculateDistance(a, b) a.distanceTo(b) or haversineDistance(a, b)

TspPackage.calculateTspRoute now uses the improved algorithm automatically.

Contributing

Issues and pull requests are welcome at github.com/kareemmohamed111/tsp_route_finder.

License

MIT

Libraries

tsp_route_finder
Traveling Salesman Problem (TSP) solver for Dart and Flutter.