🤖 machine learning

Latency-Aware Bid Acceptance under Operational Feasibility: A Public Benchmark with Hindsight Ceilings

This paper introduces FreightBidBench, a public, reproducible benchmark for online truckload bid acceptance that combines realistic operational constraints with public data, and demonstrates that a parametric surrogate-rollout cascade policy achieves near-optimal profits with significantly lower decision latency compared to full rollout methods.

Original authors: Aswin Chandrasekaran

Published 2026-07-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Aswin Chandrasekaran

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a fleet of delivery trucks. Every few seconds, a new delivery job pops up on your screen. You have to make a split-second decision: Do I take this job, or do I say no?

If you say "yes" to the wrong job, you might get stuck far away from your next customer, or you might run out of driving hours before you can finish the delivery. If you say "no" to the right job, you miss out on money. If you say "yes" to a job you can't actually do, you get fined.

This paper introduces a new, public "video game" (called FreightBidBench) designed to test how well computer programs can make these decisions. Before this, researchers mostly used secret data from real trucking companies or static puzzles that didn't change in real-time. This new benchmark is open to everyone and simulates the messy, fast-paced reality of trucking.

Here is a breakdown of the paper's main ideas using simple analogies:

1. The New "Video Game" Rules (The Benchmark)

The authors created a simulation where a computer program acts as the dispatcher. The game has three new "rules" (rewards) that make it much harder and more realistic than previous versions:

The "Don't Break the Rules" Penalty: In the old game, if a program tried to take a job it physically couldn't do (like a truck that was too far away), it just got a warning. In this new game, it gets a cash fine. This forces the computer to actually check if the job is possible before saying "yes."
The "End-of-Day" Bonus: Imagine you finish your workday with your trucks parked in a city where there are no more jobs. You are stuck. In this game, the computer gets a bonus if it parks its trucks in cities where there is lots of future demand. This stops the computer from just taking the first easy job it sees without thinking about where the truck will end up.
The "Rush Hour" Timer: Prices for deliveries go up during specific hours of the day (like rush hour). The game rewards the computer for saving its trucks for those high-paying times, rather than using them up on cheap jobs earlier in the day.

2. The "Crystal Ball" Problem (How to Measure Success)

To know if a computer is doing a good job, you need to know the "perfect" score. But in a world of random traffic and random job offers, you can't know the future.

The authors built two types of "crystal balls" to act as a ceiling for how well anyone can do:

The "Small-Scale" Perfect Solver: For very short periods (like the first 12 jobs), they can calculate the exact mathematically perfect answer. This is like solving a small puzzle perfectly.
The "Relaxed" Perfect Solver: For the whole day, they use a clever math trick. They pretend the trucks can be in two places at once or ignore some rules just to get a "best-case scenario" number. They found a new, tighter version of this trick that is much closer to reality than the old methods.

3. The "Smart Assistant" Strategy (The Cascade)

The paper tests different ways to make decisions:

The "Gut Feeling" (Simple Policy): A fast, simple rule that says "Take any job that looks okay." It's fast but makes mistakes.
The "Super-Computer" (Rollout Teacher): A very slow, powerful program that simulates thousands of possible futures to find the best move. It's accurate but takes too long to run in real life.
The "Smart Assistant" (The Cascade): This is the paper's big innovation. It's a team-up between the fast "Gut Feeling" and the slow "Super-Computer."
- The "Gut Feeling" makes the decision for easy, obvious jobs.
- The Trigger: If the "Gut Feeling" is unsure (the score is close to a tie) OR if there are very few trucks left in a specific city (a "scarcity" situation), it immediately asks the "Super-Computer" for help.

The Result: This "Smart Assistant" team gets almost 98% of the profit of the slow "Super-Computer," but it makes decisions twice as fast. It proves you don't need a supercomputer for every single decision; you just need to know when to call for backup.

4. Why This Matters

The paper shows that:

Feasibility is King: You can't just look at the money; you have to check if the truck can actually do the job. Ignoring this costs money.
Timing Matters: Saving your resources for high-value moments is better than grabbing every small opportunity.
Hybrid is Best: The best way to handle these fast decisions isn't to use a simple rule or a complex AI for everything. It's to use a simple rule for most things and only use the heavy-duty AI when the situation is critical or confusing.

In short, the authors built a fair, public test track for trucking algorithms and showed that a "smart team-up" strategy is the most efficient way to run a fleet in the real world.

Technical Summary: Latency-Aware Bid Acceptance under Operational Feasibility

Problem Definition

The paper addresses the online truckload bid acceptance problem, a closed-loop stochastic decision-making challenge where carriers or brokers must accept or reject load tenders in real-time (within seconds). The decision is constrained by three factors:

Latency: Decisions must be made instantly.
Operational Feasibility: A load can only be accepted if a truck can reach the pickup, satisfy appointment windows, adhere to Hours-of-Service (HOS) regulations, and remain feasible through delivery, accounting for stochastic yard delays.
Economic Opportunity: Accepting a load with immediate positive margin may be suboptimal if it consumes a scarce truck needed for a future high-premium window or strands the fleet in a low-value market.

The paper identifies a gap in existing literature: while static routing benchmarks (e.g., Solomon, CVRPLIB) exist, they lack closed-loop dynamics and public calibration. Conversely, dynamic fleet studies often rely on private data. The authors introduce FreightBidBench v0.3, a public, reproducible, dependency-free benchmark calibrated against the U.S. Freight Analysis Framework (FAF) and USDA truck-rate data to address this.

Methodology

1. Benchmark Formulation (v0.3)

The problem is formalized as a finite-horizon Markov Decision Process (MDP) with continuous time-stamped events.

