Towards an Ant Colony Optimization Algorithm for the Two-stage Knapsack Problem
2011 (English)In: Proceedings of the 7th ALIO/EURO Workshop on Applied Combinatorial Optimization / [ed] Ana Viana, A. Miguel Gomes, Joao Pedro Pedroso, Maria Teresa Costa, 2011, 27-27 p.Conference paper (Refereed)
We propose an Ant-Colony-Optimization algorithm for the Two-Stage Knapsack problem (TSKP) with discretely distributed weights. Three heuristic utility measures are proposed and compared. We argue why for the proposed measures it is more efficient to place pheromone on arcs instead of vertices or edges of the complete search graph. Numerical tests show that the algorithm is able to find near optimal or even optimal solutions after a relatively small number of generated solutions.
Place, publisher, year, edition, pages
2011. 27-27 p.
Two-stage model, Knapsack problem, Ant-Colony optimization, Meta-heuristic, Utility ratio
IdentifiersURN: urn:nbn:se:liu:diva-74519OAI: oai:DiVA.org:liu-74519DiVA: diva2:486472
7th ALIO/EURO Workshop on Applied Combinatorial Optimization