CODEWITHSUNDEEP
algorithmgraph-algorithm
bergin
bergin

Reputation: 1604

Looking for an algorithm for an efficient itinerary

Am wanting to write an app that helps say a travelling salesman / musician plan their tour.

So this is about making an efficient itinerary.

So they would put in their start and end points and the places they want to visit and the program would output a suggested route to encompass those points on a map.

The suggested route would obviously minimise the time, distance and financial costs assuming the edge info is given for nodes on the network.

Could someone post in some pseudo code or pointers to sites that describe the necessary algorithm(s) required to solve this problem.

I've looked at A* but that seems to be for just a start and end points.

Any ideas welcome

thanks

Alex

Upvotes: 1

Views: 1972

Answers (3)

Stefan Schröder
Stefan Schröder

Reputation: 1037

As the other authors wrote, it is a traveling saleman problem. For your musician tour planer you require both, (i) an algorithm that calculates the least cost path from one location to another [via a physical network] AND (ii) an algorithm that calculates the best sequence of locations given your start and end location and additional constraints such as time windows.

(i) can be solved with for example Dijkstra, A*, Contraction Hierarchies

(ii) can be solved with Held-Karp, Branch and Bound/Cut [exactly] and Lin-Kernighan, or any other (meta)heuristic that are also applied to solve vehicle routing problems (VRP) [heuristically]

However, implementing these algorithms efficiently is not matter of days. Thus I would recommend you to use existing software. For (i) GraphHopper will be a perfect choice and for (ii) you can try jsprit. Both are written in Java and are Open Source.

Upvotes: 4

Ari
Ari

Reputation: 2004

As mentioned, this is a case of the traveling salesman problem (TSP). Note that the TSP can be solved with a brute-force algorithm when n, the number of cities, is not too large. A musician may only want to visit 15 cities or less, so you can still find the best path with a brute-force search. You just need to calculate the weighting between the different cities (distance and other factors) and then check all possibilities to find the best possible routes. If there are more than 20 cities, you can still find the optimal solution, but you'll want a better algorithm than a direct brute-force search.

Upvotes: 1

Nuclearman
Nuclearman

Reputation: 5304

TSP (Travelling Salesman Problem) is what you want, you just will have to adjust the cost function so that it's not purely based on distance. Most likely you'll want to translate distance to an actual dollar value that accounts for the travel cost as well as the travel time.

It might be good to have a slider to bias the calculation towards either travel time or travel cost (time is money and all). Although, it's not clear how helpful it would be given how computationally intensive it tends to be to optimize a TSP instance.

Upvotes: 1

Related Questions