Routing errors in London

Image

Moderators: Unholy, Timbones

Re: Routing errors in London

Postby Twister-UK » Fri Jul 26, 2013 8:25 pm

Too impatient to wait until after midnight to see the full set of results from today, so here's a sneak preview... Same start and endpoints as yesterday.

Image

As with yesterdays testing, the shortest route always reached the intended endpoint (where Livemap returned routes), and its distance only varied slightly every now and again, so I haven't bothered plotting that one this time. The above plot concentrates on the quickest route results where, as we saw yesterday, things tend to go awry.

Once again, the yellow regions of the plot shows where the route fell short of the endpoint. Unlike yesterday, we now also have data to show where Livemap failed to return any results, these are the red regions. There's one very slender red region just after 08:00 (which pretty much coincides with when the logging fell over yesterday...), then a slightly wider region around noon, and then from just after 15:00 through to almost 19:00 the routing engine was almost entirely incapable of returning any routes - there's just that very brief period around 15:30 where a single incomplete route is generated... Once the routes start to be reliably generated again just before 19:00, they remain incomplete until just after 20:00 where they seem to return to normality again.
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 times

Re: Routing errors in London

Postby Twister-UK » Fri Jul 26, 2013 10:42 am

Twister_UK wrote:I left the script running this morning, so fingers crossed we should end up with a full 24-hour log of this route later tonight...


Sadly, script-o-matic Mk.1 was quickly hacked together in such a way that, if Livemap failed to return any routes, it'd require manual intervention to continue logging, and at just after 8am yesterday Livemap, not unexpectedly, failed to return any routes...

The all new and improved script-o-matic Mk.2 (cleans whiter than white, with 33% fewer calories, using the latest nanoparticle formulation) should now be able to resume logging automatically once valid routes are available again. It's been running on the same route since just before midnight yesterday, so at the very least I'll be able to compare the early morning results for two consecutive weekdays - be interesting to see if that 01:00-02:30 route shortening occurs again.
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 times

Re: Routing errors in London

Postby Twister-UK » Thu Jul 25, 2013 10:07 am

Bit of GIMPing (doesn't sound nearly as cool as Photoshopping...) gives us a mapped out view of all the endpoints for the above data

Image

The red dot shows the true endpoint (it appears I actually set it to a side road just off the B219, rather than the B219 itself...), and the blue dots show all of the incorrectly generated endpoints for the quickest routes within the yellow area of the earlier plot.
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 times

Re: Routing errors in London

Postby Twister-UK » Thu Jul 25, 2013 9:09 am

Early results from the first bit of script-o-matic testing...

Routing from my old favourite, Games Lane in Cockfosters (51.65501626,-0.156668998) down to the B219 in Peckham Rye (51.45954977,-0.06766258), logging started at 23:00 yesterday, with the script requesting a recalculation of the route (approximately) every minute.

Image

This is a plot of the route distances (blue = quickest, red = shortest) against time. Where the plot background changes to yellow, this indicates results where the two routes differ in their endpoints. For each result, the shortest route always reached the requested endpoint, so differences in the endpoints are entirely due to the quickest route failing to reach that endpoint. Whilst checking the progress of the script this morning, I could see on the Livemap window that the quickest route was falling well short of the endpoint - there was clear space between the two endpoint marker flags. I could also see that, at one or more points along the route, Livemap was reporting heavy traffic, whereas when I kicked off the test last night the map was clear of traffic issues.

Interesting also to note that period between 01:00 and 02:30ish where the quickest route manages to shed around 10 miles yet still reach the destination correctly.

I left the script running this morning, so fingers crossed we should end up with a full 24-hour log of this route later tonight...
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 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...).
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 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?
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 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.
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 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.
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 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.

Image

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.

Image

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.

Image
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 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.
Chris (not to be confused with Chris or Chris...)
L4 AM SE England & Shetland Islands / WME Beta Tester / Script Writer
WME/Livemap enhancement scripts @ GreasyFork and Chrome Web Store


ImageImageImage
Twister-UK
Beta tester
Beta tester
 
Posts: 2967
Joined: Sat Jan 07, 2012 12:00 am
Location: NW London
Has thanked: 451 times
Been thanked: 2785 times

PreviousNext

Return to United Kingdom

Who is online

Users browsing this forum: No registered users