Route Optimisation for Sri Lankan Roads

Haversine distance × a road factor, a nearest-neighbour seed and 2-opt improvement — the real optimiser behind Nora Labs itineraries.

17 Oct 20264 min read#Algorithms#Python#Tourism

Lesson 7 of 10 · Tourism Tech · built from Nora Travels, Nora Labs, Mahesh Travellers and my hospitality sites

A tour that zig-zags between Kandy and Galle twice wastes a day. Nora Labs orders stops with a small, explainable optimiser and reports what it saved.

Example — distance that matches the road

ExamplePython

EARTH_RADIUS_KM = 6371.0
# Sri Lankan roads are winding; straight-line km under-states real driving distance.
ROAD_FACTOR = 1.35
AVG_SPEED_KMH = 42.0

def haversine_km(lat1, lon1, lat2, lon2):
    p1, p2 = math.radians(lat1), math.radians(lat2)
    dp, dl = math.radians(lat2 - lat1), math.radians(lon2 - lon1)
    a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
    return 2 * EARTH_RADIUS_KM * math.asin(math.sqrt(a))

def road_km(a, b):
    return round(haversine_km(a["lat"], a["lon"], b["lat"], b["lon"]) * ROAD_FACTOR, 1)

def travel_minutes(a, b):
    return int(round(road_km(a, b) / AVG_SPEED_KMH * 60))

Example — nearest-neighbour seed, then 2-opt

ExamplePython

def optimize_route(stops, fixed_start=True):
    """Nearest-neighbour seed followed by 2-opt improvement (open path, not a loop)."""
    original = _tour_length(stops)
    remaining = stops[1:] if fixed_start else list(stops)
    route = [stops[0]] if fixed_start else [remaining.pop(0)]
    while remaining:
        nxt = min(remaining, key=lambda s: road_km(route[-1], s))
        remaining.remove(nxt)
        route.append(nxt)

    improved = True
    while improved:
        improved = False
        for i in range(1, len(route) - 1):
            for j in range(i + 1, len(route)):
                candidate = route[:i] + route[i:j + 1][::-1] + route[j + 1:]
                if _tour_length(candidate) + 1e-9 < _tour_length(route):
                    route, improved = candidate, True
    total = _tour_length(route)
    return {"order": route, "total_km": round(total, 1), "improved_km": round(original - total, 1)}

Domain rules on top of the maths

National parks are never overnight stops. They carry no nightly rate and attach to the nearest lodging town as day trips — Minneriya from Habarana, Wilpattu from Kalpitiya.
Show the saving. The API returns optimizer_saved_km, so a traveller sees why the order changed.

Try it yourself: read how this powers the Nora Labs wizard — the route step uses exactly this function.