Hi Everyone,
I was wondering if it is possible to run an A* Heuristic algortihm using Excel Solver given a table of cities and their distances between. I need to find the shortest route from City A to B.
I have submitted the table below.
Hi Everyone,
I was wondering if it is possible to run an A* Heuristic algortihm using Excel Solver given a table of cities and their distances between. I need to find the shortest route from City A to B.
I have submitted the table below.
Does the following help. I'm assuming this is the classic travelling salesman problem of visiting a list of cities by the shortest route.
I've chosen 7 cities from your grid and entered them on the Route sheet as a grid in B2:I9
Copy the trial numbers in C11:J11 to C13 and run the Solver shown in the picture
Richard Buttrey
RIP - d. 06/10/2022
If any of the responses have helped then please consider rating them by clicking the small star icon below the post.
I am not familiar with the A* heuristic. From what I can quickly glean from a quick internet search, the A* heuristic attempts to improve calculation times for shortest path problems by modifying the optimization algorithm. Since Solver is basically a "black box" and we don't have any control (other than choosing an overall solving method) over the details of the optimization algorithm, I have my doubts that one can incorporate both Solver and A* at the same time. I expect that attempts to program A* into Excel + Solver either drops the A* part in favor of Solver's built in algorithms and heuristics, or you end up dropping the Solver part as your attempts at A* completely take over the optimization algorithm, leaving nothing for Solver to do.
Edit to add: Unless, of course, Solver's programmers have already included A* heuristics into Solver's algorithms. I have not seen that level of documentation about the inner workings of Solver. If A* is already part of Solver's programming, someone from Frontline would need to provide documentation to that effect.
Last edited by MrShorty; 10-26-2021 at 01:33 PM.
Originally Posted by shg
Hi,
Thanks so much for your help thus far! While, it was useful, my problem is slightly different than a typical TSP as I don't necessarily need to visit each city, I only want to get from for example Madrid to Szezcin, in the most efficient way while only travelling less than 500 km per day.
I can do it by hand, but was hoping for a more efficient way on excel to do it
If I understand correctly, you aren't necessarily required to use the A* heuristic for this. Any algorithm that solves the shortest path problem will work. Is that correct?
This is a decent tutorial on solving shortest path problems in Excel: https://www.excel-easy.com/examples/...h-problem.html See if that helps with setting up a way to solve the shortest path problem.
I don't understand the explanation. Madrid to Szezcin on your matrix is 2489 Km
At 500 Km / day that will take 5 days. Are you saying that you want to go via any cities that are as close to 500 Km apart as possible?
If so then it seems that rather than a matrix of all distances you need to extract a matrix of cities where every pair is <= 500Km since there's no point considering any two cities which are greater than 500Km since by your rule you can't use them
Once you've got a smaller matrix of <=500 then it seems that the solution I offered in #4, which was just an abbreviated example of a complete matrix, will find the optimum route using Solver.
Is this a correct analysis
One other task which would probably help is to have a parallel matrix of the sub 500 Km distance between pairs of cities which showed information that identified the direction of travel, e.g. NE, SE, SW NW (North East, South East....) since the optimum solution is going to be between towns where the direction of travel is always in the same direction as that from the start city to the end city.
One this subset of < 500km and direction of travel reference is identified the solution should be more manageable and certainly quicker if some form of iteration is needed.
Last edited by Richard Buttrey; 10-29-2021 at 05:13 AM.
There are currently 1 users browsing this thread. (0 members and 1 guests)
Bookmarks