Research Article
BibTex RIS Cite

Bicriteria Shortest Path Problem and an Application

Year 2022, , 1373 - 1389, 31.12.2022
https://doi.org/10.56554/jtom.1075286

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.

References

  • 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.
  • Ahmadi, Saman & Tack Guido ; Harabor, Daniel ; Kilby, Philip, “Bi-Objective Search with Bi-Directional A*”, 29th Annual European Symposium on Algorithms, 2021.
  • Ahuja, R.K. T. L.& Magnanti & J. B. Orlin. Network Flows: MIT Working Paper No: 2059-88, Prentice Hall, 1988.
  • Arslan, H. & M. Manguoğlu. “A hybrid single-source shortest path algorithm”, Turkish Journal of Electric Engineering and Computer Sciences, 2019
  • Bellman, E. “On a Routing Problem”, Appl. Math., Vol 16, 87–90, 1958.
  • Brumbaugh-Smith, J Shier D. “An empirical investigation of some bicriterion-shortest path algorithms”. European Journal of Operational Research, 1989
  • Cheikh, Mohamed & Jarboui Bassem & Loukil Taicir. “A genetic algorithms to solve the bicriteria shortest path problem”, Electronic Notes in Discrete Mathematics, 2010.
  • Climaco, J.C.N. & E.Q.V. Martins. “A bicriterion shortest path algorithm” European Journal of Operational Research, 1982
  • Dantzig, G.B., “On the Shortest Route Through a Network”, Management Science, 187–190, 1960.
  • Dijkstra, E.W., “A Note on Two Problems in Connection with Graphs”, Numerische Mathematik, Vol 1, 269–271, 1959.
  • Ehrgott, M. Multicriteria Optimization 2nd edition, Springer , 2005
  • Floyd, R.W. “Algorithm 97: Shortest Path”, Communications of the ACM 5, 1962.
  • Ford, L.R. Jr. “Network Flow Theory, Paper P-923”, The RAND Corporation, Santa Monica, California, 1956.
  • Hansen, P. “Bicriterion Path Problems”, Multiple Criteria Decision Making Theory. e Springer- Verlag, Berlin 1980.
  • 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.
  • Mandow, L. & J.L. Pérez de la Cruz “Multiobjective A* search with consistent heuristics.” Journal of the ACM 57 (5), 2010.
  • Martins, E.Q.V., On a “Multicriteria Shortest Path Problem”, European Journal of Operational Research,1984.
  • Murthy, J. I. Mote & D.L. Olson. “A parametric approach to solving bicriterion shortest path problems”, European Journal of Operations Research 53, 1991.
  • Ning, Shi & Shaorui Zhou & Fan Wang & Yi Tao & Liming Liu. “The multi-criteria constrained shortest path problem”, Transportation Research Part E, 2017
  • 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.
  • 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.
  • Raith, Andrea & Matthias Ehrgott. “A comparison of solution strategies for biobjective shortest path problems”, Computers & Operations Research 36, 2009.
  • Schrijver A. “On the History of the Shortest Path Problem”, Documenta Mathematica, 2012.
  • Sedgewick, Robert & K. Wayne. Algorithms, Addison Wesley Publishing, 2014.
  • 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.
  • Skriver, A. “A Classification of Bicriterion Shortest Path Algorithms”, Asia Pasific Journal of Operational Research , 2000a.
  • Skriver, A. & K. A. Andersen, “A Label Correction approach for solving bicriterion shortest-path problems”, Computers & Operations Research, 2000b
  • Stewart, B.S. & C.C. White. “Multiobjective A*”. Journal of the ACM 38 (4), 1991.
  • Tung, CT & K.L. KL. “A bicriterion Pareto-optimal path algorithm”. Asia-Pacific Journal of Operations Research, 1988.
  • 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
  • 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.
  • https://en.wikipedia.org/wiki/Yen%27s_algorithm (erişim tarihi: 18.06.2021)
  • Shortest Path Data, Princeton University, “https://algs4.cs.princeton.edu/44sp/” (Erişim tarihi: 18.06.2021)
  • Dimacs (2005), Center for Discrete Mathematics and Theoretical Computer Science, “http://www.diag.uniroma1.it//~challenge9/download.shtml” (Erişim tarihi: 18.06.2021)

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

Year 2022, , 1373 - 1389, 31.12.2022
https://doi.org/10.56554/jtom.1075286

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.

