🚛 RoadStar — Autonomous Fleet Dispatch & Deadhead Optimizer

💡 Inspiration

Empty semi-truck driving—known as "deadhead"—wastes $40 Billion in fuel and emissions every year in the US. Most fleet dispatchers assign loads using a greedy "nearest-driver" shortcut. While the first match seems efficient, it traps the rest of the fleet into driving hundreds of empty miles. We built RoadStar to replace human guesswork with mathematically optimal dispatching, strict legal safety guardrails, and real-time AI telemetry.


⚡ What It Does

  • Minimizes Empty Deadhead: Uses global bipartite matching across the entire fleet simultaneously, cutting empty miles by 28% and saving 80+ gallons of diesel per cycle.
  • Enforces Real-World Regulations: Hard-blocks assignments violating the FMCSA 11-hour driving rule, missed pickup appointment windows, trailer mismatches (Reefer/Van/Flatbed), or gross weight limits.
  • Decodes Driver Texts with AI: Leverages Google Gemini 1.5 Flash (with instant offline NLP fallback) to translate informal driver SMS ("bad wreck on I-95, delayed 2 hrs") into structured delays, locations, and proactive dispatcher actions.
  • Simulates Enterprise ROI: Models annual fuel savings, reduced equipment wear, and carbon abatement for fleets up to 150 trucks.

🛠️ How We Built It

1. Cost Matrix & Highway Curvature

We compute ground travel distances using the Haversine formula with an empirical $1.17\times$ interstate winding factor:

$$d = 2R \cdot \arcsin \left( \sqrt{\sin^2\left(\frac{\Delta \phi}{2}\right) + \cos(\phi_1)\cos(\phi_2)\sin^2\left(\frac{\Delta \lambda}{2}\right)} \right) \times 1.17$$

Pairings violating safety or appointment windows receive an infinite cost penalty:

$$C_{ij} = \begin{cases} d(i, j) & \text{if pairing is legal & on-time} \ \infty \ (999{,}999) & \text{if HOS breach, late pickup window, or trailer mismatch} \end{cases}$$

2. Kuhn-Munkres (Hungarian) $O(N^3)$ Solver

We implemented the Hungarian algorithm in pure TypeScript to find the globally optimal assignment:

$$\min \sum_{i=1}^{N} \sum_{j=1}^{M} C_{ij} x_{ij} \quad \text{subject to} \quad \sum_{j} x_{ij} = 1, \quad \sum_{i} x_{ij} = 1$$

The engine solves the complete $8 \times 8$ fleet matrix in $< 5\text{ ms}$ client-side.

3. Tech Stack

  • Frontend: Vite + React 19 + TypeScript + Tailwind CSS v4
  • Icons & UI: Lucide React (lucide-react)
  • AI Telemetry: Google Gemini API (gemini-1.5-flash) + offline regex NLP parser

🧗 Challenges We Faced

  1. Real-World Constraints vs. Pure Math: Standard matching only minimizes miles. Injecting hard regulatory constraints (11h driving limits, mandatory 10h sleeper berth breaks, and warehouse appointment cutoffs) into the cost matrix without breaking feasibility was our biggest engineering hurdle.
  2. Parsing Messy Driver SMS: Truck drivers use informal voice-to-text slang. We had to design structured schemas and a zero-latency regex fallback to reliably extract delay minutes and highway corridors offline.

📚 What We Learned & Accomplishments

  • Proven Impact: Achieved a 28% reduction in empty miles and 100% FMCSA compliance with zero late pickups in our benchmark.
  • Global vs. Local Optimization: Proved mathematically how legacy "nearest-driver" dispatching inflates total fleet costs and creates safety violations.
  • Offline Reliability: Built a dual-engine architecture that runs entirely client-side without crashing if hackathon WiFi fails.

🚀 What's Next

  • Continuous Backhaul Tours: Automatically chaining delivery destinations into subsequent pickup origins for multi-day circular routes.
  • Live ELD & TMS APIs: Direct telematics integration with Samsara, Motive, and DAT freight boards.

Built With

  • google-gemini-1.5-flash-api
  • haversine
  • kuhn-munkres-(hungarian)-algorithm
  • lucide-react
  • react-19
  • tailwind-css-v4
  • typescript
  • vite
Share this project:

Updates

Submission history