Zusammenfassung
We investigate the single-criterion and multiobjective near-shortest paths problem. We present an algorithm to compute the set of near-shortest paths between two prespecified nodes while visiting a finite number of intermediate nodes in a given order. We show that the amount of work per path enumerated as well as the space complexity is polynomially bounded. Further, we extend the single-criterion near-shortest paths problem to the multiobjective case and show limitations.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Literatur
[1] G. Gallo, S. Pallottino, Shortest path algorithms, Annals of operations research 13 (1) (1988) 1–79.
[2] B. V. Cherkassky, A. V. Goldberg, T. Radzik, Shortest paths algorithms: Theory and experimental evaluation, Mathematical programming 73 (2) (1996) 129–174.
[3] S. E. Dreyfus, An appraisal of some shortest-path algorithms, Operations research 17 (3) (1969) 395–412.
[4] A. Artmeier, J. Haselmayr, M. Leucker, M. Sachenbacher, The shortest path problem revisited: Optimal routing for electric vehicles, in: Annual Conference on Artificial Intelligence, Springer, 2010, pp. 309–316.
[5] M. S. Waterman, T. H. Byers, A dynamic programming algorithm to find all solutions in a neighborhood of the optimum, Mathematical Biosciences 77 (1-2) (1985) 179–188.
[6] D. Eppstein, Finding the k shortest paths, SIAM Journal on computing 28 (2) (1998) 652–673.
[7] E. Hadjiconstantinou, N. Christofides, An efficient implementation of an algorithm for finding k shortest simple paths, Networks 34 (2) (1999) 88–101.
[8] J. Y. Yen, Finding the k shortest loopless paths in a network, management Science 17 (11) (1971) 712–716.
[9] T. H. Byers, M. S. Waterman, Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming, Operations Research 32 (6) (1984) 1381–1384.
[10] W. Matthew Carlyle, R. Kevin Wood, Near-shortest and k-shortest simple paths, Networks 46 (2) (2005) 98–109.
[11] A. Raith, M. Ehrgott, A comparison of solution strategies for biobjective shortest path problems, Computers & Operations Research 36 (4) (2009) 1299–1331.
[12] A. J. Skriver, K. A. Andersen, A label correcting approach for solving bicriterion shortest-path problems, Computers & Operations Research 27 (6) (2000) 507–524.
[13] C. T. Tung, K. L. Chew, A multicriteria pareto-optimal path algorithm, European Journal of Operational Research 62 (2) (1992) 203–209.
[14] E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische mathematik 1 (1) (1959) 269–271.
[15] R. K. Ahuja, Network flows: theory, algorithms, and applications, Pearson Education, 2017.
[16] M. L. Fredman, R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM) 34 (3) (1987) 596–615.
[17] M. Ehrgott, Multicriteria optimization, Vol. 491, Springer Science & Business Media, 2005.
[18] A. Schrijver, Combinatorial optimization: polyhedra and efficiency, Vol. 24, Springer Science & Business Media, 2003.
[19] A. J. Skriver, A classification of bicriterion shortest path (bsp) algorithms, Asia-Pacific Journal of Operational Research 17 (2) (2000) 199.
[20] A. Raith, M. Ehrgott, A comparison of solution strategies for biobjective shortest path problems, Computers & Operations Research 36 (4) (2009) 1299–1331.
[21] M. Ehrgott, X. Gandibleux, A survey and annotated bibliography of multiobjective combinatorial optimization, OR-Spektrum 22 (4) (2000) 425–460.
[22] M. Ehrgott, Approximation algorithms for combinatorial multicriteria optimization problems, International Transactions in Operational Research 7 (1) (2000) 5–31.
[23] V. Emelichev, V. Perepelitsa, Complexity of discrete multicriteria problems, Discrete Mathematics and Applications 4 (2) (1994) 89–118.
[24] P. Serafini, Some considerations about computational complexity for multi objective combinatorial problems, in: Recent advances and historical development of vector optimization, Springer, 1987, pp. 222–232.
[25] P. Hansen, Bicriterion path problems, in: Multiple criteria decision making theory and application, Springer, 1980, pp. 109–127.
[26] M. Müller-Hannemann, K. Weihe, On the cardinality of the pareto set in bicriteria shortest path problems, Annals of Operations Research 147 (1) (2006) 269–286.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer Nature
About this chapter
Cite this chapter
Schäfer, L.E., Ruzika, S. (2019). On Variants of the Single-criterion and Multiobjective Near-Shortest Paths Problem. In: Küfer, KH., Ruzika, S., Halffmann, P. (eds) Multikriterielle Optimierung und Entscheidungsunterstützung. Springer Gabler, Wiesbaden. https://doi.org/10.1007/978-3-658-27041-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-658-27041-4_2
Published:
Publisher Name: Springer Gabler, Wiesbaden
Print ISBN: 978-3-658-27040-7
Online ISBN: 978-3-658-27041-4
eBook Packages: Business and Economics (German Language)