List Of Pareto Optimal Solutions of a Biobjective Shortest Path Problem

• Autorzy: Laskov Lasko , Marinov Marin

Identyfikatory

DOI

10.15439/2023F3718

• Języki publikacji: EN

Abstrakty

EN

Many applications in practice involve the search for a shortest path in a network by optimizing two conflicting objective functions. Such problems often are referred to as biobjective optimization problems. Their goal is to find special optimal paths that are nondominated and are also known in the specialized literature as to as Pareto optimal. While most of the existing methods aim to find the minimum complete set of Pareto optimal paths, we propose an approach that is able to generate a list of all Pareto optimal solutions in a given network.

Słowa kluczowe

EN

shortest path problem; computer science; pareto optimization; linear programming; search problems; computational complexity; optimization

PL

problem najkrótszej ścieżki; informatyka; optymalizacja pareto; programowanie liniowe; problemy wyszukiwawcze; złożoność obliczeniowa; optymalizacja

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 603--613
• Opis fizyczny: Bibliogr. 20 poz., rys., wz.

Twórcy

autor

Laskov Lasko

• Informatics Department New Bulgarian University 21 Montevideo Str., 1618 Sofia, Bulgaria

• https://orcid.org/0000-0003-1833-8184

autor

Marinov Marin

• Informatics Department New Bulgarian University 21 Montevideo Str., 1618 Sofia, Bulgaria

• https://orcid.org/0009-0003-9544-819X

Bibliografia

• 1. R. Beier, H. Röglin, C. Rösner, and B. Vöcking, “The smoothed number of pareto-optimal solutions in bicriteria integer optimization,” Mathematical Programming, vol. 200, pp. 319–355, September 2022. http://dx.doi.org/10.1007/s10107-022-01885-6
• 2. J. C. Namorado Climaco and E. Queirós Vieira Martins, “A bicriterion shortest path algorithm,” European Journal of Operational Research, vol. 11, no. 4, pp. 399–404, 1982. http://dx.doi.org/10.1016/0377-2217(82)90205-3
• 3. P. Hansen, “Bicriterion path problems,” Multiple Criteria Decision Making Theory and Application, pp. 109–127, 1980. http://dx.doi.org/10.1016/S1097-2765(03)00225-9
• 4. X. Gandibleux, F. Beugnies, and S. Randriamasy, “Martins’ algorithm revisited for multi-objective shortest path problems with a maxmin cost function,” 4OR, vol. 4, no. 1, pp. 47–59, 2006. http://dx.doi.org/10.1007/s10288-005-0074-x
• 5. E. Q. V. Martins, “On a multicriteria shortest path problem,” European Journal of Operational Research, vol. 16, no. 2, pp. 236–245, 1984. http://dx.doi.org/10.1016/0377-2217(84)90077-8
• 6. J. Brumbaugh-Smith and D. Shier, “An empirical investigation of some bicriterion shortest path algorithms,” European Journal of Operational Research, vol. 43, no. 2, pp. 216–224, 1989. http://dx.doi.org/10.1016/0377-2217(89)90215-4
• 7. A. Skriver and K. Andersen, “A label correcting approach for solving bicriterion shortest-path problems,” Computers & Operations Research, vol. 27, no. 6, pp. 507–524, 2000. http://dx.doi.org/10.1016/S0305-0548(99)00037-4
• 8. A. Sedeño-noda and M. Colebrook, “A biobjective dijkstra algorithm,” European Journal of Operational Research, vol. 276, no. 1, pp. 106–118, 2019. http://dx.doi.org/10.1016/j.ejor.2019.01.007
• 9. M. Minoux, “Solving combinatorial problems with combined minmax-min-sum objective and applications,” Mathematical Programming, vol. 45, no. 1-3, pp. 361–372, 1989. http://dx.doi.org/10.1007/bf01589111
• 10. A. P. Punnen, “On combined minmax-minsum optimization,” Computers & Operations Research, vol. 21, no. 6, pp. 707–716, 1994. http://dx.doi.org/10.1016/0305-0548(94)90084-1
• 11. P. Dell’Olmo, M. Gentili, and A. Scozzari, “On finding dissimilar pareto-optimal paths,” European Journal of Operational Research, vol. 162, no. 1, pp. 70–82, 2005. http://dx.doi.org/10.1016/j.ejor.2003.10.033
• 12. F. Guerriero and R. Musmanno, “Label correcting methods to solve multicriteria shortest path problems,” Journal of Optimization Theory and Applications, vol. 111, no. 3, pp. 589–613, 2001. http://dx.doi.org/10.1023/A:1012602011914
• 13. C. Mohamed, J. Bassem, and L. Taicir, “A genetic algorithms to solve the bicriteria shortest path problem,” Electronic Notes in Discrete Mathematics, vol. 4, no. 1, pp. 851–858, 2010. http://dx.doi.org/10.1016/j.endm.2010.05.108
• 14. S. Fidanova, M. Ganzha, and O. Roeva, “Intercriteria analyzis of hybrid ant colony optimization algorithm for multiple knapsack problem,” in 2021 16th Conference on Computer Science and Intelligence Systems (FedCSIS), 2021. http://dx.doi.org/10.15439/2021F22 pp. 173–180.
• 15. A. Cassia, O. Jabali, F. Malucelli, and M. Pascoal, “The electric vehicle shortest path problem with time windows and prize collection,” in 2022 17th Conference on Computer Science and Intelligence Systems (FedCSIS), 2022. http://dx.doi.org/10.15439/2022F186 pp. 313–322.
• 16. E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959. http://dx.doi.org/10.1007/bf01386390
• 17. R. Diestel, Graph Theory, 5th ed. Berlin: Springer Publishing Company, Incorporated, 2017. ISBN 3662536218. http://dx.doi.org/10.1007/978-3-662-53622-3
• 18. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, 3rd ed. Cambridge, Massachusetts: The MIT Press, 2009. http://dx.doi.org/10.5555/1614191
• 19. M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” Journal of the ACM, vol. 34, no. 3, pp. 596–615, July 1987. http://dx.doi.org/10.1145/28869.28874
• 20. M. Müller-Hannemann and K. Weihe, “Pareto shortest paths is often feasible in practice,” Algorithm Engineering, pp. 185–197, 2001. http://dx.doi.org/10.1007/3-540-44688-5_15

Uwagi

1. Thematic Tracks Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).