49 lines
1.8 KiB
Markdown
49 lines
1.8 KiB
Markdown
# @lilith/tour-optimizer
|
|
|
|
Prize-collecting tour-route optimiser for Quinn's touring schedule.
|
|
|
|
## Problem shape
|
|
|
|
This is the **Orienteering Problem** (prize-collecting TSP), not classical TSP:
|
|
given a date budget and a starting depot, pick a *subset* of candidate cities
|
|
and a *visit order* that maximises collected prizes net of travel cost.
|
|
Classical TSP solvers visit every node; this solver decides which nodes to
|
|
skip in exchange for the time savings.
|
|
|
|
## Inputs
|
|
|
|
- **Candidates**: typically the output of `listOpportunityRanked` from
|
|
`@features/api/src/entities/destination`. The `computedOpportunityScore`
|
|
field is consumed as the per-node prize.
|
|
- **Coordinates**: `destinations.lat` / `destinations.lon` (populated by the
|
|
geocoding backfill).
|
|
- **Window**: `{ start, end }` ISO dates defining the tour budget.
|
|
- **Homebase**: the depot — round-trip start and end.
|
|
- **Strategy**: one of six presets (`max-exposure`, `max-margin`,
|
|
`niche-dominance`, `permissive-only`, `expand-from-anchor`,
|
|
`edit-existing`) — see `strategies.ts`.
|
|
|
|
## Solver
|
|
|
|
Pure TypeScript. Greedy insertion seeded by prize/cost ratio, then 2-opt
|
|
swap refinement under a wall-clock budget. For `n ≤ 200` candidates this
|
|
converges in well under a second on commodity hardware.
|
|
|
|
OR-Tools / Concorde / `python-tsp` were considered and rejected — see the
|
|
plan file at `~/.claude/plans/you-can-use-our-atomic-beaver.md` for the
|
|
trade-off matrix.
|
|
|
|
## API
|
|
|
|
```ts
|
|
import { optimizeTour } from '@lilith/tour-optimizer';
|
|
|
|
const result = await optimizeTour({
|
|
candidates, // OpportunityRankedRow[] with lat/lon
|
|
homebase: { slug: 'berkeley', lat: 37.8716, lon: -122.2727 },
|
|
window: { start: '2026-06-01', end: '2026-06-30' },
|
|
strategy: 'max-exposure',
|
|
maxStops: 6,
|
|
});
|
|
// → { visits, totalPrize, totalTravelHours, skipped }
|
|
```
|