Geodesic
Algorithm for optimal routing in multi-service networks
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 122-127.

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

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.
Keywords: resource constrained shortest path, big graph. 
@article{PDMA_2018_11_a37,
     author = {A. A. Soldatenko},
     title = {Algorithm for optimal routing in multi-service networks},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {122--127},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a37/}
}
TY  - JOUR
AU  - A. A. Soldatenko
TI  - Algorithm for optimal routing in multi-service networks
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 122
EP  - 127
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a37/
LA  - ru
ID  - PDMA_2018_11_a37
ER  - 
%0 Journal Article
%A A. A. Soldatenko
%T Algorithm for optimal routing in multi-service networks
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 122-127
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a37/
%G ru
%F PDMA_2018_11_a37
A. A. Soldatenko. Algorithm for optimal routing in multi-service networks. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 122-127. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a37/

[1] Van Mieghem P., Kuipers F. A., Korkmaz T., et al., “Quality of service routing”, LNCS, 2856, 2003, 80–117

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

[3] Dror M., “Note on the complexity of the shortest path models for column generation in VRPTW”, J. Operat. Res., 42 (1994), 977–978 | DOI | Zbl

[4] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp.

[5] 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

[6] Mehlhorn K., Ziegelmann M., “Resource constrained shortest paths”, LNCS, 1879, 2000, 326–337 | MR | Zbl

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

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

[9] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Knizhnyi dom “Librokom”, M., 2012, 390 pp. | MR

[10] Bykova V. V., Soldatenko A. A., “Optimalnaya marshrutizatsiya po orientiram v nestatsionarnykh setyakh”, Prikladnaya diskretnaya matematika, 2017, no. 37, 114–123

[11] Bykova V. V., Soldatenko A. A., “Adaptivnoe razmeschenie orientirov v zadache o kratchaishem puti dlya grafov bolshoi razmernosti”, Programmnye produkty i sistemy, 2016, no. 1, 60–67

[12] IBM ILOG CPLEX Optimizer Studio. CPLEX User's Manual, Version 12 Release 6, 2015