Skip to content

C++ Alternative Routing Library for Boost.Graph. A configurable, efficient, plug-n-play solution for alternative route planning and k-shortest paths problems.

License

Notifications You must be signed in to change notification settings

leonardoarcari/arlib

Repository files navigation

ARLib - Alternative Routing Library for Boost.Graph

Branch Travis CI
master Build Status

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.

Features

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.

Requirements

Getting started

If you want to use this library, please check the following resources

Motivation

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.

References

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).