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

共 50 条

[41] New Algorithms For Multi Objective Shortest Path Problem [J].

V. N. Sastry ;

T. N. Janakiraman ;

S. Ismail Mohideen .

OPSEARCH, 2003, 40 (4) :278-298

[42] A FACTORING APPROACH FOR THE STOCHASTIC SHORTEST-PATH PROBLEM [J].

HAYHURST, KJ ;

SHIER, DR .

OPERATIONS RESEARCH LETTERS, 1991, 10 (06) :329-334

[43] Sharing information for the all pairs shortest path problem [J].

Takaoka, Tadao .

THEORETICAL COMPUTER SCIENCE, 2014, 520 :43-50

[44] Fuzzy shortest path problem with finite fuzzy quantities [J].

Moazeni, S .

NAFIPS 2005 - 2005 Annual Meeting of the North American Fuzzy Information Processing Society, 2005, :664-669

[45] A combination of flow shop scheduling and the shortest path problem [J].

Nip, Kameng ;

Wang, Zhenbo ;

Nobibon, Fabrice Talla ;

Leus, Roel .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (01) :36-52

[46] A PARALLEL SHORTEST AUGMENTING PATH ALGORITHM FOR THE ASSIGNMENT PROBLEM [J].

BALAS, E ;

MILLER, D ;

PEKNY, J ;

TOTH, P .

JOURNAL OF THE ACM, 1991, 38 (04) :985-1004

[47] New reformulations of distributionally robust shortest path problem [J].

Cheng, Jianqiang ;

Leung, Janny ;

Lisser, Abdel .

COMPUTERS & OPERATIONS RESEARCH, 2016, 74 :196-204

[48] On Accuracy of Approximation for the Resource Constrained Shortest Path Problem [J].

Soldatenko, Aleksandr A. .

JOURNAL OF SIBERIAN FEDERAL UNIVERSITY-MATHEMATICS & PHYSICS, 2019, 12 (05) :621-627

[49] The Steiner bi-objective shortest path problem [J].

Ben Ticha, Hamza ;

Absi, Nabil ;

Feillet, Dominique ;

Quilliot, Alain .

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION, 2021, 9

[50] Improving Solutions of Shortest Path Problem with MGHS Algorithm [J].

Wang, Lei ;

Wang, Xin ;

Yi, Yufeng .

2016 8TH INTERNATIONAL CONFERENCE ON INTELLIGENT HUMAN-MACHINE SYSTEMS AND CYBERNETICS (IHMSC), VOL. 2, 2016, :152-155

← 1 2 3 4 5 →