Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Byers, T.H., Waterman, M.S.: Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming. Oper. Res. 32(6), 1381–1384 (1984)
Denoeux, T.: Decision-making with belief functions: a review. Int. J. Approx. Reason. 109, 87–110 (2019)
Dias, L.C., Clímaco, J.N.: Shortest path problems with partial information: models and algorithms for detecting dominance. Eur. J. Oper. Res. 121(1), 16–31 (2000)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Duque, D., Lozano, L., Medaglia, A.L.: An exact method for the biobjective shortest path problem for large-scale road networks. Eur. J. Oper. Res. 242(3), 788–797 (2015)
Guillaume, R., Kasperski, A., Zieliński, P.: Robust optimization with scenarios using random fuzzy sets. In: Proceedings of FUZZ-IEEE 2021, pp. 1–6. IEEE (2021)
Hansen, P.: Bicriterion path problems. In: Fandel, G., Gal, T. (eds.) Multiple Criteria Decision Making Theory and Application. Lecture Notes in Economics and Mathematical Systems, vol. 177, pp. 109–127. Springer, Berlin, Heidelberg (1980). https://doi.org/10.1007/978-3-642-48782-8_9
Helal, N., Pichon, F., Porumbel, D., Mercier, D., Lefèvre, E.: The capacitated vehicle routing problem with evidential demands. Int. J. Approx. Reason. 95, 124–151 (2018)
Mihalák, M., Srámek, R., Widmayer, P.: Approximately counting approximately-shortest paths in directed acyclic graphs. Theory Comput. Syst. 58(1), 45–59 (2016)
Montemanni, R., Gambardella, L.M.: An exact algorithm for the robust shortest path problem with interval data. Comput. Oper. Res. 31(10), 1667–1680 (2004)
Nakharutai, N., Troffaes, M.C.M., Caiado, C.C.S.: Improving and benchmarking of algorithms for \(\gamma \)-maximin, \(\gamma \)-maximax and interval dominance. Int. J. Approx. Reason. 133, 95–115 (2021)
Shafer, G.: A Mathematical Theory of Evidence. Princeton University Press, Princeton (1976)
Shenoy, P.P.: An expectation operator for belief functions in the Dempster-Shafer theory. Int. J. Gen Syst 49(1), 112–141 (2020)
Tedjini, T., Afifi, S., Pichon, F., Lefèvre, E.: The vehicle routing problem with time windows and evidential service and travel times: a recourse model. In: Vejnarová, J., Wilson, N. (eds.) ECSQARU 2021. LNCS (LNAI), vol. 12897, pp. 381–395. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-86772-0_28
Yu, G., Yang, J.: On the robust shortest path problem. Comput. Oper. Res. 25(6), 457–468 (1998)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Vu, TA., Afifi, S., Lefèvre, É., Pichon, F. (2022). On Modelling and Solving the Shortest Path Problem with Evidential Weights. In: Le Hégarat-Mascle, S., Bloch, I., Aldea, E. (eds) Belief Functions: Theory and Applications. BELIEF 2022. Lecture Notes in Computer Science(), vol 13506. Springer, Cham. https://doi.org/10.1007/978-3-031-17801-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-17801-6_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-17800-9
Online ISBN: 978-3-031-17801-6
eBook Packages: Computer ScienceComputer Science (R0)