Heuristic methods for solving multicommodity network flow problems with discontinuous cost functions

Abstract

ÖZET Bu çalışmada incelenen problem, ölçek ekonomisi gösteren belirli bir grup süreksiz maliyet fonksiyonlu ayrıtlardan oluşan bir şebeke yapısı içerisinde tüm noktadan noktaya taleplerin yönlendirilme toplam maliyetinin en asa indirilmesidir. Bu problemi çözmek için üç adet sezgisel çözüm yöntemi geliştirilmiştir. Barılardan bir tanesi iyi bir başlangıç çözümü elde etmek için, diler ikisi ise daha sonraki iyileştirmeler için tasarlanmıştır. Bir iyileştirme tekniği dal landırıp-sınırlandıntıa yaklaşımına dayanan ağaç taraması çözüm yöntemidir ve bu yöntem çözümü makul bir zaman içerisinde elde etmek için bazı sezgisel yordamlarla hızlandırılmıştır. Görece kısa zamanda sona ermesi beklenen diğer iyileştirme tekniği başlatma çözüm yöntemini bazı sınırlar ve ayarlamalar eklenmiş haliyle kullanır. Bu çözüm yöntemleri için bilgisayar programları geliştirilmiş ve sayısal sonuçlar elde etmek iç m Örnek problemlerde kullanılmıştır.

IV ABSTRACT Problem examined in this study is the minimization of total cost for the routing of all point-to-point demands in a given networK structure whose arcs have associated with them, a certain family of discontinuous cost functions exhibiting economies of scale. Three heuristic algorithms are developed to solve this problem. One of there is devised for obtaining a better initial solution and the other two are for further improvements on the initial solution. One improvement technique is a tree search algorithm based on a branch and bound philosophy which is accelerated with some heuristic routines in order to obtain a solution in a reasonable time. The other improvement technique expected to terminate m a relatively short time uses the initialization algorithm with some additional bounds and adjustments. Computer programs for these algorithms are developed and used in the solution of example problems to obtain computational results.