On Modelling and Solving the Shortest Path Problem with Evidential Weights

被引：3

作者：

Vu, Tuan-Anh ^{[1
]}

Afifi, Sohaib ^{[1
]}

Lefevre, Eric ^{[1
]}

Pichon, Frederic ^{[1
]}

机构：

[1] Univ Artois, UR 3926, Lab Genie Informat & Automat Artois LGI2A, F-62400 Bethune, France

来源：

BELIEF FUNCTIONS: THEORY AND APPLICATIONS (BELIEF 2022) | 2022年 / 13506卷

关键词：

Shortest path; Belief function; Exact method; VEHICLE-ROUTING PROBLEM; ALGORITHMS;

D O I：

10.1007/978-3-031-17801-6_14

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We study the single source single destination shortest path problem in a graph where information about arc weights is modelled by a belief function. We consider three common criteria to compare paths with respect to their weights in this setting: generalized Hurwicz, strong dominance and weak dominance. We show that in the particular case where the focal sets of the belief function are Cartesian products of intervals, finding best, i.e., non-dominated, paths according to these criteria amounts to solving known variants of the deterministic shortest path problem, for which exact resolution algorithms exist.

引用

页码：139 / 149

页数：11

共 15 条

[11] Improving and benchmarking of algorithms for Γ-maximin, Γ-maximax and interval dominance [J].

Nakharutai, Nawapon ;

Troffaes, Matthias C. M. ;

Caiado, Camila C. S. .

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 2021, 133 :95-115

[12]

Shafer G, 1976, MATH THEORY EVIDENCE

[13] An expectation operator for belief functions in the Dempster-Shafer theory* [J].

Shenoy, Prakash P. .

INTERNATIONAL JOURNAL OF GENERAL SYSTEMS, 2020, 49 (01) :112-141

[14] The Vehicle Routing Problem with Time Windows and Evidential Service and Travel Times: A Recourse Model [J].

Tedjini, Tekwa ;

Afifi, Sohaib ;

Pichon, Frederic ;

Lefevre, Eric .

SYMBOLIC AND QUANTITATIVE APPROACHES TO REASONING WITH UNCERTAINTY, ECSQARU 2021, 2021, 12897 :381-395

[15] On the robust shortest path problem [J].

Yu, G ;

Yang, J .

COMPUTERS & OPERATIONS RESEARCH, 1998, 25 (06) :457-468

← 1 2 →