An interactive optimization methodology for allocating the number and configuration of an Air Quality Monitoring Network (AQMN) in a vast area to identify the impact of multiple pollutants is described. A mathematical model based on the multiple cell approach (MCA) was used to create monthly spatial distributions for the concentrations of the pollutants emitted from different emission sources. These spatial temporal patterns were subject to a heuristic optimization algorithm to identify the optimal configuration of a monitoring network. The objective of the optimization is to provide maximum information about multi-pollutants (i.e., CO, NO(x) and SO(2)) emitted from each source within a given area. The model was applied to a network of existing refinery stacks and the results indicate that three stations can provide a total coverage of more than 70%. In addition, the effect of the spatial correlation coefficient (R(C)) on total area coverage was analyzed. The modeling results show that as the cutoff correlation coefficient R(C) is increased from 0.75 to 0.95, the number of monitoring stations required for total coverage is increased. A high R(C) based network may not necessarily cover the entire region, but the covered region will be well represented. A low R(C) based network, on the other hand, would offer more coverage of the region, but the covered region may not be satisfactorily represented.