A personal learning repository exploring the Travelling Salesman Problem (TSP) — one of the most classic combinatorial optimization problems in computer science and operations research.
This repository is built as a learning project to understand, implement, and compare various algorithmic approaches to solving the Travelling Salesman Problem (TSP).
TSP is a well-known NP-hard problem that asks: given a list of locations and the distances between them, what is the shortest possible route that visits each location exactly once and returns to the origin? Despite its simple formulation, TSP is computationally challenging at scale and serves as a benchmark for many optimization techniques.
The problem in this project is contextualized around real-world route optimization — specifically modeling how a vehicle or agent can efficiently traverse a set of geographic points, minimizing total travel distance or cost. This has direct applications in logistics, delivery systems, urban planning, and waste management routing.
The Travelling Salesman Problem has been studied for over a century and remains one of the most well-researched problems in combinatorial optimization. Its importance spans multiple domains:
- Logistics and supply chain: Optimizing delivery routes reduces operational costs and fuel consumption.
- Network design: TSP formulations appear in circuit board drilling, DNA sequencing, and data center routing.
- Operations research: TSP is a standard testbed for benchmarking exact, heuristic, and metaheuristic algorithms.
- Machine learning: Recent work has explored neural approaches (Pointer Networks, Graph Neural Networks) to approximate TSP solutions.
Understanding TSP and its solution strategies provides a strong foundation for tackling broader combinatorial optimization problems.
TPS-Optimization-Route/
│
├── Comparison TSP v3.ipynb # Main notebook: algorithm implementation & comparison
├── interactive_map_comparison.html # Interactive map visualization of route outputs
└── README.md
The notebook (Comparison TSP v3.ipynb) implements and compares multiple approaches to solving TSP. Each algorithm represents a different paradigm in optimization:
A simple constructive heuristic that starts at a node and repeatedly visits the closest unvisited node. It is fast and easy to implement, but often yields suboptimal solutions. Used here as a baseline for comparison.
- Time complexity: O(n^2)
- Pros: Simple, fast
- Cons: Greedy choices lead to poor long-term decisions
An evolutionary metaheuristic inspired by natural selection. A population of candidate routes evolves over generations through selection, crossover, and mutation operators. GA explores the solution space broadly and is capable of escaping local optima.
- Pros: Good global exploration, flexible
- Cons: Requires careful tuning of hyperparameters (population size, mutation rate, generations)
A probabilistic local search algorithm inspired by the annealing process in metallurgy. SA accepts worse solutions with a probability that decreases over time (controlled by a "temperature" parameter), allowing it to escape local optima early in the search.
- Pros: Strong local search, theoretically converges to global optimum
- Cons: Sensitive to cooling schedule; slow convergence if not tuned properly
Additional methods and variations may be explored within the notebook, including route improvement techniques such as 2-opt and 3-opt local search, which iteratively swap edges to improve an existing tour.
Each algorithm is evaluated across the following dimensions:
| Metric | Description |
|---|---|
| Total Route Distance | Sum of distances across the complete tour |
| Convergence Behavior | How solution quality improves over iterations |
| Computation Time | Wall-clock time to reach final solution |
| Route Visualization | Spatial comparison of paths on an interactive map |
Results are visualized both numerically (in the notebook) and spatially (in the HTML map), enabling a holistic comparison of algorithm performance.
The interactive_map_comparison.html file provides an interactive map built with Folium that overlays the routes generated by each algorithm on a geographic map. This allows direct visual inspection of how different approaches traverse the same set of nodes.
To use it, simply open the .html file in any modern web browser — no additional dependencies required.
Ensure you have Python 3.8+ installed along with the following libraries:
pip install numpy pandas matplotlib folium-
Clone this repository:
git clone https://github.com/abyansyah052/TPS-Optimization-Route.git cd TPS-Optimization-Route -
Launch Jupyter Notebook:
jupyter notebook "Comparison TSP v3.ipynb"Alternatively, upload the
.ipynbfile directly to Google Colab for a cloud-based environment without local setup. -
Run all cells sequentially to reproduce the algorithm comparisons and generate the interactive map output.
For those new to TSP or the algorithms used here, the following concepts are foundational:
- Combinatorial Optimization: Optimization over discrete solution spaces, where exact methods become infeasible at large scales.
- NP-Hard Problems: Problems for which no polynomial-time exact algorithm is known; TSP is a canonical example.
- Heuristics vs. Metaheuristics: Heuristics provide good-enough solutions quickly; metaheuristics (GA, SA) add mechanisms to avoid local optima.
- Greedy Algorithms: Make locally optimal choices at each step; useful as baselines but rarely globally optimal.
- Local Search: Iteratively improve a solution by making small modifications (e.g., 2-opt swaps).
Relevant literature:
- Applegate, D. et al. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
- Kirkpatrick, S. et al. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671–680.
- Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
This project was developed as part of a personal learning journey in combinatorial optimization and algorithm design.
The core logic, problem framing, algorithm selection, parameter tuning decisions, and analytical thinking behind this project were developed independently. The learning process started from first principles — understanding the problem mathematically, studying algorithm behaviors, and reasoning through trade-offs before writing any code.
AI assistance (specifically generative AI tools) was used selectively in certain parts of the implementation to help generate boilerplate, generic utility functions, and visualization scaffolding. The AI did not define the approach or the analytical direction — it was used as a productivity tool after the logic was already established.
The logic came first. AI only helped write parts of it faster.
Abyansyah Dewanto Undergraduate Student — Information Systems GitHub: @abyansyah052
This repository is for educational purposes. Feel free to explore, fork, and learn from it.