A metaheuristic called Sensitive Ant Model (SAM) for solving combinatorial optimization problems is developed. The proposed model is based on the Ant Colony System (ACS) algorithm in which agents cooperate indirectly using pheromone trails. SAM improves and extends the ACS approach by endowing each agent of the model with properties that induce heterogeneity. Different pheromone sensitivity levels are used for agents in the population. Highly-sensitive agents are essentially influenced in the decision making process by stigmergic information and thus likely to select strong pheromone-marked moves. Search intensification can be therefore sustained. Agents with low sensitivity are biased towards random search inducing diversity for exploration of the environment. A balanced sensitivity distribution is facilitated by the co-existence of several subpopulations with pheromone sensitivity level generated in a specified range. A heterogeneous agent model has the potential to cope with complex search spaces. Sensitive agents (or ants) allow many types of reactions to a changing environment facilitating an efficient balance between exploration and exploitation.