RutaFácil

// Heurística de Vecino Más Cercano + Mejora 2-Opt (Cálculo On-Device $0)
export function optimizeOrder(
  origin: LatLng,
  stops: LatLng[],
  fixedEnd?: LatLng,
): number[] {
  const n = stops.length;
  if (n <= 1) return stops.map((_, i) => i);

  const points = fixedEnd ? [origin, ...stops, fixedEnd] : [origin, ...stops];
  const dist: number[][] = points.map((a) =>
    points.map((b) => haversineKm(a, b)),
  );
  const endIdx = fixedEnd ? n + 1 : null;

  // 1. Vecino más cercano desde el origen
  const visited = new Array<boolean>(n + 1).fill(false);
  visited[0] = true;
  const path: number[] = [0];
  let current = 0;
  for (let step = 0; step < n; step++) {
    let best = -1;
    let bestDist = Infinity;
    for (let j = 1; j <= n; j++) {
      if (!visited[j] && dist[current][j] < bestDist) {
        bestDist = dist[current][j];
        best = j;
      }
    }
    visited[best] = true;
    path.push(best);
    current = best;
  }
  if (endIdx !== null) path.push(endIdx);

  // 2. Optimización 2-opt: invierte segmentos mientras acorte el camino
  let improved = true;
  while (improved) {
    improved = false;
    for (let i = 1; i < n; i++) {
      for (let k = i + 1; k <= n; k++) {
        const a = path[i - 1];
        const b = path[i];
        const c = path[k];
        const d = k + 1 <= n ? path[k + 1] : endIdx;
        const before = dist[a][b] + (d !== null ? dist[c][d] : 0);
        const after = dist[a][c] + (d !== null ? dist[b][d] : 0);
        if (after < before - 1e-9) {
          let lo = i;
          let hi = k;
          while (lo < hi) {
            [path[lo], path[hi]] = [path[hi], path[lo]];
            lo++;
            hi--;
          }
          improved = true;
        }
      }
    }
  }

  return path.slice(1, n + 1).map((p) => p - 1);
}