A HEURISTIC APPROACH BASED ON GENETIC ALGORITHM FOR CONCAVE COST TRANSPORTATION PROBLEM
Journal Name:
- Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi
Key Words:
Keywords (Original Language):
| Author Name | University of Author |
|---|---|
Abstract (2. Language):
Concave Cost Transportation Problem (CCTP) is one of the widely employed problems in real applications. In this problem, the unit cost is decreasing in the amount that is transported. Since these types of problems are nonlinear, it is difficult to solve them to optimality. In literature, metaheuristic techniques such as genetic algorithm, simulated annealing and tabu search have been successfully applied for solving these problems. In this study, we develop a new hybrid algorithm based on genetic algorithms for the problem. The efficiency and effectiveness of the algorithm are investigated using twelve randomly generated test problems in which the number of suppliers and customers changes between 4 and 40. Comparisons with other heuristics based on simulated annealing, threshold acceptance and linear threshold acceptance shows that developed hybrid GA improves solution quality by 0.3% and 5% for four problems.
Bookmark/Search this post with
Abstract (Original Language):
Konkav Maliyetli Ulaştırma Problemi (KMUP), gerçek hayatta sık karşılaşılan problemlerden birisidir. Doğrusal
maliyetli problemlerin aksine, KMUP’de taşınacak miktar arttıkça birim taşıma maliyeti azalmaktadır. Bu tür
problemlerde doğrusal olmayan maliyet fonksiyonundan dolayı klasik optimizasyon yöntemleri ile en iyi çözüme ulaşmak mümkün olmayabilir. Son yıllarda, genetik algoritmalar, tavlama benzetimi ve tabu arama gibi genel amaçlı sezgisel yöntemlerin bu tür zor problemlerin çözümünde başarıyla kullanıldığı görülmektedir. Bu çalışmada, KMUP için genetik algoritmalara dayalı bir karma sezgisel algoritma (karma GA) geliştirilmiştir.
Algoritmanın etkinliği, tedarikçi ve müşteri sayısının 4 ile 40 arasında değiştiği ve rassal olarak üretilen 12
problem üzerinde incelenmiştir. Geliştirilen karma GA, literatürde bu problem için geliştirilmiş olan tavlama
benzetimi, eşik kabulü ve doğrusal eşik kabulü yöntemine dayalı sezgisel algoritmalar ile karşılaştırılmıştır.
Karşılaştırma sonucunda, geliştirilen karma GA ile dört problem için çözüm kalitesinde %0.3 ile %5 arasında
iyileşmenin olduğu görülmüştür.
FULL TEXT (PDF):
- 4
443-454