Any Sat Navs able to sort by location?

Howdy folks,

Lets say for argument sake, you're a delivery driver with a lot of deliveries, or you're a tourist that wants to see several heritage spots before your holiday is over, etc. and you have a set list of places you need to visit, scattered wildly across the country.


For example, a delivery driver loads his van with 50 deliveries for the day. He is given a couple of pages or a spreadsheet or whatever, which has all his addresses or coordinates at the ready.


Is there a sat nav on the market, or a similar device, that he can load all of his addresses into, and it will work out a route for him to take, to deliver his load (wahey) in the most sensible order. And if it takes him several days, he can knock it off each night, and it'll continue on from where it left off?


As a driver against the clock and trying to save fuel, it's in his interest to not deliver to A, B and C, only to realise that D is actually right between A and B, so he has to drive all the way back to where he started because he wasn't familiar with the area, etc.


Does such a thing exist? I presume that if it does, it's made by Google (google earth and maps, etc.)?


(this isn't a hypothetical thread, by the way. I actually need to purchase this product if it exists!). If it doesn't exist, can anyone recommend the next best solution to such a predicament?


Cheers

Plopli

I don't know but look up 'Travelling Salesman Problem' ...

It's considered a 'hard' problem to solve for computers.
I'm pretty sure centralized fleet routing software offer this kind of functionality but I never saw a consumer GPS with it.

It seems that QGIS/Postgres combination can do it.
http://carsonfarmer.com/2010/10/pgrouting-openstreetmap-and-qgis/

A few companies offer pgRouting commercial support:
http://pgrouting.org/support.html

Visiting their sites may give you information on what is possible.

Plopli

Indeed, from one of the companies:
http://imaptools.com/traveling-sales.html

And yet another one:
http://georepublic.de/en/projects/openvrp/

Special Circumstances

[Deleted User] wrote: »

Does such a thing exist? I presume that if it does, it's made by Google (google earth and maps, etc.)?

Google maps won't even let you set one "via" point on a mobile device!

ironclaw

Plopli wrote: »

I don't know but look up 'Travelling Salesman Problem' ...

One of the hardest problems for computers to solve.

The simplest solution, and it won't be the best, is to sort based on straight line distance from the origin. This may not (probably won't) be the 'fastest' route however.

Alternatively, it depends if you must pre-compute or not. If not, and given the live traffic available on Google maps, you could keep hopping based on the closest / fastest as you go between the stops. The issue is, you won't know your route in advance.

Alun

ironclaw wrote: »

One of the hardest problems for computers to solve.

Indeed. It sounds easy to a non-mathematician but it's part of a family of mathematical problems that are called NP-Complete.

http://en.wikipedia.org/wiki/NP-complete

Another one that may also be relevant to delivery comapnies is the Knapsack problem, where you have a number of packages of different sizes and values, and you have to maximize the value of those packages you can fit into your "knapsack", or in this case, van! Again, sounds easy but is not realistically solvable for any real-life number of items.

There's lots of research gong into using quantum computers to solve these kinds of problems, but you can't expect a lowly processor in a satnav or phone to be able to get very far with something like that I'm afraid.

hi5

AA Route Planer will give you as many 'via' as you like and will then give you directions, would it really be that difficult to overlay onto a sat nav, how many 'via' on Garmin?

micks_address

can you set up the 'stops' as favourites on the sat nav software and just hit each one in turn?

GavMan

micks_address wrote: »

can you set up the 'stops' as favourites on the sat nav software and just hit each one in turn?

Think he wants the sat nav to set the stops in some sort of logical order and set optimal routes...

It seems quite simple in theory. Enter and Geocode your starting address, then enter in all your other stop addresses and geocode them. Then route each of those points individually from your starting point, calculating their distance and sorting them by distance.

Then render a map, display those points on it and then layer the routes that you generated to calculate the distances, starting with the nearest first and bobs your uncle...

cletus

If I'm correct,I think the problem is that simply travelling from start to nearest, then from that point B to the nearest to it, will not necessarily result in the shortest over all distance, only the individual shortest distances been any two points.

Rowley Birkin QC

(Full disclosure; I work for this company)

Check out www.eSpatial.com

You can upload the locations using a spreadsheet of addresses (https://help.espatial.com/data/add-data/) or add them one by one.

You can then use the Routing tool (https://help.espatial.com/routing/) to select up to 25 locations, including a start and finish point and get the optimum way to visit the locations.

You can then export the map to Google maps, preserving the route order and use it for navigation on your phone/tablet.

Here's a sample one that uses the pubs from http://irishpubfilm.com/ . Shows an optimised route to visit all of them, starting and finishing at The Gravediggers in Dublin. Click the image for an interactive version.

[URL="https://us.v-cdn.net/6034073/uploads/attachments/62501/341731.PNG[/IMG][/URL]

Here's the Google Maps link that you could use for nav on an android or ios device:

Cheers for all the replies, guys.

So, Rowley seems to have the most 'readily available' option. My issue with it being, simply, that it only allows 25 locations. I'd be looking at approximately 100-200 locations.


I've been googling around myself, and completely by chance, I came upon this:


http://support.garmin.com/support/searchSupport/case.faces?caseId={079c9120-cfd1-11df-e7d8-000000000000}

Trip Planner provides you the ability to create and save a trip with multiple destinations and can be found on certain devices. Trip Planner offers the following features:

- Allow the GPS to Optimize the order of your destinations, providing you with the most efficient route.

So I suppose I have to ask - has anyone ever used this? Too good to be true?

Kavs

You should try Nokia's Here Maps solution, its the most aaccurate sat-nav solution out there and heres the best bit its free and it can be used offline so no data charges. Might be worth a try?

https://m.youtube.com/watch?v=mHbdLRvTChE

Just a quick update - I picked up a Garmin sat nav with the trip planner function, and it works like a dream.

coylemj

There is another variable for fleet planning which is the weight of the cargo when there are multiple deliveries of relatively heavy goods so for example if you are sending out an oil tanker to deliver to multiple locations, the amount of fuel to be delivered (and therefore the weight reduction) at each drop will be a factor in determining the optimum route. I know that one of the oil companies had s/w to devise the best route each day for their tankers, I'm sure they all do at this stage. Even though they're getting the fuel for the trucks at cost price, fuel efficiency on each run was still a factor in keeping down costs.

galvo_clare

I could swear my Garmin has this function although I've never used it so don't shoot me if I'm wrong.

Deleted User wrote: »

Howdy folks,

Lets say for argument sake, you're a delivery driver with a lot of deliveries, or you're a tourist that wants to see several heritage spots before your holiday is over, etc. and you have a set list of places you need to visit, scattered wildly across the country.




Cheers