tapasBerlin-routing astar is slow due to usage of districts (trac #3144)

[behrisch]

The A* heuristic uses getDistanceTo() which always returns 0 if the origin or destination is a district edge. This effectively turns the algorithm into a Dijkstra search.

Instead, each district edge should record its geometric center and radius for computing a lower bound on distance.

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

{
    "status": "closed", 
    "changetime": "2017-05-31T08:41:01Z", 
    "description": "The A* heuristic uses getDistanceTo() which always returns 0 if the origin or destination is a district edge. This effectively turns the algorithm into a Dijkstra search.\n\nInstead, each district edge should record its geometric center and radius for computing a lower bound on distance.", 
    "reporter": "namdre", 
    "cc": "", 
    "resolution": "fixed", 
    "_ts": "1496220061172461", 
    "component": "tapasVEU", 
    "summary": "tapasBerlin-routing astar is slow due to usage of districts", 
    "priority": "major", 
    "keywords": "", 
    "time": "2017-05-24T15:53:46Z", 
    "milestone": "1.0.0", 
    "owner": "behrisch", 
    "type": "defect"
}

[behrisch]

• @namdre changed _comment0 from:

actually:

• geometric center of district-edge from nodes (and radius)
• geometric center of district-edge to nodes (and radius)

to:

1495655423789687

• @namdre commented:

save:

• for taz-source edges the geometric center of the to-nodes of all edges along with the radius
• for taz-sink edges the geometric center of the from nodes of all edges along with the raidus

the best center value would be the solution to the https://en.wikipedia.org/wiki/Smallest-circle_problem along with the radius of that circle.

The center of the bounding-box should be a sufficient approximation.

[behrisch]

@namdre changed type from "enhancement" to "defect"

[behrisch]

• @namdre changed description from:

The A* heuristic uses getDistanceTo() which always returns 0 if the origin or destination is a district edge.

Instead, each district edge should record its geometric center and radius for computing a lower bound on distance.

to:

The A* heuristic uses getDistanceTo() which always returns 0 if the origin or destination is a district edge. This effectively turns the algorithm into a Dijkstra search.

Instead, each district edge should record its geometric center and radius for computing a lower bound on distance.

• @namdre changed summary from "tapasBerlin-routing astar is low due to usage of districts" to "tapasBerlin-routing astar is slow due to usage of districts"

[behrisch]

@behrisch commented:

Wouldn't bounding boxes instead of circles do as well? (although the distance calculation takes a little bit more effort)

[behrisch]

@behrisch committed 46d67a0 (aka r24514): towards a better A* with taz, refs #3144

[behrisch]

@behrisch committed 3e60b15 (aka r24519): test for A* with taz, refs #3144

[behrisch]

@behrisch committed f942ce9 (aka r24521): adding A* taz test for duarouter, refs #3144, #21

[behrisch]

• @behrisch committed 0518c5f (aka r24522): A* with taz in duarouter, fix #3144
• @behrisch changed owner from "" to "behrisch"
• @behrisch changed resolution from "" to "fixed"
• @behrisch changed status from "new" to "closed"