Maps and the Traveling Sales Man

In this idea, I present a solution for travelers and small companies. The idea is very simple, and it could be added to any map service available online. It could be employed if the person is going to visit three locations or more.

The Problem:

Often a person has to visit three locations or more in a time frame, lets say one day. The problem is that the person has to make the decision about the order of the visits so no time or money is wasted. in order to achieve that the person has to put many parameters in consideration. eg:

The distance between each location and the other.
The estimated traffic according to time.
The perfect root between every two locations.
Putting all these in consideration, one can see that its a tough decision to make even if the number of locations is only three.

The solution:

This Optimization Problem is called the Traveling Sales Man, there are optimization methods to solve the problem. What is meant by optimization in this context is that we want to maximize the number of locations visited in the time frame, and minimizing the cost (Petrol) at the same.

So, how does this work?

first of all we want to look at the ordinary Traveling Sales Man Problem, as stated in Wikipedia:

“The travelling salesman problem (TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?”

But in this Post I added two more parameters, Petrol and traffic according to time. If we just to add the feature to map services without these two additional parameters as an option or requirement, I doubt the practicality of the solution provided by any optimization method.

of course of we add the two new parameters to any optimization software, we will need more processing resources and more data, which means forecasts for daily and hourly traffic. The processing power and the data are both available with the map services companies. What remains is there will to add that feature to there map services.

Below is an Optimization algorithm in action trying to find the perfect root.