Euclidean TSP · LPQI
Layered Priority-Queue Insertion
A geometric-topological heuristic for the Euclidean Traveling Salesman Problem. LPQI layers convex hulls and uses lazy priority queues to insert interior points quickly, yielding strong starter tours for local search (2-opt/3-opt/LK-light).
View Repository
Read the paper
Key idea
Convex layers + lazy PQ
Start on the hull, insert interior points via distance-to-segment priority queue with lazy revalidation.
Local search
2-opt · 3-opt · LK-light
Clean starter tours feed lightweight refinements for fast, high-quality results.
Dataset
TSPLIB (Tnm52–Tnm199)
Concorde optima provided for 48 planar instances with recorded runtimes.
Algorithm snapshot
Compute convex hull; initialize tour with hull vertices.
Maintain priority queue keyed by point-to-edge insertion cost; lazily refresh on pop.
Insert at cheapest edge; repeat until all interior points are placed.
Polish with 2-opt, safe 3-opt (n ≤ 150), and a short LK-style edge-flip sampler.
What to look for
Subquadratic practical behavior on Euclidean inputs.
Competitive initial tours versus classic insertions; strong feedstock for local search.
Minimal hyperparameters; deterministic runs except for LK-light sampling.
Benchmark rollup
Instance-by-instance view
Uses results_stable/bench.csv merged with Concorde optima.
#
Instance
n
Optimum
Best LPQI family length
% over optimum
Best variant
Init time (s)
LK-light (s)
Concorde runtime (s)
Integrality gap
Data sources
TSPLIB95 Concorde solutions and coordinates (see /TSPLIB95/CONCORODE_solved_instances).
Recorded algorithm runs: results_stable/bench.csv (LPQI, MHLPQI, HullRot).
Full timing and multi-stage outputs: results/concorde_full_bench.csv.
Notes
Concorde integrality gaps and runtimes are shown for context; LPQI results are purely constructive with light post-processing.
3-opt is applied only when n ≤ 150 to stay lean on larger instances.
Percent over optimum is computed from the best LPQI-family length vs the provided Concorde optimum.