Routing errors in London

[ img ]

Moderators: Unholy, Timbones

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: 1589
Joined: Wed Aug 20, 2014 11:19 am
Location: Gone!
Has thanked: 35 times
Been thanked: 50 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.
Twister-UK
Area Manager
Area Manager
 
Posts: 2529
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 369 times
Been thanked: 2182 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!

[ img ]
dknight212
 
Posts: 4963
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.
Twister-UK
Area Manager
Area Manager
 
Posts: 2529
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 369 times
Been thanked: 2182 times

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: 4963
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 9:52 am

Curiouser and curiouser...

To aid repeatability, I've now run some tests placing the start and end points at obvious places on the map. With the start point at the end of Games Lane in Cockfosters, I started generating routes southwards as before.

[ img ]

This screengrab was taken from an earlier test, hence the route summary box showing a different end point to those mentioned below...

With an end point at the north end of the B219, both the proposed routes are OK.

[ img ]

However, move the end point just a few yards further to the south, and now the route via the A406 stops short to the north of the A2214... Checking that section of the B219 in WME shows no oddities - it's a single segment between its junction nodes with the A2214 and The Gardens, so moving the end point south like this hasn't added any extra node/junction traversals compared with the route that ends right at the top end of the B219 - this time it's purely the extra distance that seems to be messing things up.

[ img ]
Twister-UK
Area Manager
Area Manager
 
Posts: 2529
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 369 times
Been thanked: 2182 times

Re: Routing errors in London

Postby Twister-UK » Tue Jul 23, 2013 6:21 am

Still at home, and now this morning all of the routes that were broken as per my original post, and seemed to be fixed as per my second post, are now broken again... Also broken is Cockfosters to Wandsworth, which is now behaving the same way Cockfosters to Balham did originally - either not returning any route, or returning two routes one of which stops short of the destination.

Cockfosters to Fulham, Finchley, and other destinations closer to the origin, all seem to work OK. Cockfosters to Catford and Brighton also work OK, once again indicating that it's not a simple distance-related bug. The calculation for the Brighton route also took considerably longer than any of the failed route attempts, suggesting also that the routing engine isn't simply timing out whilst trying to generate some of those shorter routes.

Cricklewood to Wimbledon works fine, so it doesn't appear to be a basic problem with the map data itself - between the successful Cockfosters-Fulham and Cricklewood-Wimbledon routes, all of the required segments and junctions have been traversed by one or other of the routes, and with more than sufficient overlap in the middle to avoid any risk of it being a segment/junction somewhere in the Fulham area that might be causing the problem.

To avoid the A406/A10, I also looked at routing due south from Cockfosters. Routes to Kennington and Camberwell come up fine, yet routes to Herne Hill, Dulwich and Sydenham all fail.

I'm thinking algorithm problem at this point - breaking the routes down into smaller chunks allows routing, so it's not a case of incorrectly set segment directions/turn permissions etc somewhere between the overall start and finish points preventing routing at all. Distance, or at least complexity of the route, is somehow involved - as noted above it's not simply a case of "routes > x miles = failure", but perhaps more a case of "routes traversing more than x nodes or requiring more than y instructions to turn from one segment to another = failure". This could account for the longer distance routes (e.g. Cockfosters-Brighton) working OK, as they start to skip large sections of the urban crawl that's required for the shorter routes contained entirely within London, and instead get routed over the trunk roads which offer more miles per node/instruction.
Twister-UK
Area Manager
Area Manager
 
Posts: 2529
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 369 times
Been thanked: 2182 times

Re: Routing errors in London

Postby Twister-UK » Mon Jul 22, 2013 9:44 pm

Checking the above routes from home a few hours later, Cockfosters to Balham, Wimbledon, Sutton and Croydon now all work perfectly. Friern Barnet and Bounds Green to Wimbledon also work fine.

Bounds Green to Southfields is still broken, as are several other randomly chosen starting points, however Bounds Green to a specific road within Southfields is OK.

I'll check again at work tomorrow...
Twister-UK
Area Manager
Area Manager
 
Posts: 2529
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 369 times
Been thanked: 2182 times

Re: Routing errors in London

Postby seriousarsonist » Mon Jul 22, 2013 9:10 pm

dknight212 wrote:Pip - thanks! Are yours complete routing failures or just odd routes?


Bit of both but more the later, checked a few out and they worked then they didn't , so really not sure what is going on. I did check the routes but found nothing untoward bar a few dodgy nodes which I fixed. Will look at some of your routes tomorrow


NI area manager
Waze Beta - iPhone 4s iOS 6.1.2 not jail broken
seriousarsonist
 
Posts: 1048
Joined: Thu Sep 27, 2012 6:48 pm
Location: Northern Ireland
Has thanked: 377 times
Been thanked: 146 times

Re: Routing errors in London

Postby dknight212 » Mon Jul 22, 2013 4:51 pm

This is really helpful, thanks a lot.

Do you have any ideas as to whether this is a map or an algorithm based problem?
dknight212
 
Posts: 4963
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