The Traveling Salesman Problem (TSP) is a classical problem in combinatorial optimization and graph theory.
It can be stated as follows:
“A person must visit a given number of cities (n), exactly once each, and return to the starting city.
The goal is to find the optimal route (the one with the minimum total cost) that satisfies these conditions.”
To make the problem more interesting and realistic, I introduced additional constraints that influence how the salesman can choose the next destination at each step:
-
Roads with Speed Limits
Each road between two cities is defined not only by its distance but also by a speed limit (in km/h).
This affects the time required for the salesman to travel between cities. -
City Accessibility Intervals
Each city can only be visited within a specific time window.
Outside this interval, traveling to that city is not possible.
As a result, the algorithm must consider both distance and timing when deciding the next move.
Assumptions:
To simplify and optimize the problem-solving process, we assume that the traveler’s speed on each road is equal to the speed limit associated with that road.
The problem is solved using three classical algorithmic approaches:
- Branch & Bound
- Greedy Algorithm
- Backtracking
Each algorithm offers a different perspective on how to approach and optimize the solution under the defined constraints.
This project is implemented in Python and includes a visual representation of the TSP routes generated by the algorithms.
It aims to provide both a theoretical understanding of the problem and a practical demonstration of how additional rules affect the possible solutions.
By introducing extra rules such as time windows and speed limits, the Traveling Salesman Problem becomes more realistic and challenging.
This version of the TSP better reflects real-world route planning scenarios and serves as an excellent framework for exploring algorithmic optimization techniques.