Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
KaTCH -- Karlsruhe Time-Dependent Contraction Hierarchies
Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Failed to load latest commit information.|
=========================================================== KaTCH -- Karlsruhe Time-Dependent Contraction Hierarchies =========================================================== Introduction ============ KaTCH is an implementation of time-dependent contraction hierarchies (TCHs), an algorithmic framework for fast and exact route planning in road networks that optimizes the travel time depending on the point in time when the journey starts. The implementation mainly follows the description by Batz et al.  but with some modifications. It covers the ordering stage of the preprocessing and the TCH-based EA querying. Construction of hierarchies for pre-existing node orders as well as other queries like ATCH-based EA querying and all kinds of profile queries are not yet included in KaTCH. Note that the Ordering not only computes a node order but outputs a fully functioning TCH structure. The TCH is written to file on-the-fly during the ordering process. It must be noted that KaTCH is NOT the implementation of TCHs that is used in the experiments reported by Batz et al. . Instead it has been widely reengineered and rewritten to provide more clear, more understandable, and more maintainable source code than the code developed during our research. The original TCH source code is quite experimental and not so easy to understand. KaTCH is released by Karlsruher Institut fuer Technologie (KIT) under the terms of GNU AGPL version 3 (see files 'LICENSE' and 'COPYING'). If you need a commercial license, please contact Prof. Peter Sanders <firstname.lastname@example.org> of KIT by writing an email. Performance =========== On the one hand, the preprocessing provided by KaTCH runs somewhat slower than in case of original code. Partly, this is because we switched from sparse arrays to hash tables to map nodes to internal objects during witness search. But also partly the reason is not known so far. Spending some time with more aggressive optimizing may make KaTCH as fast as the original implementation. On the other hand, the TCH structures generated by KaTCH are more accurate than in case of the original code. In the latter case the EA query of KaTCH shows a maximum relative error up to 0.00035% for an instance of the Western European road network with 1 million queries with randomly chosen start, destination, and departure time. In case of TCH structures generated by KaTCH we observe the much smaller 4.02313e-13% as maximum relative error. The EA querying of KaTCH runs significantly faster on the TCH representation of the Western Europe generated by the preprocessing of KaTCH than generated by the original code. A possible explanation could be that the more accurate TCH structures generated by KaTCH enable a more effective stalling than the somewhat less accurate structures generated by the original code. Modifications ============= KaTCH modifies the techniques described in  as explained in the following. 1. Preprocessing ---------------- The witness search is modified in the following way: - The Interval search runs in backward instead of forward direction. - The sample search is performed AFTER the interval search and runs on a thinned corridor (i.e., the predecessor graph of the backward interval search only storing the predecessors that improve the upper or lower bound of an interval) instead of the full remaining graph. Also, the sample search is performed is performed in the manner of an A* search using the lower bounds computed by the backward interval search as potential function. It is important to note that KaTCH performs the sample search for ALL witness searches. This is different from  where the sample search is only performed occasionally; namely depending on how many shortcuts are omitted and inserted/merged during the ordering process. - The profile search is performed in forward direction on the thinned corridor provided by the interval search. This is the same as in  but with the difference that the preceding interval search is a backward search instead of the forward search as said above. The only other modification is that the profile search runs in the manner of an A* search also using the lower bounds computed by the backward interval search as potential function, just like the sample search does before. 2. TCH-based EA Querying ------------------------ The querying is performed as Batz et al. (see Algorithm 4 in ) describe it but the stall-on-demand is different from the description in Section 5.4 of this article. The modifications are as follows: - Stalling is not propagated to further nodes. - Nodes are stalled by considering adjacent nodes higher up in the hierarchy as described in . However, stalling is performed not only based on the current label of these nodes but also on the stall weight. Assertions ========== Note that the source code of KaTCH contains lots of assertions that perform a lot checking. On the one hand, this increases reliability (but note that we give NO WARANTY). On the other hand, this means the assertions slow down KaTCH significantly. Compile, in case of g++, with option -DNDEBUG to get rid of this slow down. Also note that KaTCH makes intense use of double arithmetic which means rounding errors may occur. So, if an assertion fails due to rounding errors, for example during preprocessing, this does not necessarily mean that KaTCH does not work. In our experience the generated TCH structures can still be of very good quality (again, WITHOUT WARANTY). for the road network of Western Europe that we used in our experiments, for example, an assertion fails but the maximum error is below 1.0e-12%. So, if assertions fail, you should simply run the preprocessing with deactivated assertions and check experimentally how well the generated TCH structures work. File Formats ============ For input graphs KaTCH uses a text file format called TPGR. To store TCH structures it uses a binary format called BTCH. For massive testing KaTCH uses DEMAND files. All three formats are explained by the HTML files in the directory 'doc'. Relicensing =========== KaTCH is licensed under GNU AGPL version 3. If you need a commercial license, please contact the holder of the copyright Institut fuer Theroretische Informatik, Karlsruher Institut fuer Technology (KIT), 76131 Karlsruhe, Germany by writing an email to Prof. Peter Sanders <email@example.com>. Requirements ============ Libraries --------- - STL - OpenMP - BOOST strong typedef and pairing heap Language Version ---------------- C++11 Compiling and Running ===================== KaTCH contains two example .cpp files for running preprocessing and EA queries; namely examples/run_ordering.cpp examples/run_tch_ea_query.cpp To compiel them with g++ under Linux, for example, change to directory 'examples' and type, for example, > g++ -O3 -DNDEBUG -fopenmp -I.. -isystem<BOOST INCLUDE DIRECTORY> \ -std=c++11 -o <NAME OF BINARY> run_ordering.cpp replacing <BOOST INCLUDE DIRECTORY> and <NAME OF BINARY> appropriately, or analogously for 'examples/run_tch_ea_query.cpp'. Contact ======= Note that G. Veit Batz <firstname.lastname@example.org>, the author of KaTCH, no longer works at KIT. For relicensing, contact Prof. Peter Sanders <email@example.com> of KIT. References ==========  Gernot Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. "Minimum Time-Dependent Travel Times with Contraction Hierarchies", ACM Journal of Experimental Algorithmics, 18(1.4):1--43, 2013.