Ein Algorithmus für das disjunkt beschränkte Rucksackproblem

Dieses Papier schlägt eine Anpassung der Scatter-Search (SS) Meta-Heuristik vor, um das disjunkt beschränkte Rucksackproblem (DCKP) annähernd zu lösen. Das DCKP kann als Variante des Standard-Rucksackproblems mit besonderen disjunktiven Einschränkungen betrachtet werden. Zwei Versionen von SS werden vorgestellt, die nach der üblichen Struktur von SS organisiert sind. Die Methode wird rechnerisch an einer Reihe von Probleminstanzen aus der Literatur analysiert und mit den Ergebnissen verglichen, die vom Cplex-Löser und anderen Algorithmen aus der Literatur bereitgestellt werden. Für diese Instanzen, von denen die meisten nicht in akzeptabler Zeit nachgewiesen optimal gelöst werden können, liefert die vorgeschlagene Methode Ergebnisse von hoher Qualität innerhalb angemessener Rechenzeit.