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 条

[1] DETERMINING ALL OPTIMAL AND NEAR-OPTIMAL SOLUTIONS WHEN SOLVING SHORTEST-PATH PROBLEMS BY DYNAMIC-PROGRAMMING [J].

BYERS, TH ;

WATERMAN, MS .

OPERATIONS RESEARCH, 1984, 32 (06) :1381-1384

[2] Decision-making with belief functions: A review [J].

Denoeux, Thierry .

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 2019, 109 :87-110

[3] Shortest path problems with partial information:: Models and algorithms for detecting dominance [J].

Dias, LC ;

Clímaco, JN .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 121 (01) :16-31

[4]

Dijkstra E.W., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390

[5] An exact method for the biobjective shortest path problem for large-scale road networks [J].

Duque, Daniel ;

Lozano, Leonardo ;

Medaglia, Andres L. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 242 (03) :788-797

[6]

Guillaume R., 2021, P FUZZ IEEE 2021 IEE, P1

[7]

Hansen P., 1979, Multiple Criteria Decision Making Theory and Application, V177, P109, DOI DOI 10.1007/978-3-642-48782-8_9

[8] The capacitated vehicle routing problem with evidential demands [J].

Helal, Nathalie ;

Pichon, Frederic ;

Porumbel, Daniel ;

Mercier, David ;

Lefevre, Eric .

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 2018, 95 :124-151

[9] Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs [J].

Mihalak, Matus ;

Sramek, Rastislav ;

Widmayer, Peter .

THEORY OF COMPUTING SYSTEMS, 2016, 58 (01) :45-59

[10] An exact algorithm for the robust shortest path problem with interval data [J].

Montemanni, R ;

Gambardella, LM .

COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (10) :1667-1680

← 1 2 →