# How the Route Optimization Algorithm Works in the TREK Trip Planner

> Discover how the TREK trip planner's route optimization algorithm uses nearest-neighbor and 2-opt to minimize travel distance while respecting fixed start and end points.

- Repository: [Maurice/TREK](https://github.com/mauriceboe/TREK)
- Tags: deep-dive
- Published: 2026-07-04

---

**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`](https://github.com/mauriceboe/TREK/blob/main/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

```typescript
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)

```

```typescript
// 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))

```

```typescript
// 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`](https://github.com/mauriceboe/TREK/blob/main/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`](https://github.com/mauriceboe/TREK/blob/main/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.