En este trabajo se propone un algoritmo basado en la metaheurística GRASP que, asumiendo fijo un plan de rutas para los camiones, decida relevos válidos para la tripulación a lo largo del horizonte de planificación y minimice el costo que acarrea el traslado del personal en vehículos externos a la flota. Adicionalmente, sobre las soluciones alcanzadas se propone un algoritmo de mejoramiento basado en una búsqueda local que intenta arreglar ciertos traslados externos evitables.