🌏 Haversine-TSP

Efficient and Scalable TSP Solver for Real-World Geographic Points using the Haversine Formula

---

✨ Features

• 🗺️ TSP (Traveling Salesman Problem) solver for latitude-longitude locations
• ⚡ Nearest Neighbor heuristic forsSupports thousands of points
• 📐 Haversine formula for accurate Earth distance
• 📦 JSON import/export for locations & routes
• 🏙️ Built-in random city location generator for realistic simulations and demos

---

⚙️ How It Works

1. Location Generation (tsp-generator.js)

   • Instantly generates 100 random points for each of Jakarta, Yogyakarta, and Surabaya
   • Each point is labeled (Jakarta 1, ..., Surabaya 100), with a special center (Jakarta Central)
   • Output: cities-locations.json

2. Distance Calculation

   • All routing uses the accurate Haversine formula (see code), considering Earth curvature for precise km/m calculations

3. TSP Route Solving (tsp-solver.js)

   • Reads your city/location JSON
   • Applies the Nearest Neighbor heuristic to quickly compute a "good" round-trip route (start and end at same city)
   • Output: Ordered route and total distance in tsp-result.json

---

🧠 Algorithm Overview

• Haversine: Measures true shortest path between two points on a sphere (the Earth)
• Nearest Neighbor TSP:
  • Start at any city
  • At each step, travel to the nearest unvisited city
  • Repeat until all cities are visited, then return to the starting point
  • Scales to thousands of points (brute force only works for ≤ 8)

---

🚀 Quick Start

1. Clone & Install

git clone https://github.com/NeaByteLab/Haversine-TSP.git
cd Haversine-TSP
npm install

2. Generate Random City Locations

node tsp-generator.js

Output: cities-locations.json 🗃️

3. Solve TSP Route

node tsp-solver.js

Output: tsp-result.json 🏁

---

📄 Example JSON

[
  { "label": "Jakarta Central", "lat": -6.2, "lon": 106.8167 },
  { "label": "Jakarta 1", "lat": -6.21, "lon": 106.81 },
  ...,
  { "label": "Surabaya 100", "lat": -7.30, "lon": 112.77 }
]

🏁 Sample Output

{
  "route": [
    { "label": "Jakarta Central", "lat": -6.2, "lon": 106.8167 },
    ...
  ],
  "totalDistance": 3145.53
}

---

🔍 Use Cases

• 🚚 Logistics & delivery route optimization
• 🏞️ Tour, field work, and multi-city planning
• 🧪 Geographic research, simulations, and demos
• 📈 Route benchmarking and performance testing

⚠️ Limitations & Tips

• The Nearest Neighbor heuristic is extremely fast and often very good, but not mathematically optimal
• For datasets with ≤8 points, a brute-force method can guarantee the shortest possible route
• For large datasets (100+), use this heuristic or add post-processing (2-Opt, etc) for better results

---

📜 License

MIT License © 2025 NeaByteLab