Air contamination becomes an urgent problem to be considered as a result of the rapid growth in traffic all over the world. Traffic emissions differ from vehicle to vehicle depending on the vehicle type, production year, fuel octane number, and periodical maintenance of the vehicle. The majority of drivers do not revise their harmful vehicles emissions regularly. Therefore, effective tracking of high-emitting vehicles can be an important solution for reducing traffic air pollution. This study proposes a location strategy for vehicle remote sensing monitors aided with ID-plate recognizer to capture any violated vehicle emissions. The problem is formulated into a graph theory problem, and then a novel adapted metaheuristic algorithm is used to solve the problem. The methodology, using a benchmark problem, has managed to solve the problem to the optimality. Moreover, its robustness is measured statistically.