Algorithm for optimal routing in multiservice 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 E E has a cost w(e) and additional weight functions wr (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
big graph,
resource constrained shortest path,
графы большой размерности,
ресурсоограниченный кратчайший путьAuthors
| Soldatenko A. A. | Siberian Federal University | glinckon@gmail.com |
Всего: 1
References
IBM ILOG CPLEX Optimizer Studio. CPLEX User's Manual. Version 12 Release 6, 2015.
Быкова В. В., Солдатенко А. А. Адаптивное размещение ориентиров в задаче о кратчайшем пути для графов большой размерности // Программные продукты и системы. 2016. №1. С. 60-67.
Mehlhorn K. and Ziegelmann M. Resource constrained shortest paths // LNCS. 2000. V. 1879. P. 326-337.
Jepsen M., Petersen B., Spoorendonk S., and Pisinger D. A branch-and-cut algorithm for the capacitated profitable tour problem // J. Discr. Optimization. 2014. V. 14. P. 78-96.
Horvath M. and Kis T. Solving resource constrained shortest path problems with LP-based methods // J. Computers & Operat. Res. 2016. V. 73. P. 150-164.
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Книжный дом «Либроком», 2012. 390с.
Быкова В. В., Солдатенко А. А. Оптимальная маршрутизация по ориентирам в нестационарных сетях // Прикладная дискретная математика. 2017. №37. С. 114-123.
Dumitrescu I. and Boland N. Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem // J. Networks. 2003. V.42. P. 135-153.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416с.
Van Mieghem P., Kuipers F. A, Korkmaz T., et al. Quality of service routing // LNCS. 2003. V. 2856. P. 80-117.
Joksch H. C. The shortest route problem with constraints // J. Math. Analysis Appl. 1966. V.14. P. 191-197.
Dror M. Note on the complexity of the shortest path models for column generation in VRPTW // J. Operat. Res. 1994. V.42. P. 977-978.
