Heuristic Algorithms for the Fixed-Charge Multiple Knapsack Problem
In a previous paper we formulated the fixed-charge multiple knapsack problem (FCMKP),and developed an exact algorithm to solve this problem to optimality by combining pegging test and branch-and-bound technique. Although the developed algorithm was quite successful for instances with small number of knapsacks (m), for larger m the problem was hard to solve by this method.Here we present some heuristic algorithms that can produce approximate solutions of satisfactory quality for FCMKPs with much larger m than in previous papers. We present greedy, local search and tabu search heuristics, and through numerical experiments evaluate these algorithms. As the result, we find that the local scarch method gives a satisfactory approximation for uncorrelated and weakly correlated cases, while in strongly correlated case tabu search is effective in obtaining solutions of high quality, although it is far more time consuming than other heuristics.
Integer programming multiple knapsack problem fixed-charge problem tabu search
Byungjun You Takeo Yamada
Department of Computer Science, The National Defense Academy Yokosuka,Kanagawa 239-8686, Japan
国际会议
The Seventh International Symposium(ISORA08)(第七届国际效力研究及其应用学术会议)
云南丽江
英文
207-218
2008-10-31（万方平台首次上网日期，不代表论文的发表时间）