Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

List Of Pareto Optimal Solutions of a Biobjective Shortest Path Problem

,

DOI: http://dx.doi.org/10.15439/2023F3718

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 603–613 ()

Full text

Abstract. 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.

References

  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