State: Includes fleet state (location, next available time, remaining HOS drive/duty budgets) and the current load tender (origin, destination, price, time windows, stochastic yard delays).
Action: Binary decision (Accept/Reject).
Feasibility Layer: A deterministic map assigns loads to trucks based on reachability, appointment windows, and HOS constraints. If no truck can serve the load within constraints, the assignment is infeasible.
Reward Structure: The v0.3 release introduces three specific reward components to isolate distinct policy classes:
- L1 (Service-Failure Penalty): A penalty ( $-\rho$ ) is applied if a policy accepts an infeasible load. This creates linear regret for feasibility-blind policies.
- L2 (Terminal Fleet Value): A terminal reward based on the location of trucks at the horizon end, weighted by outbound tonnage and net imbalance. This penalizes greedy policies that strand trucks in low-value markets.
- L3 (Temporal Price-Premium Window): A multiplicative price premium is applied during specific daily hours. This creates a timing problem where accepting off-peak loads may preclude capturing on-peak premiums.

2. Hindsight Ceilings (Upper Bounds)

To evaluate policy performance without relying solely on a rollout teacher, the paper proposes three complementary ceilings:

Exact Small-Prefix DP: An exact dynamic program for small load prefixes (up to $L=16$ ) using memoized search. This serves as a trustworthy reference for small instances.
LP-Style Relaxation: A full-horizon upper bound that relaxes integrality, sequencing, and location constraints, allowing fractional truck-hours and ignoring spatial continuity.
Lagrangian-per-Truck Information Relaxation: A tighter bound that dualizes only the cross-truck assignment constraint while retaining per-truck HOS, location, and sequencing structures. This is justified as an information relaxation (Brown et al., 2010) and is significantly tighter than the LP relaxation.

3. Policy Classes

The paper evaluates a hierarchy of policies:

Baselines: Reject all, Accept all feasible, Myopic margin, and Bid price.
Surrogate: A dependency-free linear surrogate (ridge regression) trained on rollout teacher labels, featuring load attributes, fleet state, feasibility probes, and temporal features.
Rollout Teacher: A finite-lookahead Monte Carlo expansion using common random numbers to estimate the expected value of accept/reject branches.
Surrogate-Rollout Cascade: A parametric policy that uses the surrogate for most decisions but escalates to the expensive rollout teacher under two triggers:
1. Boundary Band ( $\beta$ ): When the surrogate's signed score is near zero (uncertainty).
2. Scarcity Threshold ( $\kappa$ ): When the origin market has few immediately available trucks (high-stakes capacity decisions).

Key Results

1. Calibration and Layer Ablation

Experiments confirm that the three reward layers successfully separate policy classes:

L1: A penalty of $\rho = \$ 10$ causes feasibility-blind policies (myopic margin, bid price) to underperform feasibility-aware greedy baselines by approximately $\$ 3.1k $–$ \ $3.7k$ .
L2: A terminal value weight of $\omega = 0.25$ reduces the "Accept all feasible" policy's retention to ~90% of the rollout teacher's profit, demonstrating that myopic feasibility is insufficient.
L3: A price-premium amplitude of 0.5 widens the gap between the best simple policy and the rollout teacher to ~11–14 percentage points, creating headroom for future-aware methods.

2. Policy Performance

On "tight" and "scarce" scenarios (10-seed evaluation):

Simple Baselines: Retain 86.5%–91.0% of rollout profit.
Linear Surrogate: Retains 89.3%–94.2% of rollout profit, outperforming simple baselines but leaving significant value on the table.
Cascade: A cascade with a single escalation band (\beta = \500$) and scarcity threshold ( $\kappa = 2$ $κ = 2$ ) recovers 98.0%–98.2% of rollout profit.
- On "tight" scenarios, the cascade is statistically indistinguishable from the rollout teacher (95% CI spans zero).
- Latency: The cascade operates at 40%–56% of the rollout teacher's mean decision latency (e.g., ~12.95ms vs 32.11ms on tight scenarios).

3. Hindsight Diagnostics

The Lagrangian-per-truck bound is 20.7% tighter (tight scenario) and 39.3% tighter (scarce scenario) than the LP-style relaxation.
Rollout retention against the Lagrangian bound is 67.6% (tight) and 65.7% (scarce), suggesting that the remaining gap is due to cross-truck coordination rather than single-truck scoring errors.

Significance and Claims

The paper claims the following contributions and insights:

Reproducible Benchmark: FreightBidBench v0.3 provides the first public, versioned, and dependency-free benchmark for online truckload bid acceptance that explicitly models operational feasibility and economic trade-offs.
Structural Separation: The three reward components (L1, L2, L3) mathematically and empirically isolate distinct failure modes (feasibility blindness, positioning myopia, and timing blindness), ensuring that future methods are tested against meaningful structural challenges.
Methodological Headroom: By tightening the upper bound via Lagrangian relaxation, the paper demonstrates that the "headroom" for improvement is smaller than LP relaxations suggest. The remaining gap lies in inter-truck coordination (joint-decision lookahead) rather than single-tender scoring.
Cascade Efficiency: The surrogate-rollout cascade is presented as the optimal framing for practice. It leverages cheap surrogates for routine decisions while deferring high-stakes, uncertain decisions (driven by scarcity or score ambiguity) to expensive teachers, achieving near-optimal profit with significantly reduced latency.
Operational Feasibility as Reward: The paper argues that feasibility should be embedded in the reward function (via penalties) rather than treated as a side diagnostic, as ignoring it incurs linear regret.

The authors explicitly state that the benchmark is the primary artifact; the methods results serve as evidence that the sharpened problem admits a non-trivial latency-profit frontier. The release includes versioned scenario contracts, policy sets, and exact-plus-relaxed ceilings to serve as a reproducible testbed for future work.