An adaptive tabu-simulated annealing for concave cost transportation problems
Küçük Resim Yok
Tarih
2008
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
TAYLOR & FRANCIS LTD
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
The transportation problem (TP) is one of the most popular network problems because of its theoretical and practical importance. If the transportation cost linearly depends on the transported amount of the product, then TP is solvable in polynomial time with linear programming methods. However, in the real world, the transportation costs are generally nonlinear, frequently concave where the unit cost for transporting products decreases as the amount of products increases. Since concave cost transportation problems (ccTPs) are NP-hard, solving large-scale problems is time consuming. In this study, we propose a hybrid algorithm based on the concepts borrowed from tabu search (TS) and simulated annealing ( SA) to solve the ccTP. This algorithm, called ATSA ( adaptive tabu-simulated annealing), is an SA approach supplemented with a tabu list and adaptive cooling strategy. The effectiveness of ATSA has been investigated in two stages using a set of TPs with different sizes. The first stage includes performance analysis of ATSA using SA, ASA ( adaptive simulated anealing) and TS, which are basic forms of ATSA. In the second stage, ATSA has been compared with the heuristic approaches given in the literature for ccTP. Statistical analysis shows that ATSA exhibits better performance than its basic forms and heuristic approaches.
Açıklama
Anahtar Kelimeler
transportation problem, concave cost, simulated annealing, tabu search, hybrid algorithms, adaptive cooling strategy
Kaynak
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
WoS Q Değeri
Q3
Scopus Q Değeri
Q1
Cilt
59
Sayı
3
