A fast algorithm for optimally finding partially disjoint shortest paths

Longkun Guo, Yunyun Deng, Kewen Liao, Qiang He, Timos Sellis, Zheshan Hu

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-review

Abstract

The classical disjoint shortest path problem has recently recalled interests from researchers in the network planning and optimization community. However, the requirement of the shortest paths being completely vertex or edge disjoint might be too restrictive and demands much more resources in a network. Partially disjoint shortest paths, in which a bounded number of shared vertices or edges is allowed, balance between degree of disjointness and occupied network resources. In this paper, we consider the problem of finding k shortest paths which are edge disjoint but partially vertex disjoint. For a pair of distinct vertices in a network graph, the problem aims to optimally find k edge disjoint shortest paths among which at most a bounded number of vertices are shared by at least two paths. In particular, we present novel techniques for exactly solving the problem with a runtime that significantly improves the current best result. The proposed algorithm is also validated by computer experiments on both synthetic and real networks which demonstrate its superior efficiency of up to three orders of magnitude faster than the state of the art.

Original languageEnglish
Title of host publicationProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
EditorsJerome Lang
PublisherInternational Joint Conferences on Artificial Intelligence
Pages1456-1462
Number of pages7
Volume2018-July
ISBN (Electronic)9780999241127
DOIs
Publication statusPublished - Jul 2018
Event27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018

Conference

Conference27th International Joint Conference on Artificial Intelligence, IJCAI 2018
CountrySweden
CityStockholm
Period13/07/1819/07/18

Fingerprint

Planning
Experiments

Cite this

Guo, L., Deng, Y., Liao, K., He, Q., Sellis, T., & Hu, Z. (2018). A fast algorithm for optimally finding partially disjoint shortest paths. In J. Lang (Ed.), Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018 (Vol. 2018-July, pp. 1456-1462). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2018/202
Guo, Longkun ; Deng, Yunyun ; Liao, Kewen ; He, Qiang ; Sellis, Timos ; Hu, Zheshan. / A fast algorithm for optimally finding partially disjoint shortest paths. Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. editor / Jerome Lang. Vol. 2018-July International Joint Conferences on Artificial Intelligence, 2018. pp. 1456-1462
@inproceedings{9d5892888a574e499f767094da574fcd,
title = "A fast algorithm for optimally finding partially disjoint shortest paths",
abstract = "The classical disjoint shortest path problem has recently recalled interests from researchers in the network planning and optimization community. However, the requirement of the shortest paths being completely vertex or edge disjoint might be too restrictive and demands much more resources in a network. Partially disjoint shortest paths, in which a bounded number of shared vertices or edges is allowed, balance between degree of disjointness and occupied network resources. In this paper, we consider the problem of finding k shortest paths which are edge disjoint but partially vertex disjoint. For a pair of distinct vertices in a network graph, the problem aims to optimally find k edge disjoint shortest paths among which at most a bounded number of vertices are shared by at least two paths. In particular, we present novel techniques for exactly solving the problem with a runtime that significantly improves the current best result. The proposed algorithm is also validated by computer experiments on both synthetic and real networks which demonstrate its superior efficiency of up to three orders of magnitude faster than the state of the art.",
author = "Longkun Guo and Yunyun Deng and Kewen Liao and Qiang He and Timos Sellis and Zheshan Hu",
year = "2018",
month = "7",
doi = "10.24963/ijcai.2018/202",
language = "English",
volume = "2018-July",
pages = "1456--1462",
editor = "Jerome Lang",
booktitle = "Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018",
publisher = "International Joint Conferences on Artificial Intelligence",

}

Guo, L, Deng, Y, Liao, K, He, Q, Sellis, T & Hu, Z 2018, A fast algorithm for optimally finding partially disjoint shortest paths. in J Lang (ed.), Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. vol. 2018-July, International Joint Conferences on Artificial Intelligence, pp. 1456-1462, 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, Stockholm, Sweden, 13/07/18. https://doi.org/10.24963/ijcai.2018/202

A fast algorithm for optimally finding partially disjoint shortest paths. / Guo, Longkun; Deng, Yunyun; Liao, Kewen; He, Qiang; Sellis, Timos; Hu, Zheshan.

Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. ed. / Jerome Lang. Vol. 2018-July International Joint Conferences on Artificial Intelligence, 2018. p. 1456-1462.

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-review

TY - GEN

T1 - A fast algorithm for optimally finding partially disjoint shortest paths

AU - Guo, Longkun

AU - Deng, Yunyun

AU - Liao, Kewen

AU - He, Qiang

AU - Sellis, Timos

AU - Hu, Zheshan

PY - 2018/7

Y1 - 2018/7

N2 - The classical disjoint shortest path problem has recently recalled interests from researchers in the network planning and optimization community. However, the requirement of the shortest paths being completely vertex or edge disjoint might be too restrictive and demands much more resources in a network. Partially disjoint shortest paths, in which a bounded number of shared vertices or edges is allowed, balance between degree of disjointness and occupied network resources. In this paper, we consider the problem of finding k shortest paths which are edge disjoint but partially vertex disjoint. For a pair of distinct vertices in a network graph, the problem aims to optimally find k edge disjoint shortest paths among which at most a bounded number of vertices are shared by at least two paths. In particular, we present novel techniques for exactly solving the problem with a runtime that significantly improves the current best result. The proposed algorithm is also validated by computer experiments on both synthetic and real networks which demonstrate its superior efficiency of up to three orders of magnitude faster than the state of the art.

AB - The classical disjoint shortest path problem has recently recalled interests from researchers in the network planning and optimization community. However, the requirement of the shortest paths being completely vertex or edge disjoint might be too restrictive and demands much more resources in a network. Partially disjoint shortest paths, in which a bounded number of shared vertices or edges is allowed, balance between degree of disjointness and occupied network resources. In this paper, we consider the problem of finding k shortest paths which are edge disjoint but partially vertex disjoint. For a pair of distinct vertices in a network graph, the problem aims to optimally find k edge disjoint shortest paths among which at most a bounded number of vertices are shared by at least two paths. In particular, we present novel techniques for exactly solving the problem with a runtime that significantly improves the current best result. The proposed algorithm is also validated by computer experiments on both synthetic and real networks which demonstrate its superior efficiency of up to three orders of magnitude faster than the state of the art.

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

UR - https://www.ijcai.org/proceedings/2018/

U2 - 10.24963/ijcai.2018/202

DO - 10.24963/ijcai.2018/202

M3 - Conference Paper published in Proceedings

VL - 2018-July

SP - 1456

EP - 1462

BT - Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018

A2 - Lang, Jerome

PB - International Joint Conferences on Artificial Intelligence

ER -

Guo L, Deng Y, Liao K, He Q, Sellis T, Hu Z. A fast algorithm for optimally finding partially disjoint shortest paths. In Lang J, editor, Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. Vol. 2018-July. International Joint Conferences on Artificial Intelligence. 2018. p. 1456-1462 https://doi.org/10.24963/ijcai.2018/202