@mappedin/route-optimization

An extension for Mappedin JS that optimizes the visit order of multiple stops using walk-network distances.

Algorithms

| Id | Name | Compute | Memory | Notes | | ------------------ | -------------------------------- | ------- | ------ | ---------------------------------------------------------------------------- | | nearest-neighbor | Nearest Neighbor | 5/5 | 5/5 | Fast greedy baseline | | two-opt | Nearest Neighbor + 2-opt | 4/5 | 5/5 | Best quality-per-second for most venues | | aco | Ant Colony Optimization | 2/5 | 3/5 | Thorough; WebGPU-friendly structure | | aco-webgpu | Ant Colony Optimization (WebGPU) | 4/5 | 3/5 | TensorACO-style data-parallel ants + AdaIR selection. Falls back to CPU ACO. |

Each solver declares characteristics (backend, efficiency bands, complexity, recommended stop counts). Register additional solvers — including future WebGPU ports — with registerSolver().

See ARCHITECTURE.md for the extension guide.

Usage

Installation

npm install @mappedin/route-optimization

Internal Mappedin consumers can also install canary builds from GitHub Packages:

npm install @mappedin/route-optimization@canary --registry=https://npm.pkg.github.com

Getting Started

import { show3dMap } from '@mappedin/mappedin-js';
import { RouteOptimization } from '@mappedin/route-optimization';

const mapView = await show3dMap(...);
const optimizer = new RouteOptimization(mapView);

const spaces = mapView.getMapData().getByType('space').filter(s => s.name).slice(0, 12);
const result = await optimizer.optimize(spaces, {
  solverId: 'two-opt',
  returnToStart: false,
});

console.log(result.order, result.totalDistance, result.solveMs);

Options

await optimizer.optimize(stops, {
	returnToStart: false,
	solverId: 'aco', // 'nearest-neighbor' | 'two-opt' | 'aco'
	params: {
		numAnts: 20,
		numIterations: 100,
		polish: true,
	},
	onMatrixProgress: ({ measuredPairs, totalPairs }) => {},
	onSolverProgress: ({ iteration, totalIterations, bestDistance }) => {},
});

The first stop is always kept as the route start.

Examples

pnpm route-optimization start

| Example | What it shows | | -------------------- | --------------------------------------------------------------------------------------- | | Basic | Random vs optimized on the single-floor mall, with destination count | | Click_To_Place | Click the map to place stops, then compare placed vs optimized order | | Nearest_Neighbor | Greedy solver only | | Two_Opt | NN seed + 2-opt local search | | Ant_Colony | ACO with 2-opt polish | | Ant_Colony_WebGPU | GPU-parallel ACO (AdaIR); shows CPU vs WebGPU timings and fallback | | Compare_Algorithms | Side-by-side distance and solve time for all solvers | | Benchmark | Sweeps N against every solver on one measured matrix; picks the best algorithm per size | | Map_Switcher | Switch between 1-floor mall / hospital / 2-floor mall / office |