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

Özet

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.

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.

Anahtar kelimeler: : 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ı