How the Route Optimization Algorithm Works in the TREK Trip Planner

The TREK trip planner optimizes routes using a nearest-neighbor heuristic followed by a 2-opt improvement pass, minimizing Euclidean travel distance while respecting fixed start and end anchors.

The route optimization algorithm in the TREK trip planner lives inside client/src/components/Map/RouteCalculator.ts and powers the automatic reordering of waypoints to minimize travel time. This lightweight solver requires no external dependencies, making it ideal for client-side execution within the open-source TREK repository.

Step-by-Step Optimization Pipeline

The exported optimizeRoute function processes waypoint arrays through a six-stage pipeline that balances computational efficiency with route quality.

Input Validation and Early Exit

First, the algorithm filters out invalid waypoints lacking latitude or longitude coordinates using places.filter (line 77). If the resulting set contains zero or one valid points, or exactly two points without any anchors, the function returns the input unchanged immediately (lines 80-83), avoiding unnecessary computation on trivial cases.

Nearest-Neighbor Initialization

The nearestNeighborOrder helper (lines 119-145) generates an initial seed order by starting from the start anchor (if provided) and repeatedly selecting the closest unvisited waypoint based on squared Euclidean distance. This greedy approach produces a reasonably good initial tour in O(n²) time.

2-Opt Local Search Refinement

The twoOptImprove function (lines 147-170) iteratively improves this seed by reversing sub-segments whenever such a reversal reduces the total tourLength. This local search optimization continues until no improving swaps remain, effectively untangling crossing routes while keeping start and end anchors fixed.

Round-Trip Orientation

When the start and end anchors are identical (indicating a round-trip day starting and ending at the same hotel), the algorithm reorients the loop so the waypoint nearest to the hotel appears first (lines 186-190). This ensures the visual route reads logically as "leave hotel → nearest place → ... → return".

Distance Calculation Helpers

Fast Euclidean Distance

The sqDist(a, b) function (lines 103-106) computes squared Euclidean distance between two coordinates, used for fast distance comparisons without expensive square root operations.

Total Tour Length

The tourLength(order, start?, end?) function (lines 108-116) calculates the complete path distance, optionally including segments from the start anchor to the first waypoint and from the last waypoint to the end anchor.

Implementation Examples

import { optimizeRoute } from '@/components/Map/RouteCalculator'

// Simple day without anchors
const places = [
  { lat: 48.8566, lng: 2.3522 }, // Eiffel Tower
  { lat: 48.8600, lng: 2.3400 }, // Louvre
  { lat: 48.8625, lng: 2.3320 }, // Musée d'Orsay
]

const ordered = optimizeRoute(places)
console.log('Optimized order:', ordered)

// Round-trip with hotel as both start and end
const hotel = { lat: 48.8668, lng: 2.3013 }
const dayPlaces = [
  { id: 1, lat: 48.8565, lng: 2.3324 },
  { id: 2, lat: 48.8813, lng: 2.3151 },
  { id: 3, lat: 48.8796, lng: 2.3080 },
  { id: 4, lat: 48.8723, lng: 2.2926 },
  { id: 5, lat: 48.8660, lng: 2.3102 }, // nearest the hotel
]

const roundTrip = optimizeRoute(dayPlaces, { start: hotel, end: hotel })
console.log('Round-trip order (ids):', roundTrip.map(p => p.id))

// Transfer day with different start and end hotels
const startHotel = { lat: 48.8500, lng: 2.3000 }
const endHotel   = { lat: 48.9000, lng: 2.3500 }

const transfer = optimizeRoute(dayPlaces, { start: startHotel, end: endHotel })
console.log('Transfer day order (ids):', transfer.map(p => p.id))

Summary

• The TREK route optimizer implements a hybrid approach combining nearest-neighbor construction with 2-opt improvement.
• All calculations use squared Euclidean distance via sqDist for performance, with final tour length computed by tourLength.
• The algorithm handles three distinct scenarios: open-ended days, round-trips (start equals end), and transfer days (different start/end).
• The implementation remains entirely client-side in client/src/components/Map/RouteCalculator.ts with zero external solver dependencies.

Frequently Asked Questions

What algorithm does TREK use for route optimization?

The TREK trip planner uses a nearest-neighbor heuristic followed by a 2-opt local search improvement. This combination provides near-optimal solutions for the traveling salesman problem variant while remaining computationally lightweight enough to run in the browser.

Does TREK require external APIs for route optimization?

No. According to the TREK source code, the entire optimization logic resides in client/src/components/Map/RouteCalculator.ts and uses only Euclidean distance calculations. No external solvers or mapping APIs are required for the reordering algorithm itself, though OSRM routing may be used for actual path display.

How does TREK handle round-trip itineraries?

When the start and end anchors are identical (same hotel), the algorithm detects this condition and ensures the waypoint closest to the hotel appears first in the sequence. This orientation creates a logical loop where the traveler visits the nearest attraction first before proceeding to farther destinations.

What is the time complexity of the TREK optimizer?

The nearest-neighbor phase runs in O(n²) time where n is the number of waypoints, while the 2-opt improvement typically runs in O(n²) per iteration until convergence. The algorithm includes early exit conditions for trivial cases (0-2 points) to maximize performance.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}