With new cases of avian influenza H5N1 (H5N1AV) arising frequently, the threat of a new influenza pandemic remains a challenge for public health. Several vaccines have been developed specifically targeting H5N1AV, but their production is limited and only a few million doses are readily available. Because there is an important time lag between the emergence of new pandemic strain and the development and distribution of a vaccine, shortage of vaccine is very likely at the beginning of a pandemic. We coupled a mathematical model with a genetic algorithm to optimally and dynamically distribute vaccine in a network of cities, connected by the airline transportation network. By minimizing the illness attack rate (i.e., the percentage of people in the population who become infected and ill), we focus on optimizing vaccine allocation in a network of 16 cities in Southeast Asia when only a few million doses are available. In our base case, we assume the vaccine is well-matched and vaccination occurs 5 to 10 days after the beginning of the epidemic. The effectiveness of all the vaccination strategies drops off as the timing is delayed or the vaccine is less well-matched. Under the best assumptions, optimal vaccination strategies substantially reduced the illness attack rate, with a maximal reduction in the attack rate of 85%. Furthermore, our results suggest that cooperative strategies where the resources are optimally distributed among the cities perform much better than the strategies where the vaccine is equally distributed among the network, yielding an illness attack rate 17% lower. We show that it is possible to significantly mitigate a more global epidemic with limited quantities of vaccine, provided that the vaccination campaign is extremely fast and it occurs within the first weeks of transmission.