Routing errors in London

Image

Moderators: Unholy, Timbones

Re: Routing errors in London

Postby dknight212 » Tue Jul 23, 2013 12:15 pm

Chris

This is really useful work you're doing here. Thanks so much.

David
dknight212
 
Posts: 4964
Joined: Sun Apr 24, 2011 9:21 am
Location: London, UK
Has thanked: 473 times
Been thanked: 636 times

Re: Routing errors in London

Postby Twister-UK » Tue Jul 23, 2013 1:55 pm

Could there be a distance related aspect to this after all?

For these shorter cross-London routes, I'm noticing that when the dark-blue preferred route starts to fall short of the intended destination, the difference between the preferred and alternate route mileages is significant - you can see this in the earlier screengrabs, where the dark blue route is 42 miles whereas the pale blue route is only 26 miles. Adjusting the end point by a small amount then seems to cap the longer route at this distance (give or take half a mile or so), up to the point where Waze then returns no results at all. The capping distance isn't always 42 miles - repeating this test with a different end point gave a cap at 44.5 miles, then another test gave a cap of 45 miles - but once the routing code decides to cut the longer route short for a given area of the map (and probably also a given route into that area) it does then seem to stick to that cap until something fundamental changes in the route calculations.

I wonder if the routing algorithm starts to degrade once the difference in route mileage gets to a certain point (i.e. where the longer route option starts to fall short of the destination), before falling over completely when the difference gets too great (i.e. where no routes are generated at all)...


This might explain why the problem tends to appear on these cross-city routes, where there's a fast/lengthy option around the ring road vs a slow/short option directly across the city, but not as you start looking at even longer-distance routing (e.g. city to city) where any localised variation in routing mileage gets swamped by the much greater overall routing distance.

It could also explain why, so far, this problem only seems to crop up with N-S (or vice versa) routing across London, whereas E-W and W-E routing is OK - the shape of the North Circular (and to a less-well defined extent, the South Circular) means there's less of a distance differential between the time and distance route alternatives travelling E-W than when travelling N-S. Not a huge amount (a quick play around on Google Maps suggests it's a 1.4x distance penalty E-W vs 1.5x N-S), but it is there.
L4 AM for NW London and Shetland Islands - HTC One M8/Android 5.0.1
Waze App 3.9.9.0, not about to switch to 4.x any time soon...
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store
Image
Twister-UK
Area Manager
Area Manager
 
Posts: 2117
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 291 times
Been thanked: 1674 times

Re: Routing errors in London

Postby dknight212 » Tue Jul 23, 2013 3:18 pm

Ok testing some E-W routes:

A13 Alfred's Way (Barking) to A316 The Avenue (Richmond) = fail

coming in a bit to Mortlake I get two routes but both drop a bit short over the northside of the river. One of these uses the North Circular.

a bit more to the east side of Putney and we get two successful routes neither of which use the North Circular.

Ditto for Chelsea.

Woolwich to Chelsea ok

Woolwich to East Sheen = fail

Woolwich to Putney is a very interesting one so screen shotted. Destination is just by Wandsworth Park but although I get two routes one drops short on the north side whilst the south of the river one actually crosses the river to end up nearer the first one than the destination!

Image
dknight212
 
Posts: 4964
Joined: Sun Apr 24, 2011 9:21 am
Location: London, UK
Has thanked: 473 times
Been thanked: 636 times

Re: Routing errors in London

Postby Twister-UK » Tue Jul 23, 2013 8:29 pm

Once again, testing from home in the evening makes the routing engine seem like the pinnacle of coding excellence, with every requested route being delivered without fail... This is on the exact same system which, during breakfast time testing, makes the routing engine seem like a steaming pile of doodah. Meh.
L4 AM for NW London and Shetland Islands - HTC One M8/Android 5.0.1
Waze App 3.9.9.0, not about to switch to 4.x any time soon...
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store
Image
Twister-UK
Area Manager
Area Manager
 
Posts: 2117
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 291 times
Been thanked: 1674 times

Re: Routing errors in London

Postby CTCNetwork » Tue Jul 23, 2013 8:33 pm

Hi,

Good work guys. Would this have anything to do with the time that the routing is done? Is it confined to a particular time/s of day?
Does it tie up with say a busy route calculating period or maybe server/database cleanups or backups?

Des. . . ;)
CTCNetwork
 
Posts: 1581
Joined: Wed Aug 20, 2014 11:19 am
Location: Gone!
Has thanked: 34 times
Been thanked: 42 times

Re: Routing errors in London

Postby Twister-UK » Tue Jul 23, 2013 10:18 pm

CTCNetwork wrote:Would this have anything to do with the time that the routing is done? Is it confined to a particular time/s of day?


Testing in the mornings (6-7am) and around lunchtime (12-2pm) is when I see routing errors occurring, whereas testing in the evening (9pm onwards) seems to be pretty solid.


