In this paper, we handle the problem of picking and delivering patients among the distinct units of a hospital. This problem is found in hospitals with several (specialized) units covering a large area, and it emerges from a real situation faced by a hospital in northern Italy. Patient transportation requests arrive dynamically during the day, and the hospital transportation department must service them all using capacitated and homogeneous vehicles. Each request is associated with a patient urgency level (weight) and a time window. The objective is to design vehicle routes to serve all requests and minimize the total weighted tardiness. To solve the problem, we propose a re-optimization heuristic based on two policies that mimic the patients’ and hospital’s decision-making processes. We then improve the solutions obtained with the policies using a tabu search. Computational results show that we can obtain high-quality solutions using the tabu search compared with the policies and a simulated annealing-based heuristic from the literature.