Solve TSP with 2-opt and multiple random seeds

README.md

Results

First, I tested on berlin52. The program occasionally finds the optimal solution, usually taking a few hundred iterations.

Next, I tested a 127-city problem, bier127.tsp. I started with 1,000 initial random routes.

The optimal solution is known to be of length 118282, but the optimal solution found by the program is 121950. This is ~3% above optimal.

I then cranked up the number of initial routes to 10,000. After around a minute, the program found a solution of length 120109. This is still ~1.5% above optimal.

On a harder problem like d2103 with 2,103 points, this approach fails even harder. First, I noticed that the time-per-iteration is quite slow for this problem. I could optimize the program, but didn't bother. In order to make the program run in ~1 minute, I tried 20 hill-climbing steps with only one random initial seed. The optimal solution is of length 80450. The solution found by the program is of length 96363, about ~19% above optimal.

main.rs

use rand::prelude::*;
use std::error::Error;
use std::fs::File;
use std::io::{BufRead, BufReader};
use std::path::Path;
use std::{env, cmp};

#[derive(Clone, Copy, Debug)]
struct City {
    x: f64,
    y: f64,
}

// Represents a TSP solution
#[derive(Clone)]
struct TSPSolution {
    route: Vec<usize>,
    length: i64,
}

// --- TSPLIB parsing --------------------------------------------------------

fn parse_tsplib<P: AsRef<Path>>(path: P) -> Result<Vec<City>, Box<dyn Error>> {
    let file = File::open(path)?;
    let reader = BufReader::new(file);

    let mut in_coords = false;
    let mut cities = Vec::new();

    for line in reader.lines() {
        let line = line?;
        let trimmed = line.trim();

        if trimmed.eq_ignore_ascii_case("NODE_COORD_SECTION") {
            in_coords = true;
            continue;
        }

        if trimmed.eq_ignore_ascii_case("EOF") {
            break;
        }

        if in_coords {
            // Typical line: "<index> <x> <y>"
            // Robustly split on whitespace
            let parts: Vec<&str> = trimmed.split_whitespace().collect();
            if parts.len() < 3 {
                continue;
            }
            // parts[0] is the 1-based index; ignore it
            let x: f64 = parts[1].parse()?;
            let y: f64 = parts[2].parse()?;
            cities.push(City { x, y });
        }
    }

    if cities.is_empty() {
        return Err("No coordinates found (did you pass a EUC_2D TSPLIB file?)".into());
    }

    Ok(cities)
}

// --- Distance helpers (TSPLIB EUC_2D rounded) -----------------------------

#[inline]
fn euc2d_rounded(a: &City, b: &City) -> i64 {
    let dx = a.x - b.x;
    let dy = a.y - b.y;
    ((dx * dx + dy * dy).sqrt()).round() as i64
}

fn route_length(cities: &[City], route: &[usize]) -> i64 {
    let mut total: i64 = 0;
    for i in 0..route.len() - 1 {
        total += euc2d_rounded(&cities[route[i]], &cities[route[i + 1]]);
    }
    // return to start
    total += euc2d_rounded(&cities[*route.last().unwrap()], &cities[route[0]]);
    total
}

// Perform a 2-opt swap (reverse segment [i..j])
fn two_opt_swap(route: &[usize], i: usize, j: usize) -> Vec<usize> {
    let mut new_route = route.to_vec();
    new_route[i..=j].reverse();
    new_route
}

// Hill climbing with 2-opt
fn hill_climbing(cities: &[City], max_iterations: usize, rng: &mut impl Rng) -> TSPSolution {
    let n = cities.len();

    // random initial route
    let mut current_route: Vec<usize> = (0..n).collect();
    current_route.shuffle(rng);
    let mut current_length = route_length(cities, &current_route);

    let mut best_route = current_route.clone();
    let mut best_length = current_length;

    for _ in 0..max_iterations {
        let mut improved = false;

        // full 2-opt neighborhood
        for i in 1..n - 1 {
            for j in (i + 1)..n {
                let candidate_route = two_opt_swap(&current_route, i, j);
                let candidate_length = route_length(cities, &candidate_route);
                if candidate_length < current_length {
                    current_route = candidate_route;
                    current_length = candidate_length;

                    if current_length < best_length {
                        best_route = current_route.clone();
                        best_length = current_length;
                    }
                    improved = true;
                }
            }
        }

        if !improved {
            break;
        }
    }

    TSPSolution {
        route: best_route,
        length: best_length,
    }
}

fn main() -> Result<(), Box<dyn Error>> {
    let args: Vec<String> = env::args().collect();

    if args.len() < 2 {
        eprintln!(
            "Usage: {} <tsplib_file> [max_iterations] [random_restarts]",
            args[0]
        );
        std::process::exit(1);
    }

    let file_path = &args[1];
    let max_iterations: usize = args.get(2).and_then(|s| s.parse().ok()).unwrap_or(1000);
    let random_restarts: usize = args.get(3).and_then(|s| s.parse().ok()).unwrap_or(1);

    let cities = parse_tsplib(file_path)?;
    let mut rng = rand::thread_rng();

    let mut global_best: Option<TSPSolution> = None;

    for _ in 0..random_restarts {
        let sol = hill_climbing(&cities, max_iterations, &mut rng);
        match &global_best {
            None => global_best = Some(sol),
            Some(best) => {
                if sol.length < best.length {
                    global_best = Some(sol);
                }
            }
        }
    }

    let best = global_best.unwrap();
    println!("Best tour length found (EUC_2D, rounded per-edge): {}", best.length);
    println!("Route (0-based indices): {:?}", best.route);

    Ok(())
}