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 条

[1] An acceptability index based approach for solving shortest path problem on a network with interval weights
Ebrahimnejad, Ali
RAIRO - Operations Research, 2021, 55
[2] Solving the shortest path tour problem
Festa, P.
Guerriero, F.
Lagana, D.
Musmanno, R.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 230 (03) : 464 - 474
[3] An acceptability index based approach for solving shortest path problem on a network with interval weights
Ebrahimnejad, Ali
RAIRO-OPERATIONS RESEARCH, 2021, 55 : S1767 - S1787
[4] On Solving the Quadratic Shortest Path Problem
Hu, Hao
Sotirov, Renata
INFORMS JOURNAL ON COMPUTING, 2020, 32 (02) : 219 - 233
[5] Solving the Shortest Path Problem with QAOA
Fan, Zhiqiang
Xu, Jinchen
Shu, Guoqiang
Ding, Xiaodong
Lian, Hang
Shan, Zheng
SPIN, 2023, 13 (01)
[6] New algorithm for the shortest path problem with nonnegative weights
Zhang, Zhongzhen
Tang, Xiaowo
Dianzi Keji Daxue Xuebao/Journal of University of Electronic Science and Technology of China, 1995, 24 (05):
[7] A DNA procedure for solving the shortest path problem
Wang, Zhaocai
Xiao, Dongmei
Li, Wenxia
He, Lin
APPLIED MATHEMATICS AND COMPUTATION, 2006, 183 (01) : 79 - 84
[8] Solving a shortest path problem by ant algorithm
Fan, H
Hua, Z
Li, JJ
Yuan, D
PROCEEDINGS OF THE 2004 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-7, 2004, : 3174 - 3177
[9] Solving the shortest path problem with interval arcs
Sengupta A.
Pal T.K.
Fuzzy Optimization and Decision Making, 2006, 5 (1) : 71 - 89
[10] A New Algorithm for Solving Multicriteria Shortest Path Problem
MA Liang\ \ WANG Long\|de College of Systems Science and Systems Engineering
Journal of Systems Science and Systems Engineering, 1999, (03) : 335 - 339

← 1 2 3 4 5 →