Summary: There are numerous practical vehicle routing applications in which vehicles have to stop at certain facilities along their routes to be able to continue their service. At these stops, the vehicles replenish or unload their cargo or they stop to refuel. In this paper, we study the vehicle routing problem with intermediate stops (VRPIS), which considers stopping requirements at intermediate facilities. Service times occur at these stops and may depend on the load level or fuel level on arrival. This is incorporated into the routing model to respect route duration constraints. We develop an adaptive variable neighborhood search (AVNS) to solve the VRPIS. The adaptive mechanism guides the shaking step of the AVNS by favoring the route and vertex selection methods according to their success within the search. The performance of the AVNS is demonstrated on test instances for VRPIS variants available in the literature. Furthermore, we conduct tests on newly generated instances of the electric vehicle routing problem with recharging facilities, which can also be modeled as VRPIS variant. In this problem, battery electric vehicles need to recharge their battery en route at respective recharging facilities.