A LAGRANGEAN RELAXATION-BASED SOLUTION APPROACH FOR MULTICOMMODITY NETWORK DESIGN PROBLEM WITH CAPACITY VIOLATIONS

Authors : Levent Erişkin

Pages : 241-263

View : 12 | Download : 9

Publication Date : 2021-11-08

Article Type : Research

Abstract :Bu çalışmada, cezalandırıcı kısıtlara sahip çoklu mal şebeke problemi için Lagrangean gevşetmesi tabanlı iki farklı ayrıştırma yaklaşımı formüle edilmekte ve karşılaştırılmaktadır. Bu problemler kapasite kısıtlarının ilave bir ceza maliyeti ile ihlal edilebilediği kapasite kısıtlı çoklu mal şebeke problemlerinin farklı versiyonlarıdır. Bu maliyetler amaç fonksiyonuna doğrusal olmayan terimler olarak yansıtılmakta, bu kapsamda bu problemler doğrusal olmayan karışık tam sayılı eniyileme problemlerine dönüşmektedir. Bilgimiz dahilinde, bu tip problemlerin çözümü için herhangi bir kesin çözüm algoritması bulunmamaktadır. Bu problemler için iki farklı Lagrangean gevşetmesi tabanlı ayrıştırma teklif etmekte ve gradyant altı algoritması ile çözmekteyiz. Ortaya çıkan alt-problemler kolaylıkla çözülebilmekte ve önerilen algoritmalar CPLEX çözücünün herhangi bir çözüm bile bulamadığı durumlar için makul sonuçlar elde etmektedir. Çalışmada ayrıca bu iki gevşetmenin farklı performans metrikleri bazında karşılaştırmasının yapıldığı bir hesaplamalı analiz de yapmaktayız. Her ne kadar iki gevşetme de çözüm süresi ve iterasyon adedi açısından benzer performanslar gösterse de Gevşetme 1’nin istatistiksel olarak Gevşetme 2’den daha üstün olduğunu gözlemledik.
Keywords : Çoklu Mal Şebeke Dizayn Problemi, Lagrangean Gevşetmesi, Gradyan Altı Algoritması, Ayrıştırma