Travelling Salesman Problem - Route optimisation

Discussion in 'General Software' started by mmBax, Jan 9, 2020.

  1. mmBax

    mmBax Member

    Joined:
    Oct 26, 2011
    Messages:
    3,183
    Apparently that’s what it is commonly referred as.

    With work, every so often we get a job land on our desk that requires us to travel across the countryside. Generally the sites are bunched around a town or two, but every now and then you get a mixed bag that throws you all over the countryside and it'd be nice to be able to plan an efficient route.

    Is anybody aware of any software, or something relatively cheap, that will allow you to import multiple sites and have it optimise the travel route for you?

    Something that isn’t really outdated, something that ultimately allows you to upload a kml/kmz.
    Even better if it allows you to set travel time and a rough time per job site.

    It’s one of those things that I’ve been doing by eye, but as the number of sites increase, it starts getting a bit harder to judge where you’ll end up at the end of the day. And it’s nice to be able to plan where I need accommodation.

    I’ve trialled https://www.myrouteonline.com/ - which seems pretty good, no kml import, but you can import the coordinates from a text or csv I’m assuming. Unfortunately it’s crazy expensive. 1 credit per address. 100 credits for 30 dollars a month or 500 dollars for 6000 in a year. For scale I think we'd be looking at 2000 unique sites at this stage.

    Apparently Microsoft Streets and Trips was good at it but that is no longer available either.

    Seems like it'd be a very common question, especially amongst delivery companies for route planning?
     
  2. power

    power Member

    Joined:
    Apr 20, 2002
    Messages:
    62,211
    Location:
    brisbane
    if there's something cheap i'd like to see it because people would be all over this like stink on shit.
     
  3. Jumpingmanjim

    Jumpingmanjim Member

    Joined:
    Sep 20, 2008
    Messages:
    581
    And can you do it in Log(n) time please?
     
    Phido likes this.
  4. Hater

    Hater Member

    Joined:
    Nov 19, 2012
    Messages:
    4,666
    Location:
    Canberra
    cant throw a bunch of waypoints at google maps API? something something optimized for USPS only turning left something something
     
  5. theSeekerr

    theSeekerr Member

    Joined:
    Jan 19, 2010
    Messages:
    3,240
    Location:
    Broadview SA
  6. power

    power Member

    Joined:
    Apr 20, 2002
    Messages:
    62,211
    Location:
    brisbane
  7. shredder

    shredder Member

    Joined:
    Dec 26, 2001
    Messages:
    12,985
    Location:
    New Zealand
    Some questions I think are relevant.
    • What's your budget?
    • What's your expected workflow? Is it roughly: feed in your List of 2000 sites once (updating regularly over time), then be able to make a selection of sites from the List, and receive a travelling salesperson KML route for that selection of sites?
    I've done large scale geospatial tech work. A few years out of the game now. But my educated 10-minute-Google suggests the following initial open source leads :
    • A QGIS install with the addition of pgRouting, processing OSM street data. It'll take some work though, as in I could do it with my industry experience, but I don't like a layperson's chances unless they're highly technical and persistent.
    • Here is another option, alternative to the QGIS based setup. May be easier. Has tutorials onsite.
    Other than such an in-house option, you're stuck paying someone else to do it (by way of a paid service or subscription).
     
    Last edited: Jan 12, 2020
  8. Azrael

    Azrael Member

    Joined:
    Jun 27, 2001
    Messages:
    8,839
    Location:
    Melbourne
    As you would probably know the TSP is NP-VeryHard (technically its not NP Complete). But its visual-cognitively easy, I would stick with medium length planning visually.

    We spent a bunch of time and effort working on the psychology of this when I was at Adelaide Uni. See Yi, Steyvers, Lee and Dry (2011) or Vickers, D., Butavicius, M.A., Lee, M.D., & Medvedev, A. (2001)
     
  9. OP
    OP
    mmBax

    mmBax Member

    Joined:
    Oct 26, 2011
    Messages:
    3,183
    Thanks guys,

    I could probably discuss some purchasing with those higher up but I'm not sure how willing they'd be to jump on board. In the meantime I'll push it into the too hard basket and keep doing visual routing. We do have a lot of sites coming in but the requirements for needing a specifically routed path probably isn't high enough to justify the cost.

    8/10 'jobs' may just be sending us to Town A and Town B.
    The other 2 may send us all across the countryside, but like I said, it may not be worth the effort if its going to require more than a few hours of brain time.
     
  10. Hive

    Hive Member

    Joined:
    Jul 8, 2010
    Messages:
    5,873
    Location:
    Some place far away
    elvis surely ai could solve this?
     
  11. shredder

    shredder Member

    Joined:
    Dec 26, 2001
    Messages:
    12,985
    Location:
    New Zealand
    Course "AI" (read, in this case: a complex program) can do it. I was doing tsp's in ArcINFO Network Analyst a decade ago. Slightly prohibitive cost for a one-off though!

    I'd just break it into zones and go from there.
     
    Last edited: Jan 13, 2020
  12. Derfman

    Derfman Member

    Joined:
    Jul 6, 2014
    Messages:
    84
    Location:
    Sydney
    Badger Maps.
     
  13. chook

    chook Member

    Joined:
    Apr 9, 2002
    Messages:
    2,130
    I know this thread is kind of done but in case someone coems by in the future:

    I have never done geospatial work but I have worked alongside a team of dudes who looked after the data. They were all ESRI people because that is apparently the main player but they all raved about QGIS and how you could make it do whatever you wanted but you had to know how.
     
  14. OP
    OP
    mmBax

    mmBax Member

    Joined:
    Oct 26, 2011
    Messages:
    3,183
    Thanks again guys, we've just jumped over to ESRI not too long ago, I'll shoot the email off to somebody higher up that chain and see if anybody knows of ways to help out.

    It's probably way beyond the scope of what I was wanting.
    I wanted it so 1-10 staff could identify a route that happens maybe once or twice a month per person.
    If I shot it up the chain it has potential to impact/help 80-100 people but I'm not sure if the project would get legs.
     
  15. shredder

    shredder Member

    Joined:
    Dec 26, 2001
    Messages:
    12,985
    Location:
    New Zealand
    If you've got permanent GIS people, they tend to be underutilised/bored, so they might even appreciate something interesting to work on.
     
  16. power

    power Member

    Joined:
    Apr 20, 2002
    Messages:
    62,211
    Location:
    brisbane
    This looks pretty ok.
     
  17. nav

    nav Member

    Joined:
    Aug 20, 2001
    Messages:
    3,790
    Location:
    melbourne
    Bit late to the party, but you could use something like this in Excel:


    Not sure how many cities you’re dealing with, but manually building the table/matrix with time estimates from using Google Maps wouldn’t take too long.

    -nav.
     
  18. OppyLock

    OppyLock Member

    Joined:
    Dec 29, 2003
    Messages:
    47

Share This Page

Advertisement: