Geodesic
Approximate algorithm for searching shortest path in multiservice network with constrained resource
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 186-191.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: resource constrained shortest path, graph-based algorithm, optimal routing, computer and multi-service networks. 
@article{PDMA_2019_12_a51,
     author = {A. A. Soldatenko},
     title = {Approximate algorithm for searching shortest path in multiservice network with constrained resource},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {186--191},
     publisher = {mathdoc},
     number = {12},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a51/}
}
TY  - JOUR
AU  - A. A. Soldatenko
TI  - Approximate algorithm for searching shortest path in multiservice network with constrained resource
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 186
EP  - 191
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a51/
LA  - ru
ID  - PDMA_2019_12_a51
ER  - 
%0 Journal Article
%A A. A. Soldatenko
%T Approximate algorithm for searching shortest path in multiservice network with constrained resource
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 186-191
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a51/
%G ru
%F PDMA_2019_12_a51
A. A. Soldatenko. Approximate algorithm for searching shortest path in multiservice network with constrained resource. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 186-191. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a51/

[1] Joksch H. C., “The shortest route problem with constraints”, J. Math. Analysis Appl., 14 (1966), 191–197 | DOI | MR | Zbl

[2] Di Puglia Pugliese L., Guerriero F., “A survey of resource constrained shortest path-problems: exact solution approaches”, J. Networks., 62:3 (2013), 183–200 | DOI | MR | Zbl

[3] Zhu X., Wilhelm W. E., “A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation”, J. Computers Operations Research, 39:2 (2012), 164–178 | DOI | MR | Zbl

[4] Dumitrescu I., Boland N., “Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem”, J. Networks, 42 (2003), 135–153 | DOI | MR | Zbl

[5] Jepsen M., Petersen B., Spoorendonk S., Pisinger D., “A branch-and-cut algorithm for the capacitated profitable tour problem”, J. Discrete Optimization, 14 (2014), 78–96 | DOI | MR | Zbl

[6] Horvath M., Kis T., “Solving resource constrained shortest path problems with LP-based methods”, J. Computers Operations Research, 73 (2016), 150–164 | DOI | MR | Zbl

[7] Soldatenko A. A., “Algoritm optimalnoi marshrutizatsii v multiservisnykh telekommunikatsionnykh setyakh”, Prikladnaya diskretnaya matematika. Prilozhenie, 2018, no. 11, 122–127

[8] Kormen T. Kh., Leizerson Ch. I., Rivest R. L., Shtain K., Algoritmy. Postroenie i analiz, Vilyams, M., 2018, 1328 pp.

[9] IBM ILOG CPLEX Optimizer Studio. CPLEX User's Manual. Version 12 Release 6, IBM Corp., 2015 https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.studio.help/pdf/usrcplex.pdf

[10] Pathan A. K., Monowar M. M., Khan S., Simulation Technologies in Networking and Communications: Selecting the Best Tool for the Test, CRC Press, 2017, 648 pp.