I have used a GAP as a subproblem in a previous project where the aim was to solve the single source capacitated facility location problem. I tried several things in order to speed up the computations, and found that the most effective approach was to use exact knapsack separation from the capacity constraints. That is, I basically solved the dual of the "natural" column generation master.
The way I implemented it was using CPLEX by first solving the LP relaxation at the root node, then I ran several cut-loops until I experienced too much trailing off. After that, I converted the problem to an IP and added a cut callback, which used the same separation routine as I used at the root node. After experimenting a bit, I found that I got the best results this way, as CPLEX wanted to stop the cut-loop at the root node earlier than I did. I am definitely not saying this is the best way to do it, but in my experience, it worked quite okay.
But, given that it is an NP-annoying (complexity class formally defined by @prubin, I think) problem, you will have to expect that in some cases the computation time explodes!
(You can find an implementation in c of a exact knapsack separation routine here: header source, the function you need is