{
const params = `
PROBLEM_FILE = /abstract-light-painting.tsp
OUTPUT_TOUR_FILE = /abstract-light-painting.tour
RUNS = 5
`;
const filename_tsp = "/abstract-light-painting.tsp";
const contents_tsp = await FileAttachment(
"abstract-light-painting.tsp"
).text();
const filename_output = "/abstract-light-painting.tour";
return await runLKH(params, filename_tsp, contents_tsp, filename_output);
}
/**
* Solves a TSP problem given a distance matrix
* @param {number[][]} distances - Upper triangular distance matrix
* @param {Object} options - Optional solver parameters
* @param {number} [options.runs=5] - Number of LKH runs
* @returns {Promise<number[]>} Array of indices representing the tour
*/
async function solveTSP(distances, options = {}) {
const { runs = 5 } = options;
// Generate TSPLIB format problem file
const problemFile = generateTSPLIB(distances);
// Create LKH parameter file
const paramFile = [
"PROBLEM_FILE = /input.tsp",
"OUTPUT_TOUR_FILE = /output.tour",
`RUNS = ${runs}`
].join("\n");
// Run LKH solver
const tourFile = await runLKH(
paramFile,
"/input.tsp",
problemFile,
"/output.tour"
);
// Parse tour file
const tour = parseTour(tourFile);
return tour;
}
function generateTSPLIB(distances) {
// For a triangular matrix of n-1 rows, number of cities is n
// First row has n-1 elements, second has n-2, etc.
const dimension = distances[0].length + 1; // Derive n from first row length
const lines = [
"NAME : generated_problem",
"TYPE : TSP",
`DIMENSION : ${dimension}`,
"EDGE_WEIGHT_TYPE : EXPLICIT",
"EDGE_WEIGHT_FORMAT : UPPER_ROW",
"NODE_COORD_TYPE : NO_COORDS",
"DISPLAY_DATA_TYPE : NO_DISPLAY",
"",
"EDGE_WEIGHT_SECTION :"
];
// Add each row of the triangular matrix
for (let i = 0; i < distances.length; i++) {
const row = distances[i].map((d) => Math.round(d)).join(" ");
if (row.length > 0) {
lines.push(row);
}
}
console.log("Generated TSPLIB file:");
console.log(lines.join("\n"));
return lines.join("\n");
}
function parseTour(tourFile) {
console.log("Parsing tour file:", tourFile);
const tour = [];
let inTourSection = false;
for (const line of tourFile.split("\n")) {
const trimmed = line.trim();
if (trimmed === "TOUR_SECTION") {
inTourSection = true;
continue;
}
if (inTourSection) {
const node = parseInt(trimmed);
if (node === -1) {
break;
}
// Convert from 1-based to 0-based indexing
tour.push(node - 1); // Changed from node - 2
}
}
console.log("Parsed tour before rotation:", tour);
// Rotate tour to start from first city
const minIndex = tour.indexOf(Math.min(...tour));
return [...tour.slice(minIndex), ...tour.slice(0, minIndex)];
}
{
const distances = [[100, 200, 300], [150, 250], [400]];
try {
const tour = await solveTSP(distances, { runs: 10 });
return tour;
} catch (error) {
return error;
}
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
