On the Top-k Shortest Paths with Dissimilarity Constraints

EasyChair Preprint 2568

Abstract

The problem of finding the k-shortest (simple) paths between a pair of nodes is a fundamental problem in graph theory, which is used in various kinds of applications in road networks, transportation networks, communication networks, etc.

Here, we study variants of this problem in which the reported paths must satisfy a pairwise threshold of dissimilarity. More precisely, we study the problem of finding k-shortest dissimilar paths (paths with similarity bounded by a threshold theta) with different variants and with different similarity measure.  We prove this problem to be NP-Complete for every similarity measure and we also prove the NP-Completeness of the problem even if a part of the solution is already given. Finally, we present several algorithms / methods that can solve the described problem in a reasonable time (using dynamic programming, enumeration methods and integer linear programming ILP).

Keyphrases: dissimilar path, k-shortest simple path, multi-objective optimization, transportation networks

@booklet{EasyChair:2568,
  author    = {Ali Al Zoobi and David Coudert and Nicolas Nisse},
  title     = {On the Top-k Shortest Paths with Dissimilarity Constraints},
  howpublished = {EasyChair Preprint 2568},
  year      = {EasyChair, 2020}}