Algorithm for optimal routing in multi-service networks

The resource constrained shortest path problem (RCSP) is NP-hard extension of shortest path problem in the directed graph $G=(V,E)$. In RCSP problem, each arc $e\in E$ has a cost $w(e)$ and additional weight functions $w_r(e)$ which specify its requirements from a set of resource. Such problem allows to model a multi-service networks and search optimal route between two certain vertices. In this paper, we propose two heuristic algorithms for solving RCSP problem on big graphs. First algorithm is a modification of the famous Dijkstra's algorithm with additional labels, they allow to search the resource constrained shortest path. Unlike the known modifications, this modification does not require additional knowledge about the graph. Second algorithm adds potential functions and landmarks to the first. This modification accelerates algorithm on big graphs. Complexity of proposed algorithms corresponds to complexity of Dijkstra's algorithm. We provide computational experiments that show efficiency of proposed algorithms.