TSP Route Optimization

Instructions

Build route optimization features that reorder stops to minimize travel time or distance, supporting both API-backed and algorithmic approaches.

Mapbox Optimization API

• Use the Optimization v2 API endpoint: POST https://api.mapbox.com/optimized-trips/v2
• Submit waypoints as GeoJSON with optimize: true to get the optimal visit order
• Respect API constraints: maximum 25 waypoints per request for the standard tier
• For itineraries exceeding 25 stops, partition into clusters first, optimize each cluster, then sequence the clusters
• Handle the roundtrip parameter: set false for one-way routes (different start/end), true for return-to-origin
• Parse the response waypoint_index array to map optimized order back to the original stop list
• Cache optimization results keyed by the set of waypoint coordinates (order-independent hash) with a 24-hour TTL

Algorithmic Fallback

When the API is unavailable or the use case requires offline operation:

• Nearest Neighbor heuristic: O(n²) greedy approach — start from the first stop, always visit the nearest unvisited stop. Fast but produces solutions 20-25% longer than optimal
• 2-opt improvement: After generating an initial tour (nearest neighbor), iteratively swap pairs of edges if the swap reduces total distance. Repeat until no improving swap exists
• Or-tools (Google): For Rust/Python projects, use the OR-Tools routing library for vehicle routing problems with time windows, capacity constraints, and precedence rules
• Use Haversine distance for straight-line estimates; prefer Mapbox Directions API distances for road-network accuracy

Multi-Day Itinerary Optimization

• Partition stops into daily groups based on: geographic clustering (k-means on lat/lng), daily time budget, and opening hours
• Within each day, run TSP optimization on that day’s stops
• Cross-day optimization: if a stop near today’s cluster has better availability tomorrow, swap it — minimize total multi-day travel
• Respect hard constraints: fixed-time reservations, venue closing hours, travel time buffers

Waypoint Data Model

Each waypoint should carry:

• id: unique stop identifier
• coordinates: [longitude, latitude] (GeoJSON order)
• time_window: optional { open, close } in ISO 8601
• duration_minutes: expected time spent at the stop
• priority: required | preferred | optional — required stops are never dropped
• day_assignment: optional pre-assigned day for multi-day trips

Distance Matrix

• Build an n×n distance/duration matrix before optimization
• For road networks, batch requests to Mapbox Matrix API (max 25 sources × 25 destinations)
• For larger matrices, tile the requests and assemble
• Cache matrix entries — coordinates rarely change within a trip planning session
• Fall back to Haversine when matrix API is rate-limited

Performance Targets

Inputs Required

• Array of waypoints with coordinates, time windows, and durations
• Trip configuration: single-day vs. multi-day, roundtrip vs. one-way
• Optimization objective: minimize distance, minimize time, or balance both
• API credentials: Mapbox access token (if using API approach)
• Constraints: fixed start/end locations, required visit order for specific stops

Output Format

• Ordered array of waypoint IDs representing the optimized visit sequence
• Per-leg travel time and distance estimates
• Total route duration and distance
• For multi-day: array of daily route objects, each containing the day’s ordered stops
• Optimization metadata: method used, improvement percentage over original order, computation time

Anti-Patterns

• Optimizing presentation order, not route order: The display list order is not the travel order — always separate data model ordering from route ordering
• Ignoring time windows: Reordering stops without respecting opening hours produces invalid itineraries
• Single massive API call: Exceeding the 25-waypoint limit causes silent truncation or errors — always partition first
• Haversine for driving routes: Straight-line distance drastically underestimates urban driving time — use road-network distances for anything user-facing
• Re-optimizing on every minor edit: Cache results and only re-run optimization when stops are added, removed, or moved significantly (>500m)
• Dropping the return leg: For roundtrip itineraries, forgetting to include the return-to-start leg underestimates total travel time