tsp_route_finder
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_mapor 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 aTspResultwithroute,closedRoute,totalDistance,isOptimal,strategyandreorder().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 withendIndex. - Custom distance functions, through the
distance:parameter. - Choice of algorithm with
TspStrategy, plus an optionaltimeLimit. TspLocationwithdistanceTo(), and thehaversineDistance()andTspRouteFinder.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))(orcompute(...)).
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
Libraries
- tsp_route_finder
- Traveling Salesman Problem (TSP) solver for Dart and Flutter.