This paper deals with the dynamic vehicle allocation problem (DVAP) in road transportation of full truckloads between terminals. The DVAP involves multi-period resource allocation and consists of defining the “movements” of a fleet of vehicles that transport goods between terminals with a wide geographical distribution. These movements may be of fully laden vehicles, unladen vehicles for repositioning or vehicles held at a terminal to meet future demands. Emphasis is given to the characterization of the problem in real situations, the mathematical modeling of the problem and the use of exact and heuristic methods to solve it, including GRASP and simulated annealing metaheuristics. Results based on a case study of a transportation company in Brazil are presented and analyzed, showing that the approach can be effective in supporting practical decisions.