Certified-Gap Dual-Price Policies for Real-Time Truckload Bid Acceptance

This paper studies real-time truckload bid acceptance when trucks relocate between markets and operate under hours-of-service clocks and appointment windows. It formulates the problem as a weakly coupled dynamic program and derives both a dual-price policy and an upper bound from the same Lagrangian relaxation, yielding a certified optimality gap for every run. On a public closed-loop benchmark with 30 paired seeds, the policy outperforms a rollout-trained surrogate in two of three scenarios and ties the third. Inference takes 0.04–0.09 ms, while certificates reach 57–64% of optimal.