References

  • 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.
  • Ahmadi, Saman & Tack Guido ; Harabor, Daniel ; Kilby, Philip, “Bi-Objective Search with Bi-Directional A*”, 29th Annual European Symposium on Algorithms, 2021.
  • Ahuja, R.K. T. L.& Magnanti & J. B. Orlin. Network Flows: MIT Working Paper No: 2059-88, Prentice Hall, 1988.
  • Arslan, H. & M. Manguoğlu. “A hybrid single-source shortest path algorithm”, Turkish Journal of Electric Engineering and Computer Sciences, 2019
  • Bellman, E. “On a Routing Problem”, Appl. Math., Vol 16, 87–90, 1958.
  • Brumbaugh-Smith, J Shier D. “An empirical investigation of some bicriterion-shortest path algorithms”. European Journal of Operational Research, 1989
  • Cheikh, Mohamed & Jarboui Bassem & Loukil Taicir. “A genetic algorithms to solve the bicriteria shortest path problem”, Electronic Notes in Discrete Mathematics, 2010.
  • Climaco, J.C.N. & E.Q.V. Martins. “A bicriterion shortest path algorithm” European Journal of Operational Research, 1982
  • Dantzig, G.B., “On the Shortest Route Through a Network”, Management Science, 187–190, 1960.
  • Dijkstra, E.W., “A Note on Two Problems in Connection with Graphs”, Numerische Mathematik, Vol 1, 269–271, 1959.
  • Ehrgott, M. Multicriteria Optimization 2nd edition, Springer , 2005
  • Floyd, R.W. “Algorithm 97: Shortest Path”, Communications of the ACM 5, 1962.
  • Ford, L.R. Jr. “Network Flow Theory, Paper P-923”, The RAND Corporation, Santa Monica, California, 1956.
  • Hansen, P. “Bicriterion Path Problems”, Multiple Criteria Decision Making Theory. e Springer- Verlag, Berlin 1980.
  • 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.
  • Mandow, L. & J.L. Pérez de la Cruz “Multiobjective A* search with consistent heuristics.” Journal of the ACM 57 (5), 2010.
  • Martins, E.Q.V., On a “Multicriteria Shortest Path Problem”, European Journal of Operational Research,1984.
  • Murthy, J. I. Mote & D.L. Olson. “A parametric approach to solving bicriterion shortest path problems”, European Journal of Operations Research 53, 1991.
  • Ning, Shi & Shaorui Zhou & Fan Wang & Yi Tao & Liming Liu. “The multi-criteria constrained shortest path problem”, Transportation Research Part E, 2017
  • 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.
  • 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.
  • Raith, Andrea & Matthias Ehrgott. “A comparison of solution strategies for biobjective shortest path problems”, Computers & Operations Research 36, 2009.
  • Schrijver A. “On the History of the Shortest Path Problem”, Documenta Mathematica, 2012.
  • Sedgewick, Robert & K. Wayne. Algorithms, Addison Wesley Publishing, 2014.
  • 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.
  • Skriver, A. “A Classification of Bicriterion Shortest Path Algorithms”, Asia Pasific Journal of Operational Research , 2000a.
  • Skriver, A. & K. A. Andersen, “A Label Correction approach for solving bicriterion shortest-path problems”, Computers & Operations Research, 2000b
  • Stewart, B.S. & C.C. White. “Multiobjective A*”. Journal of the ACM 38 (4), 1991.
  • Tung, CT & K.L. KL. “A bicriterion Pareto-optimal path algorithm”. Asia-Pacific Journal of Operations Research, 1988.
  • 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
  • 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.
  • https://en.wikipedia.org/wiki/Yen%27s_algorithm (erişim tarihi: 18.06.2021)
  • Shortest Path Data, Princeton University, “https://algs4.cs.princeton.edu/44sp/” (Erişim tarihi: 18.06.2021)
  • Dimacs (2005), Center for Discrete Mathematics and Theoretical Computer Science, “http://www.diag.uniroma1.it//~challenge9/download.shtml” (Erişim tarihi: 18.06.2021)
There are 34 citations in total.

Details

Primary Language Turkish
Subjects Industrial Engineering
Journal Section Research Article
Authors

Hakan Gürsoy 0000-0002-7759-1502

Ekrem Duman 0000-0001-5176-6186

Publication Date December 31, 2022
Submission Date February 18, 2022
Acceptance Date November 25, 2022
Published in Issue Year 2022

Cite

APA Gürsoy, H., & Duman, E. (2022). İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI. Journal of Turkish Operations Management, 6(2), 1373-1389. https://doi.org/10.56554/jtom.1075286
AMA Gürsoy H, Duman E. İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI. JTOM. December 2022;6(2):1373-1389. doi:10.56554/jtom.1075286
Chicago Gürsoy, Hakan, and Ekrem Duman. “İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI”. Journal of Turkish Operations Management 6, no. 2 (December 2022): 1373-89. https://doi.org/10.56554/jtom.1075286.
EndNote Gürsoy H, Duman E (December 1, 2022) İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI. Journal of Turkish Operations Management 6 2 1373–1389.
IEEE H. Gürsoy and E. Duman, “İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI”, JTOM, vol. 6, no. 2, pp. 1373–1389, 2022, doi: 10.56554/jtom.1075286.
ISNAD Gürsoy, Hakan - Duman, Ekrem. “İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI”. Journal of Turkish Operations Management 6/2 (December 2022), 1373-1389. https://doi.org/10.56554/jtom.1075286.
JAMA Gürsoy H, Duman E. İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI. JTOM. 2022;6:1373–1389.
MLA Gürsoy, Hakan and Ekrem Duman. “İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI”. Journal of Turkish Operations Management, vol. 6, no. 2, 2022, pp. 1373-89, doi:10.56554/jtom.1075286.
Vancouver Gürsoy H, Duman E. İKİ KRİTERLİ EN KISA YOL PROBLEMİ VE BİR UYGULAMASI. JTOM. 2022;6(2):1373-89.

2229319697  logo   logo-minik.png 200311739617396