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 条
  • [21] Solving a Fuzzy Shortest Path Problem with Multiple Inputs and Outputs by using Data Envelopment Analysis
    Kordrostami, Sohrab
    Noveiri, Monireh Jahani Sayyad
    2013 13TH IRANIAN CONFERENCE ON FUZZY SYSTEMS (IFSC), 2013,
  • [22] Genetic Algorithm for Solving Fuzzy Shortest Path Problem in a Network with mixed fuzzy arc lengths
    Mahdavi, Iraj
    Tajdin, Ali
    Hassanzadeh, Reza
    Mandavi-Amiri, Nezam
    Shafieian, Hosna
    PROCEEDINGS OF THE FOURTH GLOBAL CONFERENCE ON POWER CONTROL AND OPTIMIZATION, 2011, 1337 : 265 - +
  • [23] Boosting of Existing Algorithms with Boundary Reduction for Shortest Path Problem
    Wei, Wei
    Yang, Weidong
    Xu, Heyang
    INFORMATICA-AN INTERNATIONAL JOURNAL OF COMPUTING AND INFORMATICS, 2021, 45 (07): : 31 - 44
  • [24] The k-Centrum Shortest Path Problem
    Garfinkel, Robert
    Fernandez, Elena
    Lowe, Timothy J.
    TOP, 2006, 14 (02) : 279 - 292
  • [25] Discussion on a Simplified Algorithm for the Shortest Path Problem
    Cuiyan
    Litong
    Renshupo
    2008 INTERNATIONAL WORKSHOP ON INFORMATION TECHNOLOGY AND SECURITY, 2008, : 66 - 69
  • [26] Applying Reinforcement Learning for Shortest Path Problem
    Sun, Zhixuan
    2022 INTERNATIONAL CONFERENCE ON BIG DATA, INFORMATION AND COMPUTER NETWORK (BDICN 2022), 2022, : 820 - 824
  • [27] On the shortest path problem with negative cost cycles
    Pugliese, Luigi Di Puglia
    Guerriero, Francesca
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2016, 63 (02) : 559 - 583
  • [28] Analysis of algorithms for shortest path problem in parallel
    Popa, Bogdan
    Popescu, Dan
    PROCEEDINGS OF THE 2016 17TH INTERNATIONAL CARPATHIAN CONTROL CONFERENCE (ICCC), 2016, : 613 - 617
  • [29] Improved artificial fish-swarm algorithm based on adaptive vision for solving the shortest path problem
    Ma, X.-M., 1600, Editorial Board of Journal on Communications (35): : 1 - 6
  • [30] Extended dominance and a stochastic shortest path problem
    Hutson, Kevin R.
    Shier, Douglas R.
    COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (02) : 584 - 596
12345