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

A. A. Soldatenko

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 186-191

Résumé

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, \dots, 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 $\varepsilon$-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 $\varepsilon$ approximation of the RCSP problem in $\mathcal{O}(\mathopen|V\mathclose|^2)$ time. For real networks, $\varepsilon$ can be calculate using values of $w(e)$ and $r_i(e)$, $e \in E$. The paper provides a description of the RevTree algorithm and results of computational experiments, which justify the effectiveness of proposed algorithm.

Détail

Keywords: resource constrained shortest path, graph-based algorithm, optimal routing, computer and multi-service networks.