K shortest path problem together with arc tolerances

Abstract

ÖZET K EN KİSA YOL PROBLEMİ ¥E ARK TOLERANSLARI Mi N HESAPLANMASI YİLMAZ, Hakan Yüksele Lisans Tezi, End. Müh. Bölümü Tez Yöneticisi: Dec.ûr. Canan SEPİL Mayıs 1990 Bu makalede, doğrultusuz, ark uzunlukları pozitif olan şebekelerde başlangıç ve bitiş noktalan arasındaki döngüsüz K en kısa yolu etkili bir şekilde bulan ve Katoh tarafından geliştirilen yöntem ile birlikte K inci çözümün optimalitesini bozmadan ark uzunluklarında mümkün olan en büyük artış ve en büyük azalışları karakterize eden bir yöntem açıklanmaktadır. Bu toleransların K en kısa yol için hesaplanması, mevcut yollardan hangilerinin sistemde mevcut olan ve/veya eklenen kısıtlayıcıları karşıladığı ve optimal kaldığı hususunda karar verilmesinde esneklik sağlar. Katoh tarafından geliştirilen K en kısa yol yönteminin önemi m ve n sırasıyla toplam ark ve düğüm sayıları olmak üzere, bilgisayar zamanı açısından diğer yöntemlerden daha iyi olmasıdır. Bu makalede önce K en kısa yol problemi ve ark toleranslarının hesaplanmasında mevcut olan yöntemler gözden geçirilmiştir. bunu, Katoh'un geliştirdiği yöntem, kompleksitesi 0<Kn2>, izlemektedir. Son olarak, K en kısa yolların herbirinde ark toleranslarını bulmak için geliştirilen ve `cycle tracing` yönteminin bir devamı olan yeni metot açıklanmaktadır.

ABSTRACT K LOO PL ESS SHORTEST PATHS TOGETHER WITH ARC TOLERANCES YILMAZ, Hakan M.S. in Industrial Engineering, Supervisor: Assoc. Prof. Canon SEPİL May 1990, This paper works 88 an efficient algorithm for finding K shortest loopless paths between two specified nodes of an undirected graph G having nonnegative arc lengths and characterizes the ranges of maximum increase and decrease in the arc lengths that can be tolerated without changing the optimally of the Kth solution. Calculating arc tolerances for K shortest paths provides flexibility fn deciding ybtcti of the K shortest paths satisfy the imposed constraints and stay optimal. The significance of the algorithm developed by Katoh is that, letting n and rn as the number of nodes and arcs in G respectively, it is better than those realized by the other algorithms i n terms of its runni ng ti me. This paper first reviews the existing algorithms for finding K shortest paths together with the several algorithms for calculating all arc tolerances. This is followed by the presentation of Katoh's algorithm which is proved to be O(KN^) in terms of time complexity in the worst case. Finally, the new method which is an extension of `cycle tracing` algorithm for finding all the arc tolerances in all K paths is combined with this method in an example problem to show how it works. Key w.ords: K shortest loopless paths, sensitivity analysis m