In a drive-thru scenario, where vehicles drive by a roadside access point (AP) to obtain temporary Internet access, efficient resource allocation schemes are required to fully utilize the limited communication opportunity. In this paper, we study random access in vehicle-to-roadside (V2R) communications in a dynamic environment, where both the channel contention and capacity vary over time. We consider that a vehicle has a file to upload when it is within the coverage range of the AP. A fixed payment to the AP is required for each time slot that the vehicle has sent a request for packet transmission, and a self-incurred penalty is imposed for not being able to complete the file upload. We first formulate the problem of finding the optimal transmission policy as a finite-horizon sequential decision problem. Then we solve the problem using dynamic programming, and design a dynamic optimal random access algorithm. Simulation results based on realistic vehicular traffic model show that our algorithm achieves the minimal total cost, the highest probability of completing file upload, and the highest upload ratio as compared with two other heuristic schemes. © 2011 IEEE.