PSDP Algorithm
PSDP is a geometric initialization and routing framework for Euclidean TSP-style problems, designed as a middle path between classical heuristics and heavy deep-learning approaches. It reformulates tour construction as a wave-like sweep over angular sectors, then couples this with local search to achieve strong gaps while keeping latency low enough for real-time or on-device use. The work is driven by benchmarked evidence, complexity-aware engineering, and a focus on instance-level behavior rather than headline averages.
A research-grade construction heuristic for Euclidean TSP that trades a small optimality gap for predictable, low-latency performance on real-world instances.
Role
Research lead · Algorithm design · Implementation
Stack
- Python
- C++
- NumPy
- Matplotlib
- TSPLIB benchmarks
Highlights
- —Designed a sector-based geometric initialization that “uncrosses” tours before local search
- —Achieved competitive optimality gaps against classic greedy baselines on multiple TSPLIB instances
- —Characterized instances where PSDP outperforms greedy heuristics, highlighting geometry-dependent behavior
- —Implemented a full benchmarking pipeline with reproducible runs, plots, and complexity analysis