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 条

[31] Analysis of algorithms for shortest path problem in parallel [J].

Popa, Bogdan ;

Popescu, Dan .

PROCEEDINGS OF THE 2016 17TH INTERNATIONAL CARPATHIAN CONTROL CONFERENCE (ICCC), 2016, :613-617

[32] Extended dominance and a stochastic shortest path problem [J].

Hutson, Kevin R. ;

Shier, Douglas R. .

COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (02) :584-596

[33] Scheduling Problem 1∥gi (Ci) as a Shortest Path Problem [J].

Paluch, Stanislav ;

Janosikova, Alzbeta ;

Ruzicka, Vendelin ;

Urbanicova, Ivana .

MATHEMATICAL METHODS IN ECONOMICS 2013, PTS I AND II, 2013, :685-691

[34] A new exact algorithm for the shortest path problem: An optimized shortest distance matrix [J].

Yuan, Huilin ;

Hu, Jianlu ;

Song, Yufan ;

Li, Yanke ;

Du, Jie .

COMPUTERS & INDUSTRIAL ENGINEERING, 2021, 158

[35] Solving shortest path problems with a weight constraint and replenishment arcs [J].

Smith, Olivia J. ;

Boland, Natashia ;

Waterer, Hamish .

COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (05) :964-984

[36] A PARAMETRIC APPROACH TO SOLVING BICRITERION SHORTEST-PATH PROBLEMS [J].

MOTE, J ;

MURTHY, I ;

OLSON, DL .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1991, 53 (01) :81-92

[37] On Solving the Shortest Basis Problem Based on Sequential Reduction [J].

Lyu, Shanxiang ;

Wang, Zheng ;

Liu, Ling .

IEEE COMMUNICATIONS LETTERS, 2021, 25 (05) :1515-1519

[38] A Reduced Uncertainty-Based Hybrid Evolutionary Algorithm for Solving Dynamic Shortest-Path Routing Problem [J].

Kusetogullari, Huseyin ;

Sharif, Md Haidar ;

Leeson, Mark S. ;

Celik, Turgay .

JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, 2015, 24 (05)

[39] Shortest Path Problem With Ordinary Differential Equations Constrained [J].

Azar, Ali Babapour ;

Nodeh, Zohreh Hosseini .

COMPUTATIONAL METHODS FOR DIFFERENTIAL EQUATIONS, 2020, 8 (04) :661-672

[40] Parallel Ant Colony Algorithm for Shortest Path Problem [J].

Katona, Geza ;

Lenart, Balazs ;

Juhasz, Janos .

PERIODICA POLYTECHNICA-CIVIL ENGINEERING, 2019, 63 (01) :243-254

← 1 2 3 4 5 →