Standard

The algorithm for constrained shortest path problem based on incremental lagrangian dual solution. / Novikov, Boris; Guralnik, Roman.

Databases and Information Systems - 13th International Baltic Conference, DB and IS 2018, Proceedings. Springer Nature, 2018. p. 360-375 (Communications in Computer and Information Science; Vol. 838).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Novikov, B & Guralnik, R 2018, The algorithm for constrained shortest path problem based on incremental lagrangian dual solution. in Databases and Information Systems - 13th International Baltic Conference, DB and IS 2018, Proceedings. Communications in Computer and Information Science, vol. 838, Springer Nature, pp. 360-375, 13th International Baltic Conference on Databases and Information Systems, DB and IS 2018, Trakai, Lithuania, 1/07/18. https://doi.org/10.1007/978-3-319-97571-9_28

APA

Novikov, B., & Guralnik, R. (2018). The algorithm for constrained shortest path problem based on incremental lagrangian dual solution. In Databases and Information Systems - 13th International Baltic Conference, DB and IS 2018, Proceedings (pp. 360-375). (Communications in Computer and Information Science; Vol. 838). Springer Nature. https://doi.org/10.1007/978-3-319-97571-9_28

Vancouver

Novikov B, Guralnik R. The algorithm for constrained shortest path problem based on incremental lagrangian dual solution. In Databases and Information Systems - 13th International Baltic Conference, DB and IS 2018, Proceedings. Springer Nature. 2018. p. 360-375. (Communications in Computer and Information Science). https://doi.org/10.1007/978-3-319-97571-9_28

Author

Novikov, Boris ; Guralnik, Roman. / The algorithm for constrained shortest path problem based on incremental lagrangian dual solution. Databases and Information Systems - 13th International Baltic Conference, DB and IS 2018, Proceedings. Springer Nature, 2018. pp. 360-375 (Communications in Computer and Information Science).

BibTeX

@inproceedings{ca8593f786df4408b4ff756e2dd4b276,
title = "The algorithm for constrained shortest path problem based on incremental lagrangian dual solution",
abstract = "Most of the systems that rely on the solution of shortest path problem or constrained shortest demand real-time response to unexpected real world events that affect the input graph of the problem such as car accidents, road repair works or simply dense traffic. We developed new incremental algorithm that uses data already present in the system in order to quickly update a solution under new conditions. We conducted experiments on real data sets represented by road graphs of the cities of Oldenburg and San Joaquin. We test the algorithm against that of Muhandiramge and Boland [1] and show that it provides up to 50% decrease in computation time compared to solving the problem from scratch.",
keywords = "Constrained shortest path, Incremental, Road graphs",
author = "Boris Novikov and Roman Guralnik",
year = "2018",
month = aug,
day = "15",
doi = "10.1007/978-3-319-97571-9_28",
language = "English",
isbn = "9783319975702",
series = "Communications in Computer and Information Science",
publisher = "Springer Nature",
pages = "360--375",
booktitle = "Databases and Information Systems - 13th International Baltic Conference, DB and IS 2018, Proceedings",
address = "Germany",
note = "13th International Baltic Conference on Databases and Information Systems, DB and IS 2018 ; Conference date: 01-07-2018 Through 04-07-2018",

}

RIS

TY - GEN

T1 - The algorithm for constrained shortest path problem based on incremental lagrangian dual solution

AU - Novikov, Boris

AU - Guralnik, Roman

PY - 2018/8/15

Y1 - 2018/8/15

N2 - Most of the systems that rely on the solution of shortest path problem or constrained shortest demand real-time response to unexpected real world events that affect the input graph of the problem such as car accidents, road repair works or simply dense traffic. We developed new incremental algorithm that uses data already present in the system in order to quickly update a solution under new conditions. We conducted experiments on real data sets represented by road graphs of the cities of Oldenburg and San Joaquin. We test the algorithm against that of Muhandiramge and Boland [1] and show that it provides up to 50% decrease in computation time compared to solving the problem from scratch.

AB - Most of the systems that rely on the solution of shortest path problem or constrained shortest demand real-time response to unexpected real world events that affect the input graph of the problem such as car accidents, road repair works or simply dense traffic. We developed new incremental algorithm that uses data already present in the system in order to quickly update a solution under new conditions. We conducted experiments on real data sets represented by road graphs of the cities of Oldenburg and San Joaquin. We test the algorithm against that of Muhandiramge and Boland [1] and show that it provides up to 50% decrease in computation time compared to solving the problem from scratch.

KW - Constrained shortest path

KW - Incremental

KW - Road graphs

UR - http://www.scopus.com/inward/record.url?scp=85052903704&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-97571-9_28

DO - 10.1007/978-3-319-97571-9_28

M3 - Conference contribution

AN - SCOPUS:85052903704

SN - 9783319975702

T3 - Communications in Computer and Information Science

SP - 360

EP - 375

BT - Databases and Information Systems - 13th International Baltic Conference, DB and IS 2018, Proceedings

PB - Springer Nature

T2 - 13th International Baltic Conference on Databases and Information Systems, DB and IS 2018

Y2 - 1 July 2018 through 4 July 2018

ER -

ID: 34896090