I've been running another quick test, leaving the start and end points unchanged and just calling the navigate() function from the console. Although I haven't been getting any errors (as expected given the time of day), I have noticed the routes returned change slightly every now and again, and I'm guessing this is the routing engine adjusting to the live traffic conditions out there right now.

Presumably then, during those times of the day when traffic conditions are more changeable (i.e. the start of the morning rush hour and throughout the working day), the routing engine will have more live data to contend with whilst trying to calculate its routes, and so maybe this is where the problem lies?
L4 AM for NW London and Shetland Islands - HTC One M8/Android 5.0.1
Waze App 3.9.9.0, not about to switch to 4.x any time soon...
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store
Image
Twister-UK
Area Manager
Area Manager
 
Posts: 2117
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 291 times
Been thanked: 1674 times

Re: Routing errors in London

Postby faitaru » Wed Jul 24, 2013 4:30 am

I've always thought the errors occur when the recommended route is significantly longer than the crow flies (rather than an alternative route).

It's going to be related to the problems you get routing between peninsulars; for example Barrow to Morecambe, Shoebury to Whitstable, Ilfracombe to Swansea.

Only difference is the cross city London routes have a straight line alternative, but I'm sure the problems with the longer Circular routes is the same.
iPhone 4S • iOS 8.2 • Waze 3.9.3928.928
AM for Nowhere :(UK Country Admin • iOS Beta Tester • Mega Driver
UK WikiUK ForumWaze UK on FacebookBecome a UK Area ManagerWaze Status
faitaru
Waze Global Champs
Waze Global Champs
 
Posts: 400
Joined: Thu Oct 21, 2010 6:07 am
Location: Bedfordshire, UK
Has thanked: 48 times
Been thanked: 65 times

Re: Routing errors in London

Postby dknight212 » Wed Jul 24, 2013 6:34 am

Chris - I think you have these tests scripted now, is that right? Is it very difficult to tabulate these results so Waze HQ have an easy reference for their checking? No worries if not.

Ideally something like: start lat/lon/street, finish lat/lon/street, time of day, success/fail, distance A, distance B

Just shoot me if I'm asking too much!
dknight212
 
Posts: 4964
Joined: Sun Apr 24, 2011 9:21 am
Location: London, UK
Has thanked: 473 times
Been thanked: 636 times

Re: Routing errors in London

Postby Twister-UK » Wed Jul 24, 2013 11:51 am

dknight212 wrote:Chris - I think you have these tests scripted now, is that right? Is it very difficult to tabulate these results so Waze HQ have an easy reference for their checking? No worries if not.

Ideally something like: start lat/lon/street, finish lat/lon/street, time of day, success/fail, distance A, distance B


I haven't automated any of it yet, but it's something I was mulling over this morning...

Just shoot me if I'm asking too much!


Inbound, weapons hot :mrgreen:


Something else that crossed my mind regarding the interaction between the routing algorithm and the traffic data - since the traffic data changes quite frequently at certain times of the day, I wonder if the routing code takes a snapshot of the data before starting to generate each new route, or if it just assumes that the live data isn't going to change significantly during the calculation of the new route. If the latter, then there's always the chance that during the calculations the data has changed in such a way that the intended route breaks whatever internal thresholds/sanity checking are set for the routing code.

Given that it generally seems to be the quickest route option that starts to fall short of the intended destination before the routing code gives up completely, this would tie in with it being traffic data related - the shortest route would only be affected if the road closure data got updated during the routing calculation, whereas changes in traffic density shouldn't affect it at all (it doesn't care how long it takes to get from A to B...).
L4 AM for NW London and Shetland Islands - HTC One M8/Android 5.0.1
Waze App 3.9.9.0, not about to switch to 4.x any time soon...
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store
Image
Twister-UK
Area Manager
Area Manager
 
Posts: 2117
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 291 times
Been thanked: 1674 times

Re: Routing errors in London

Postby dknight212 » Wed Jul 24, 2013 11:53 am

Twister_UK wrote:
Something else that crossed my mind regarding the interaction between the routing algorithm and the traffic data - since the traffic data changes quite frequently at certain times of the day, I wonder if the routing code takes a snapshot of the data before starting to generate each new route, or if it just assumes that the live data isn't going to change significantly during the calculation of the new route. If the latter, then there's always the chance that during the calculations the data has changed in such a way that the intended route breaks whatever internal thresholds/sanity checking are set for the routing code.

Given that it generally seems to be the quickest route option that starts to fall short of the intended destination before the routing code gives up completely, this would tie in with it being traffic data related - the shortest route would only be affected if the road closure data got updated during the routing calculation, whereas changes in traffic density shouldn't affect it at all (it doesn't care how long it takes to get from A to B...).


Good thinking, could test by rerunning the same route several times?
dknight212
 
Posts: 4964
Joined: Sun Apr 24, 2011 9:21 am
Location: London, UK
Has thanked: 473 times
Been thanked: 636 times

PreviousNext

Return to United Kingdom

Who is online

Users browsing this forum: No registered users