Core Route Planning Algorithm
Relevant source files
The following files were used as context for generating this wiki page:
The Core Route Planning Algorithm is the deterministic engine responsible for generating multi-stop trip geometries, identifying relevant Park4Night (P4n) locations along that route, and ranking those locations based on user preferences and detour distance. It ensures that users only see relevant stops within a specific distance (corridor) from their planned path.
Sources: src/lib/planner.ts:1-5, README.md:54-61
High-Level Architecture
The system operates as a multi-stage pipeline. It starts with external route generation, moves through geographic sampling and data retrieval, and concludes with corridor filtering and heuristic scoring.
The logic is exposed via a POST endpoint at /api/plan, which orchestrates the call to planAndSearch.
Sources: src/app/api/plan/route.ts:25-30, src/lib/search.ts:50-65
1. Route Generation & Geometry
The initial step uses the Open Source Routing Machine (OSRM) to build a continuous route through all provided waypoints (Stops). The result is a GeoJSON-style polyline used for all subsequent geometric calculations.
- Endpoint:
https://router.project-osrm.org/route/v1/driving/ - Key Function:
planRoute(stops: Stop[]) - Data Structures:
PlannedRoutecontaining the polyline, distance in km, and duration in minutes.
Sources: src/lib/osrm.ts:16-52
2. Corridor Sampling and Retrieval
Because the Park4Night API limits the number of results per "around" query (approx. 100–200), the algorithm employs a sampling and grid technique to ensure full coverage along the route.
Adaptive Grid Sampling
The algorithm samples the OSRM polyline at regular intervals (stepKm). At each sample point, it generates an adaptive grid of query coordinates. This "5–9× trick" involves fanning out into cardinal rings to prevent dense regions from being truncated by API caps.
3. Filtering and Constraints
Once places are gathered, they are subjected to "Hard" and "Soft" filters.
Hard Filters
Places are excluded if they do not meet the following criteria:
- Category: Private and off-road places are excluded via
classifyPlace. - Rating: Must be equal to or higher than
specs.minRating. - Distance: Perpendicular distance (
kmFromRoad) must be withinsettings.maxKmFromRoad. - Look-Ahead: If a
ProgressWindowis active, the place must fall within the specific [fromKm, toKm] range of the trip.
Sources: src/lib/planner.ts:24-34, src/lib/planner.ts:70-75
4. Scoring and Ranking Heuristics
Places that pass hard filters are assigned a composite score. A lower score is better. The scoring system translates ratings and service matches into "km-equivalent" bonuses subtracted from the raw detour distance.
| Factor | Calculation / Weight |
|---|---|
| Base Cost | Raw kmFromRoad (perpendicular distance from route) |
| Rating Bonus | Up to -1.5 km for a 5-star rating |
| Service Bonus | -0.4 km for every user-requested service matched |
| Dog Park Bonus | Tapers from -1.2 km (at 0km distance) to 0 km |
Sources: src/lib/planner.ts:121-140
Ranking Logic Snippet
// Rank: lower score first.
// Ties break by progress along the route so the list reads in travel order.
results.sort((a, b) => a.score - b.score || a.progressKm - b.progressKm);
Sources: src/lib/planner.ts:109-111
5. Look-Ahead Windows
The algorithm supports "Day Planning" and "On the Road" modes through LookAhead windows. This allows the system to calculate a specific segment of the route to search within, rather than the entire polyline.
Summary of Key Data Structures
| Type | Description |
|---|---|
Stop | A waypoint with lat/lng and a label (A, B, C...). |
ScoredPlace | A P4N place enriched with kmFromRoad, progressKm, and score. |
ProgressWindow | A range defined by fromKm and toKm along the route polyline. |
CorridorSettings | User-defined constraints: maxKmFromRoad, dogParkMaxKm. |
Sources: src/lib/types.ts:80-165
The Core Route Planning Algorithm effectively combines spatial analysis with user-defined preferences to solve the "discoverability" problem in van-trip planning, ensuring that recommended stops are both high-quality and geographically convenient.