| Branch | Travis CI |
|---|---|
| master |  |
ARLib is a generic library for Boost.Graph providing several Alternative Routing algorithms. Alternative routing, also known in the literature as alternative route planning or k-shortest paths with limited overlapping, is the problem of finding a number of good s-t paths in a graph. While the problem of finding the shortest path between a pair of nodes has been intensively studied and efficient solutions are well-known (most notably the Dijkstra's algorithm), finding several, high-quality paths introduces some challenges. In fact, we look for s-t paths that are (a) as short as possible (b) sufficiently dissimilar from each other.
ARLib implements the following state-of-the-art algorithms to solve the problem:
Moreover, the following algorithms are also available:
- Bidirectional Dijkstra - A speed-up variant of Dijkstra's algorithm that searches the graph both from the source and the target for faster convergence.
- Uninformed Bidirectional Pruner - A pre-processing algorithm to prune a graph from those vertices that unlikely could be part of an s-t path.
- A C++17 compliant compiler
- CMake (>= 3.5)
- Boost::Graph (>= 1.65)
If you want to use this library, please check the following resources
In the context of software frameworks for managing and operating on graphs, Boost.Graph library (BGL) is an established solution, known for providing a high-quality, high-performance implementation of graph structures and algorithms operating on them. Moreover, the generic interface that the library provides, along with its permissive license, makes BGL a valuable choice for the development of software systems that leverage graphs.
The purpose of ARLib is to provide a set of algorithms that solve the alternative routing problem for systems using BGL, for which an open source, high-performance C++ implementation is, as of now, missing. In the interest of preserving the generality of usage of BGL, ARLib follows the same conventions that official BGL algorithms set, so that ARLib users will find executing alternative routing algorithms on their graphs natural and non-intrusive.
The algorithm provided in this library are implementations of algorithms described in these scientific papers:
| Algorithm | Paper |
|---|---|
| OnePass+ | Theodoros Chondrogiannis, Panagiotis Bouros, Johann Gamper and UlfLeser, Exact and Approximate Algorithms for Finding k-Shortest Paths with Limited Overlap , In Proc. of the 20th Int. Conf. on Extending Database Technology (EDBT) (2017) |
| ESX | Same as above |
| Penalty | Yanyan Chen, Michael GH Bell, and Klaus Bogenberger. Reliable pretrip multipath planning and dynamic adaptation for a centralized road navigation system. Intelligent Transportation Systems, IEEE Transactions on, 8(1):14–20, 2007 |
| Bidirectional Dijkstra | Nicholson, T. Alastair J. "Finding the shortest route between two points in a network." The computer journal 9.3 (1966): 275-280. |
| Uninformed Bidirectional Pruner | Andreas Paraskevopoulos, Christos Zaroliagis. Improved Alternative Route Planning. Daniele Frigioni and Sebastian Stiller. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 33, pp.108–122, 2013, OpenAccess Series in Informatics (OASIcs). |