Routers ignore junction size/traveltime (trac #752)

behrisch commented 11 years ago

currently DUAROUTER only considers normal edges when computing shortest/fastest routes. In areas with several adjacent junctions, paths that maximize the number of traversed junctions may be preferred because the perceived traveltime is lower.

This sometimes leads to bad routes.

It is also a problem with for computing the A* (astar) straight-line traveltime heuristic since the sum of edge lengths may be lower than the straight-line distance between start and end junctions.

The solution would be to include internal edges in the network graph. This would also help with #2202 (also see #2566)

Migrated from http://sumo.dlr.de/ticket/752

{
    "status": "new", 
    "changetime": "2017-09-22T09:29:21Z", 
    "description": "currently DUAROUTER only considers normal edges when computing shortest/fastest routes. In areas with several adjacent junctions, paths that maximize the number of traversed junctions may be preferred because the perceived traveltime is lower. \n\nThis sometimes leads to bad routes. \n\nIt is also a problem with for computing the A* (astar) straight-line traveltime heuristic since the sum of edge lengths may be lower than the straight-line distance between start and end junctions.\n\nThe solution would be to include internal edges in the network graph.\nThis would also help with #2202 (also see #2566)\n", 
    "reporter": "namdre", 
    "cc": "", 
    "resolution": "", 
    "_ts": "1506072561352091", 
    "component": "routing (DUAROUTER)", 
    "summary": "Routers ignore junction size/traveltime", 
    "priority": "major", 
    "keywords": "sumo-user", 
    "time": "2012-09-25T09:25:51Z", 
    "milestone": "1.0.0", 
    "owner": "", 
    "type": "defect"
}

[ ] A*
[ ] internal junctions
[ ] less costs in car - public transfer

behrisch commented 11 years ago

@namdre changed milestone from "" to "1.0.0"

behrisch commented 11 years ago

@namdre changed summary from "DUAROUTER ignores junction size/traveltime" to "Routers ignores junction size/traveltime"

behrisch commented 11 years ago

@namdre changed summary from "Routers ignores junction size/traveltime" to "Routers ignore junction size/traveltime"

behrisch commented 11 years ago

@namdre changed description from:

currently DUAROUTER only considers edges when computing shortest/fastest routes. In areas with several adjacent junctions paths that maximize the number of traversed junctions may be preferred because the perceived traveltime is lower. This potentially degrades traffic flow.

to:

currently DUAROUTER only considers edges when computing shortest/fastest routes. In areas with several adjacent junctions paths that maximize the number of traversed junctions may be preferred because the perceived traveltime is lower.

This sometimes leads to bad routes.

It is also a problem with for computing the A* (astar) straight-line traveltime heuristic since the sum of edge lengths may be lower than the straight-line distance between start and end junctions.

The solution would be to include internal edges in the network graph. This would also help with #2202 (also see #2566)

behrisch commented 11 years ago

@namdre changed keywords from "" to "sumo-user"

behrisch commented 11 years ago

@namdre changed description from:

currently DUAROUTER only considers edges when computing shortest/fastest routes. In areas with several adjacent junctions paths that maximize the number of traversed junctions may be preferred because the perceived traveltime is lower.

This sometimes leads to bad routes.

It is also a problem with for computing the A* (astar) straight-line traveltime heuristic since the sum of edge lengths may be lower than the straight-line distance between start and end junctions.

The solution would be to include internal edges in the network graph. This would also help with #2202 (also see #2566)

to:

currently DUAROUTER only considers normal edges when computing shortest/fastest routes. In areas with several adjacent junctions paths that maximize the number of traversed junctions may be preferred because the perceived traveltime is lower.

This sometimes leads to bad routes.

It is also a problem with for computing the A* (astar) straight-line traveltime heuristic since the sum of edge lengths may be lower than the straight-line distance between start and end junctions.

The solution would be to include internal edges in the network graph. This would also help with #2202 (also see #2566)

behrisch commented 11 years ago

@namdre changed description from:

currently DUAROUTER only considers normal edges when computing shortest/fastest routes. In areas with several adjacent junctions paths that maximize the number of traversed junctions may be preferred because the perceived traveltime is lower.

This sometimes leads to bad routes.

It is also a problem with for computing the A* (astar) straight-line traveltime heuristic since the sum of edge lengths may be lower than the straight-line distance between start and end junctions.

The solution would be to include internal edges in the network graph. This would also help with #2202 (also see #2566)

to:

currently DUAROUTER only considers normal edges when computing shortest/fastest routes. In areas with several adjacent junctions, paths that maximize the number of traversed junctions may be preferred because the perceived traveltime is lower.

This sometimes leads to bad routes.

It is also a problem with for computing the A* (astar) straight-line traveltime heuristic since the sum of edge lengths may be lower than the straight-line distance between start and end junctions.

The solution would be to include internal edges in the network graph. This would also help with #2202 (also see #2566)

behrisch commented 6 years ago

still missing:

a test with multiple consecutive internal edges on a junction
speed comparison (also for A*)
recheck the intermodal edge output

namdre commented 6 years ago

The same issue also applies to routing in SUMO. Should I open up another ticket or would you just add another label to this one? The issue is potentially more complicated because multiple classes use the function MSEdge::getSuccessors() with the assumption that normal edges are returned. (FileHelper, MELoop, ...)

namdre commented 6 years ago

the current implementation is slower by ~ factor 3

total time for 10k random trips:

acosta --no-internal dijkstra: 71 edges, ~50ms acosta dijkstra: 173 edges, ~150ms acosta --no-internal astar: 63 edges, ~50ms acosta astar: 153 edges, ~130ms

bs --no-internal dijkstra: 12k edges, ~31s bs dijkstra: 33k edges, ~118s bs --no-internal astar: 9k edges, ~26s bs astar: 23k edges, ~84s

namdre commented 6 years ago

Suggested refactoring to improve speed:

EDGE::getSuccessors returns a list of pairs <normal edge, internalEdge>
- internalEdge is nullptr if option --no-internal-links is set or the network was built withount internal edges
EdgeInfo stores prevInternal along with prev
getEffort and getTravelTime take prevInternal as an additional argument
- the effort / travel time for the internal edge (and further internal edges if there is an internal junction) are added to the result

This keeps the size of the routing graph small while still taking internal edges into account.

namdre commented 5 years ago

@behrisch what is still missing to close this ticket?

behrisch commented 4 years ago

I would consider this one fixed although there are still discrepancies which might be a result f miscalculated internal lanes as in the latest change of landmark distances #6548

eclipse-sumo / sumo

Routers ignore junction size/traveltime (trac #752) #752