Approximate algorithm for searching shortest path in multiservice network with constrained resource

In the paper, we consider the Resource Constrained Shortest Path problem (RCSP). This problem is NP-hard extension of a well-known shortest path problem in the directed graph G = (V, E). In the RCSP problem each arc e from E has a cost w(e) and additional weight functions r_i(e), i = 1,..., k, which specifying its requirements from a finite set of resource. The RCSP problem has various practical applications, including design and operation of multi-service network. Nowadays, multi-service networks grow at a rapid pace. Therefore, it is relevant to search for a new approximation algorithms that can solve the RCSP problem quickly. This paper reviews existing approximation algorithms for the RCSP problem. A polynomial time ^-approximation algorithm RevTree based on node labeling method is presented in the paper. The main advantage of the RevTree algorithm over existing ones is its ability to produce e approximation of the RCSP problem in O(|V|²) time. For real networks, e can be calculate using values of w(e) and r_i(e), e £ E. The paper provides a description of the RevTree algorithm and results of computational experiments, which justify the effectiveness of proposed algorithm.

Keywords

Authors

References