The reason there is ice at 37 F is radiation heat transfer.
Pavement is similar to a "black body". It can radiate away its energy to another colder black body, like the nighttime sky, or deep shade.
There is also the phenomenon of thermal inertia. That's what's in play when bridges freeze first. The ground is a thermal reservoir, slowing the cooling rate for pavement. But there is no ground directly in contact with the underside of a bridge.
FWIW, the water freezes around 32F, and so even if the air is at 37, if the pavement is 32, moisture on the pavement will freeze. The air does not have to be 32 for there to be ice forming on unsalted pavement.