Travelling salesman (berlin52)
The problem
The travelling salesman problem asks for the shortest round trip that visits each of a set of locations once and returns to the start. TSPLIB (Reinelt, 1991) is a library of instances with known optimal tours. berlin52 is one of them: 52 locations in Berlin, given as points in the plane. Its optimal tour has length 7542.
The distance between two locations is TSPLIB's EUC_2D: the Euclidean distance, rounded to the nearest integer. Locations 1 and 2, at (565, 575) and (25, 185), are 666 apart.
What makes it hard
The problem is NP-hard (Garey and Johnson, 1979, Computers and Intractability). With symmetric distances, 52 locations give 51!/2 ≈ 7.8 × 10⁶⁵ different tours. A search that only accepts shorter tours stops at the first tour that no single move improves: a local optimum, not necessarily the optimal tour.
Representation
A Permutation of the 52 locations is the order of the visits; the tour returns from the last one
to the first. Every permutation is a valid tour, so no tour needs repairing. The fitness is the
tour's length, to minimize.
Algorithm
A local search that keeps one tour and tries one neighbor per step.
The neighbor is an inversion: a random segment of the tour is reversed. This is the 2-opt move: it removes two edges and reconnects the tour the other way. Flood (1956, Operations Research 4(1): 61-75) suggested the move, and Croes (1958, Operations Research 6(6): 791-812) made it a method. With symmetric distances, only those two edges change length. genoxide's guide recommends inversion for tours.
The acceptance is simulated annealing (Kirkpatrick, Gelatt and Vecchi, 1983, Science 220(4598): 671-680). A shorter or equal tour is always accepted. A tour longer by Δ is accepted with probability exp(−Δ / T), for a temperature T. T starts at 100 and is multiplied by 0.999995 after every step. At first, a tour 100 longer is accepted with probability 37%; the optimal tour's edges are 145 long on average. After 200,000 steps T is about 37, after 400,000 about 14, and after 1,000,000 about 0.7, when the search hardly goes uphill. Accepting worse tours early lets it leave local optima; cooling slowly gives it time to settle into a good region of tours before the temperature drops.
The search also restarts, as in iterated local search (Lourenço, Martin and Stützle, 2003, in the Handbook of Metaheuristics): after 100,000 steps without a shorter tour, it starts again from the best tour, changed by 3 random inversions.
The run stops at the optimum, or after 1,000,000 evaluations.
Output
The first line gives the length of the best tour found and the evaluations it took. The second gives that tour, from location 1, with the locations numbered from 1 as in TSPLIB. The tour returns from the last location to location 1.
The project page plays this run back, on a map of Berlin's districts. TSPLIB gives the locations no names and no real positions ("52 locations in Berlin (Groetschel)"), so their placement on the map is for orientation: every location inside Berlin, the dense cluster in the centre.
Good results
The optimum is 7542. The run of output.txt reaches it after 547,764 evaluations. Over seeds 1 to
100, 99 runs reached it: half within 342,000 evaluations and 91 within 430,000, while T was still
between about 12 and 30, and the other 8 within 804,000. The last seed ended at 7732. Without the
restarts, 95 of them reached it.
With a faster cooling, 0.99996 per step down to T ≈ 0.03 at 200,000 steps, and no restarts, half of seeds 1 to 30 reached the optimum; the others froze in tours 1.7% to 6% longer.
Known optimum: 7542 (tour length)
Source: examples/tsp_berlin52
Interactive run: tachsin.gr/projects/genoxide/examples/tsp-berlin52
cargo run --release --example tsp_berlin52
//! Travelling salesman: the shortest round trip through the 52 locations in Berlin of TSPLIB's
//! berlin52, whose optimal tour has length 7542.
//!
//! A permutation genome is the order of the visits. Local search with inversion neighbors (a
//! random 2-opt move: a reversed segment of the tour) and simulated annealing, which also accepts
//! worse tours, less and less often as the temperature cools, with restarts from the best tour
//! when the search stalls.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example tsp_berlin52
//! ```
mod trace;
use genoxide::prelude::*;
// the coordinates of the locations, from berlin52.tsp
const LOCATIONS: [(f64, f64); 52] = [
(565.0, 575.0),
(25.0, 185.0),
(345.0, 750.0),
(945.0, 685.0),
(845.0, 655.0),
(880.0, 660.0),
(25.0, 230.0),
(525.0, 1000.0),
(580.0, 1175.0),
(650.0, 1130.0),
(1605.0, 620.0),
(1220.0, 580.0),
(1465.0, 200.0),
(1530.0, 5.0),
(845.0, 680.0),
(725.0, 370.0),
(145.0, 665.0),
(415.0, 635.0),
(510.0, 875.0),
(560.0, 365.0),
(300.0, 465.0),
(520.0, 585.0),
(480.0, 415.0),
(835.0, 625.0),
(975.0, 580.0),
(1215.0, 245.0),
(1320.0, 315.0),
(1250.0, 400.0),
(660.0, 180.0),
(410.0, 250.0),
(420.0, 555.0),
(575.0, 665.0),
(1150.0, 1160.0),
(700.0, 580.0),
(685.0, 595.0),
(685.0, 610.0),
(770.0, 610.0),
(795.0, 645.0),
(720.0, 635.0),
(760.0, 650.0),
(475.0, 960.0),
(95.0, 260.0),
(875.0, 920.0),
(700.0, 500.0),
(555.0, 815.0),
(830.0, 485.0),
(1170.0, 65.0),
(830.0, 610.0),
(605.0, 625.0),
(595.0, 360.0),
(1340.0, 725.0),
(1740.0, 245.0),
];
const OPTIMUM: f64 = 7542.0;
// TSPLIB's EUC_2D distance: the Euclidean distance, rounded to the nearest integer
fn distance(a: (f64, f64), b: (f64, f64)) -> f64 {
let (dx, dy) = (a.0 - b.0, a.1 - b.1);
((dx * dx + dy * dy).sqrt() + 0.5).floor()
}
fn main() -> Result<()> {
let distances: Vec<Vec<f64>> = LOCATIONS
.iter()
.map(|&a| LOCATIONS.iter().map(|&b| distance(a, b)).collect())
.collect();
let tour_length = |order: &Order| {
(0..order.len())
.map(|i| distances[order[i]][order[(i + 1) % order.len()]])
.sum::<f64>()
};
let search = LocalSearch::builder(Permutation::new(LOCATIONS.len())?)
.neighbor(InversionMutation)
.acceptance(Acceptance::Annealing {
initial_temperature: 100.0,
cooling: 0.999_995,
})
// after 100,000 steps without a shorter tour, start again from the best one, changed by 3
// inversions
.restart(100_000, 3)
.minimize()
.seed(1)
.build()?;
// with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
let mut trace = trace::Trace::from_env();
let outcome = Engine::new(search, tour_length)
.stop_when(Stop::target(OPTIMUM).or(Stop::evaluations(1_000_000)))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
println!(
"tour length {} after {} evaluations (the optimum: {OPTIMUM})",
outcome.best_fitness(),
outcome.evaluations()
);
// the tour from location 1, numbered from 1 as in TSPLIB
let order = outcome.best_genome();
let start = order.iter().position(|&i| i == 0).unwrap_or(0);
let tour: Vec<usize> = order[start..]
.iter()
.chain(&order[..start])
.map(|location| location + 1)
.collect();
println!("tour {tour:?}");
trace.write();
Ok(())
}
python examples/tsp_berlin52/main.py
"""Travelling salesman: the shortest round trip through the 52 locations in Berlin of TSPLIB's
berlin52, whose optimal tour has length 7542.
A permutation genome is the order of the visits. Local search with inversion neighbors (a random
2-opt move: a reversed segment of the tour) and simulated annealing, which also accepts worse
tours, less and less often as the temperature cools, with restarts from the best tour when the
search stalls.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on the example's
page, with trace.py.
python examples/tsp_berlin52/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace
# the coordinates of the locations, from berlin52.tsp
LOCATIONS = np.array([
(565.0, 575.0), (25.0, 185.0), (345.0, 750.0), (945.0, 685.0),
(845.0, 655.0), (880.0, 660.0), (25.0, 230.0), (525.0, 1000.0),
(580.0, 1175.0), (650.0, 1130.0), (1605.0, 620.0), (1220.0, 580.0),
(1465.0, 200.0), (1530.0, 5.0), (845.0, 680.0), (725.0, 370.0),
(145.0, 665.0), (415.0, 635.0), (510.0, 875.0), (560.0, 365.0),
(300.0, 465.0), (520.0, 585.0), (480.0, 415.0), (835.0, 625.0),
(975.0, 580.0), (1215.0, 245.0), (1320.0, 315.0), (1250.0, 400.0),
(660.0, 180.0), (410.0, 250.0), (420.0, 555.0), (575.0, 665.0),
(1150.0, 1160.0), (700.0, 580.0), (685.0, 595.0), (685.0, 610.0),
(770.0, 610.0), (795.0, 645.0), (720.0, 635.0), (760.0, 650.0),
(475.0, 960.0), (95.0, 260.0), (875.0, 920.0), (700.0, 500.0),
(555.0, 815.0), (830.0, 485.0), (1170.0, 65.0), (830.0, 610.0),
(605.0, 625.0), (595.0, 360.0), (1340.0, 725.0), (1740.0, 245.0),
])
OPTIMUM = 7542
# TSPLIB's EUC_2D distance: the Euclidean distance, rounded to the nearest integer
dx = LOCATIONS[:, None, 0] - LOCATIONS[None, :, 0]
dy = LOCATIONS[:, None, 1] - LOCATIONS[None, :, 1]
DISTANCES = np.floor(np.sqrt(dx * dx + dy * dy) + 0.5)
def tour_length(order):
return float(DISTANCES[order, np.roll(order, -1)].sum())
search = gx.LocalSearch(
gx.Permutation(len(LOCATIONS)),
neighbor=gx.InversionMutation(),
acceptance=gx.Annealing(initial_temperature=100.0, cooling=0.999_995),
# after 100,000 steps without a shorter tour, start again from the best one, changed by 3
# inversions
restart=(100_000, 3),
objective="minimize",
seed=1,
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(LOCATIONS, OPTIMUM)
result = search.run(
tour_length, target=OPTIMUM, evaluations=1_000_000, on_generation=trace.on_generation
)
print(
f"tour length {result.best_fitness:.0f} after {result.evaluations} evaluations "
f"(the optimum: {OPTIMUM})"
)
# the tour from location 1, numbered from 1 as in TSPLIB
order = result.best_genome
tour = np.roll(order, -np.flatnonzero(order == 0)[0]) + 1
print(f"tour {tour.tolist()}")
trace.write()
What it prints, from a seeded run:
tour length 7542 after 547764 evaluations (the optimum: 7542)
tour [1, 49, 32, 45, 19, 41, 8, 9, 10, 43, 33, 51, 11, 52, 14, 13, 47, 26, 27, 28, 12, 25, 4, 6, 15, 5, 24, 48, 38, 37, 40, 39, 36, 35, 34, 44, 46, 16, 29, 50, 20, 23, 30, 2, 7, 42, 21, 17, 3, 18, 31, 22]