Scheduling the deliveries from a regional distribution centre (RDC) to large stores of a major fmcg retailer includes every possible vehicle routing complexity. Usual constraints, like the size of the vehicle and the length of the driving day, apply. More importantly, loading feasibility is a major factor, with frozen goods being at the front, produce and perishable products in the middle, and groceries at the tail of the rear end loading vehicle. Moreover, these three product types have different time windows, determined store by store. Items like medium movers and alcoholic drinks may only be stocked at particular hub depots, from where they must be collected and then delivered to the retail outlets. Collections of salvage are made from the stores and goods from suppliers are backhauled to a RDC, which may not be the vehicle's base. Then there may be trunking between RDCs. In this case study, deliveries and collections by vehicles at a RDC are presently scheduled by updating daily a basic plan prepared every six months, using the skills of an experienced distribution professional. A simulated annealing based algorithm has been developed to speed up the process by circumventing the need for the skeletal schedule. In the application tested, the solution produced by the algorithm requires the same number of vehicles as actually used, though the total delivery time is slightly longer. Further improvements, particularly in the quality of the initial solution, may be possible by exploiting the problem structure in recognisable ways.