Bicriteria Shortest Path Problem and an Application

Abstract

In this paper bicriteria shortest path problem, a specific case of shortest path problem, is studied. This problem can be seen frequently in real life, and there are methods that provides solution to the problem. Since the solution of the problem is a set of solution points, aforementioned methods need long computation times. Thus there exist heuristic solutions, which does not guarantee to find the complete set of solutions, but solve in a relatively shorter time compared to exact method, in the literature. In the paper we will explain both of the exact methods and heuristic methods and make an application to compare those solution methods.

Keywords

• shortest path
• bicriteria shortest path
• multicriteria shortest path
• Martins Algorithm
• Dijkstra's Algorithm
• labeling
• A* algorithms

İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI

Abstract

Bu çalışmada çok kriterli en kısa yol probleminin özel bir durumu olan iki kriterli en kısa yol problemi incelenmektedir. Gerçek hayatta sıkça karşılaşılan bu problem için literatürde birçok çözüm metodu önerilmiştir. Problemin çözümü tek bir sonuç değil bir çözüm kümesinden oluştuğu için bu metotlar uzun hesaplama ve işlem sürelerine sahiptir. Bu nedenle de literatürde çözüm kümesinin tamamını bulma garantisi olmasa da çok daha kısa sürede çözme kapasitesi olan sezgisel metotlar geliştirilmiştir. Bu çalışmada çözüm kümesinin tamamını veren metotlar ile sözü geçen sezgisel metotlar açıklanacak ve bu metotlar arasında karşılaştırma imkânı sunan bir uygulama yapılacaktır.

Keywords

• : En kısa yol problemi
• iki kriterli en kısa yol problemi
• çok kriterli en kısa yol problemi
• Dijsktra algoritması
• Martins algoritması
• etiketleme algoritmaları
• A* algoritmaları

References

1. Akçayol, M. A. & S. Toklu. “Genetic algorithm based a new algorithm for time dynamic shortest path problem.” Journal of the Faculty of Engineering and Architecture of Gazi University, December 2011.
2. Ahmadi, Saman & Tack Guido ; Harabor, Daniel ; Kilby, Philip, “Bi-Objective Search with Bi-Directional A*”, 29th Annual European Symposium on Algorithms, 2021.
3. Ahuja, R.K. T. L.& Magnanti & J. B. Orlin. Network Flows: MIT Working Paper No: 2059-88, Prentice Hall, 1988.
4. Arslan, H. & M. Manguoğlu. “A hybrid single-source shortest path algorithm”, Turkish Journal of Electric Engineering and Computer Sciences, 2019
5. Bellman, E. “On a Routing Problem”, Appl. Math., Vol 16, 87–90, 1958.
6. Brumbaugh-Smith, J Shier D. “An empirical investigation of some bicriterion-shortest path algorithms”. European Journal of Operational Research, 1989
7. Cheikh, Mohamed & Jarboui Bassem & Loukil Taicir. “A genetic algorithms to solve the bicriteria shortest path problem”, Electronic Notes in Discrete Mathematics, 2010.
8. Climaco, J.C.N. & E.Q.V. Martins. “A bicriterion shortest path algorithm” European Journal of Operational Research, 1982

9. Dantzig, G.B., “On the Shortest Route Through a Network”, Management Science, 187–190, 1960.
10. Dijkstra, E.W., “A Note on Two Problems in Connection with Graphs”, Numerische Mathematik, Vol 1, 269–271, 1959.
11. Ehrgott, M. Multicriteria Optimization 2nd edition, Springer , 2005
12. Floyd, R.W. “Algorithm 97: Shortest Path”, Communications of the ACM 5, 1962.
13. Ford, L.R. Jr. “Network Flow Theory, Paper P-923”, The RAND Corporation, Santa Monica, California, 1956.
14. Hansen, P. “Bicriterion Path Problems”, Multiple Criteria Decision Making Theory. e Springer- Verlag, Berlin 1980.
15. Hart, P. E. & N.J. Nilsson & B. Raphael. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics, 1968.
16. Mandow, L. & J.L. Pérez de la Cruz “Multiobjective A* search with consistent heuristics.” Journal of the ACM 57 (5), 2010.
17. Martins, E.Q.V., On a “Multicriteria Shortest Path Problem”, European Journal of Operational Research,1984.
18. Murthy, J. I. Mote & D.L. Olson. “A parametric approach to solving bicriterion shortest path problems”, European Journal of Operations Research 53, 1991.
19. Ning, Shi & Shaorui Zhou & Fan Wang & Yi Tao & Liming Liu. “The multi-criteria constrained shortest path problem”, Transportation Research Part E, 2017
20. Pulido, F.J. & J. L. Perez-de-la-Cruz & L. Mandow. “Dimensionality reduction in multiobjective shortest path search” Computers & Operations Research 64:60–70. , 2015.
21. Pulido, F.J. & J.L.Perez-de-la-Cruz & L.Mandow.“Multiobjective shortest path problems with lexicographic goal-based preferences”. European Journal of Operational Research 239, 2014.
22. Raith, Andrea & Matthias Ehrgott. “A comparison of solution strategies for biobjective shortest path problems”, Computers & Operations Research 36, 2009.
23. Schrijver A. “On the History of the Shortest Path Problem”, Documenta Mathematica, 2012.
24. Sedgewick, Robert & K. Wayne. Algorithms, Addison Wesley Publishing, 2014.
25. Serafini, P. (1986). “Some considerations about computational complexity for multi objective combinatorial problems.” Recent advances and historical development of vector optimization, volume Bibliograph of Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin.
26. Skriver, A. “A Classification of Bicriterion Shortest Path Algorithms”, Asia Pasific Journal of Operational Research , 2000a.
27. Skriver, A. & K. A. Andersen, “A Label Correction approach for solving bicriterion shortest-path problems”, Computers & Operations Research, 2000b
28. Stewart, B.S. & C.C. White. “Multiobjective A*”. Journal of the ACM 38 (4), 1991.
29. Tung, CT & K.L. KL. “A bicriterion Pareto-optimal path algorithm”. Asia-Pacific Journal of Operations Research, 1988.
30. Ulloa, C.H. & W. Yeohz & J. Baier & H. Zhang & L. Suazo & S. Koenig. “A Simple and Fast Bi-Objective Search Algorithm”, Association for the Advancement of Artificial Intelligence, 2020
31. Xiao-Bing, Hu & Chi Zhang Gong & Peng Zhang Ming & Kong Zhang & Hang Li & Mark S. Leeson& Jian-Qin Liao. “Finding the 𝑘 shortest paths by ripple-spreading algorithms Finding the 𝑘 shortest paths by ripple-spreading algorithms”, Artificial Intelligence, 2020.
32. https://en.wikipedia.org/wiki/Yen%27s_algorithm (erişim tarihi: 18.06.2021)
33. Shortest Path Data, Princeton University, “https://algs4.cs.princeton.edu/44sp/” (Erişim tarihi: 18.06.2021)
34. Dimacs (2005), Center for Discrete Mathematics and Theoretical Computer Science, “http://www.diag.uniroma1.it//~challenge9/download.shtml” (Erişim tarihi: 18.06.2021)