Bidirectional Dijkstra Routing

[aerostitch]

Issue migrated from trac ticket # 1258

component: core | priority: major | keywords: bidirectional search

2014-10-01 01:11:50: marcuspueschel@googlemail.com created the issue

---

Hello everybody,

as recommended in the Navit-IRC channel, i provide a diff for the route.c that implements the bidirectional version of the Dijkstra to reduce the time needed for calculate a route request. In a next step the pthreads have to be exchanged by the Glib Threads to ensure the portability to other platforms that do not support pthreads.

Greetings, hoschi

[aerostitch]

2014-10-01 01:12:12: marcuspueschel@googlemail.com uploaded file route.c_bidirDijkstra.diff (48.5 KiB)

[aerostitch]

2014-10-17 15:53:49: @pgrandin commented

---

That's quite a lot of work here!

Unfortunately it's really hard to merge this patch as is : can you please update your code to make it configurable?

Ultimately, we should start by having it disabled until we can gather some user feedback, before enabling it by default.

Thanks a lot for your contribution!

[aerostitch]

2014-10-18 01:11:31: tryagain commented

---

Marcus,

Can you please share your results regarding actual performance benefit, memory usage analysis before and after applying the patch?

Thank you for your work.

[aerostitch]

2014-12-19 10:41:20: @jandegr commented

---

Hi, I got it to compile and run after I glued the following in :

double now_ms()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec*1000. + tv.tv_usec/1000.;
}

or did I miss out on something ?

The patch says

/**@brief varaibles used for enabling and disabling functions
 -
 - These variables are influenced by the menue and control if the bidirectional routing
 - and also the parallel graph buildup are used or not.
 -/
int useBidirectionalRouting = 0;
int useBidirectionalMultiThread = 0;

I could test it by recompiling it with both 0's changed to 1's, but do you have some code to change it from the menu as the comment suggests ?

I did no get in to real comparison or statisticsyet, but I get the following output after compiling it for Multithread :

navit:route_graph_build:route_calc_selection() took: 0.01 ms
navit:route_graph_build:mapset_open() took: 0.00 ms
navit:route_graph_build_done:build took: 789.02 ms
navit:route_graph_flood_bidirectional2Threads: took: 1.510 ms
navit:route_graph_build_done:build took: 7323.51 ms

so I suppose it runs ok ?

The route is drawn correct, but the demovehicle runs 50 meter forth and back on the start of the route forever.

Jan

[aerostitch]

2014-12-19 10:59:40: marcuspueschel@googlemail.com uploaded file gui_internal_command.c.diff (0.9 KiB)

[aerostitch]

2014-12-19 10:59:47: marcuspueschel@googlemail.com uploaded file navit_shipped.xml.diff (0.5 KiB)

[aerostitch]

2014-12-19 11:00:31: marcuspueschel@googlemail.com uploaded file route.c_bidirDijkstra.2.diff (48.5 KiB)

[aerostitch]

2014-12-19 11:02:55: marcuspueschel@googlemail.com commented

---

Hello Jan, i've attached three files for you. There is an menu Extension and a new diff for the route.c-file. it compiles just fine. Navigation functions properly but i can not exclude bugs.

I wish you a happy christmas, Marcus

[aerostitch]

2014-12-19 13:38:06: @jandegr commented

---

Hi Marcus, Thanks for the update, control from the menu works fine, and route calculation goes fine as well, but the demovehicle keeps acting funny on a 1T or 2T calculated route. I am convinced it works fine for normal driving, I just happen to do a lot of testing with the demovehicle

EDIT 20/12 : Now I had many tests go well at the start of the route, but had the demovehicle jump forth and back at the end of the route EDIT : first debugging leads to : in navigation_update (navigation.c) the updates of a traditional route result in a 'turn_around= -2' of that specific debugging line, routes 1T or 2T output other numbers for turnaround, causing the route to be reprocessed completely at each update.

Tested on Navit 5976 in Ubuntu

Happy christmas to you too Marcus, Jan

[aerostitch]

2014-12-19 13:38:06: @jandegr

[aerostitch]

2014-12-19 13:38:06: @jandegr

[aerostitch]

2014-12-19 13:38:06: @jandegr

[aerostitch]

2014-12-19 13:38:06: @jandegr

[aerostitch]

2015-02-07 23:46:58: @jandegr commented

---

Hi Marcus If you calculate a route the classic Navit way and switch on the route graph map, it shows a serie of descending values along the path representing the remaining cost to the destination. Demovehicle drives the cheapest and follows these values to destination. In case of a bidir calculated route, it shows a serie of ascending values up to the common point and there a sequence of descending values towards destination starts. Demovehicle gets completely confused by this. I could partially solve it by assigning the correct values to the routepoints in calculate_costs_and_set_ref() but for a complete solution, on the points next to the route those values should simply be removed, otherwise demovehicle will still wander off from the route on some crossing where it still finds a seamingly cheaper way. I suppose using something like value_back instead of value in the backwards part of the bidir loop could solve this.

reagards, Jan

[aerostitch]

2015-02-07 23:46:58: @jandegr