+ Reply to Thread
Results 1 to 6 of 6

A Star Heuristic for Shortest Route

  1. #1
    Registered User
    Join Date
    10-26-2021
    Location
    Johannesburg, South Africa
    MS-Off Ver
    2019
    Posts
    3

    A Star Heuristic for Shortest Route

    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.
    Attached Files Attached Files

  2. #2
    Forum Moderator - RIP Richard Buttrey's Avatar
    Join Date
    01-14-2008
    Location
    Stockton Heath, Cheshire, UK
    MS-Off Ver
    Office 365, Excel for Windows 2010 & Excel for Mac
    Posts
    29,464

    Re: A Star Heuristic for Shortest Route

    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
    Attached Images Attached Images
    Attached Files Attached Files
    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.

  3. #3
    Forum Guru
    Join Date
    04-13-2005
    Location
    North America
    MS-Off Ver
    2002/XP and 2007
    Posts
    15,803

    Re: A Star Heuristic for Shortest Route

    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.
    Quote Originally Posted by shg
    Mathematics is the native language of the natural world. Just trying to become literate.

  4. #4
    Registered User
    Join Date
    10-26-2021
    Location
    Johannesburg, South Africa
    MS-Off Ver
    2019
    Posts
    3

    Re: A Star Heuristic for Shortest Route

    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

  5. #5
    Forum Guru
    Join Date
    04-13-2005
    Location
    North America
    MS-Off Ver
    2002/XP and 2007
    Posts
    15,803

    Re: A Star Heuristic for Shortest Route

    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.

  6. #6
    Forum Moderator - RIP Richard Buttrey's Avatar
    Join Date
    01-14-2008
    Location
    Stockton Heath, Cheshire, UK
    MS-Off Ver
    Office 365, Excel for Windows 2010 & Excel for Mac
    Posts
    29,464

    Re: A Star Heuristic for Shortest Route

    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.

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Star Trek DS9
    By Pepe Le Mokko in forum The Water Cooler
    Replies: 1
    Last Post: 12-09-2019, 06:04 PM
  2. Excel Combination Solver for Determining Shortest Route
    By excelcombinations in forum Excel Programming / VBA / Macros
    Replies: 1
    Last Post: 09-15-2017, 08:24 AM
  3. Replies: 1
    Last Post: 01-17-2010, 02:49 PM
  4. What is the use of the star before AND in if statement
    By arfanvilla in forum Excel General
    Replies: 4
    Last Post: 07-04-2008, 05:54 AM
  5. Bob- you are a star!
    By Dharsh in forum Excel General
    Replies: 0
    Last Post: 04-28-2005, 09:06 AM
  6. [SOLVED] star
    By shashi in forum Excel General
    Replies: 2
    Last Post: 04-03-2005, 12:06 PM

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1