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,152
    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:
    61,037
    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:
    503
    And can you do it in Log(n) time please?
     
  4. Hater

    Hater Member

    Joined:
    Nov 19, 2012
    Messages:
    4,323
    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,072
    Location:
    Prospect SA
  6. power

    power Member

    Joined:
    Apr 20, 2002
    Messages:
    61,037
    Location:
    brisbane
  7. shredder

    shredder Member

    Joined:
    Dec 26, 2001
    Messages:
    12,474
    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,789
    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,152
    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,656
    Location:
    Some place far away
    elvis surely ai could solve this?
     
  11. shredder

    shredder Member

    Joined:
    Dec 26, 2001
    Messages:
    12,474
    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

Share This Page

Advertisement: