This article aims to illustrate the use of improvement heuristics for solving a vehicle routing problem with time constraints. We present, at first, a state-of-the-art about vehicle routing problems (VRP) by zooming in the VRP with time windows. We then present the possible methods of resolution proposed in the literature. Subsequently, we study the case of the Moroccan post office for postal delivery in the Fes-Meknes-Oujda region. To cope with the rapid changes in its environment, Moroccan post office is engaged in a process of continuous improvement of its transport network. This approach serves both the objectives of improving the quality of service and logistical and economic rationalization. It is in this context that our work fits in. We have tried to improve the postal routing network by using the improvement heuristic based on a set of scenarios in order to arrive at a tactical planning of routing network and efficient management of vehicle fleet while respecting in the same time quality, time and cost constraints.