Since fruit and vegetable are highly perishable, and have strong timeliness in selling and consuming, the delivery routes of transport vehicles must be planned reasonably. On the path of fruit and vegetable delivery, a transport vehicle may encounter some unusual circumstances and may not arrive at the next distribution site in time. In this case, the vehicle routes of other transport vehicles should be replanned. A mathematical model for vehicle route replanning with time windows for fruit and vegetable delivery was established, and an improved ant colony algorithm was used to resolve the model. Simulation experiment results showed that the new dispatching routing of fruit and vegetable could be optimized efficiently by using the proposed model and adopted algorithm. This research could provide theoretical support for enterprises which hoped to decrease rot loss of fruit and vegetable, increase sales income and control operating cost effectively.