This research has proposed an adaptive ant colony algorithm and its colored Petri net approach, aiming to solve the slow operation problems existed in vehicle routing problems. The new developed method has improved the updating rule of pheromone, changed the formula of transfer probability and the constructed technique of feasible solutions, with the Petri net model conducted accordingly. The proposed method is finally verified compared to GA and some other ACOs through standard test cases, with the results demonstrated that the method developed effectively improves the convergence efficiency, refrains the searching from being trapped in local optima, and ensures the diversity of the final solutions.