1. OCAU Merchandise now available! Check out our 20th Anniversary Mugs, Classic Logo Shirts and much more! Discussion here.
    Dismiss Notice

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,241
    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:
    63,548
    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:
    609
    And can you do it in Log(n) time please?
     
    Phido likes this.
  4. Hater

    Hater Member

    Joined:
    Nov 19, 2012
    Messages:
    4,955
    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,403
    Location:
    Broadview SA
  6. power

    power Member

    Joined:
    Apr 20, 2002
    Messages:
    63,548
    Location:
    brisbane
  7. shredder

    shredder Member

    Joined:
    Dec 26, 2001
    Messages:
    13,901
    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,977
    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,241
    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:
    6,153
    Location:
    AvE
    elvis surely ai could solve this?
     
  11. shredder

    shredder Member

    Joined:
    Dec 26, 2001
    Messages:
    13,901
    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:
    90
    Location:
    Sydney
    Badger Maps.
     
  13. chook

    chook Member

    Joined:
    Apr 9, 2002
    Messages:
    2,210
    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,241
    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:
    13,901
    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:
    63,548
    Location:
    brisbane
    This looks pretty ok.
     
  17. nav

    nav Member

    Joined:
    Aug 20, 2001
    Messages:
    4,056
    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
  19. doug81

    doug81 Member

    Joined:
    Jul 18, 2005
    Messages:
    4,646
    Location:
    Cambodia
    Where I used to work we used Oracle for our work allocation software, allocating ~5k jobs daily to ~1k contractors nationally (metro and regional). Worked with them to implement auto-routing optimisation. We spent over 200K on Oracle staff configuring their own product to do this (which we were already spending a couple of million a year on). We previously had about a dozen people scheduling and allocating work, and the best we could get to was having half that. It ran like a dogs breakfast and couldn't take in many of the conditions we required, even with the 'workarounds' suggested by the owners of the product. Much of my hatred of dealing with Oracle stems from this project, just an expensive piece of shit.

    FYI, I went on to found an AI startup that has since been wound up. But before that I went through the Startup Chile accelerator and one of the previous generations had a route optimisation company - https://www.simpliroute.com/en/route-planning - worth checking out as they were having some success over in LatAm, and I'm sure the solution would work in a similar way in Aus. The CEO's name is Alvaro Echeverria if that's of any use to you...
     
  20. ^catalyst

    ^catalyst Member

    Joined:
    Jun 27, 2001
    Messages:
    11,894
    Location:
    melbourne

Share This Page

Advertisement: