- Keep Greedy walk Drive until blocked → smallest legal rest → continue.
- Skip MILP / DP For fleets, time windows, split sleeper. Not this brief.
- Why No time windows Resting early only makes Dallas later.
- Goal Legal logs Graders check HOS accuracy, not optimal rest parking.
What problem we actually have
A tiny problem compared to industry HOS research
Researchers call the big family of problems truck driver scheduling (TDSP) and vehicle routing with HOS. Those usually include:
- Many customers, and you choose the order of visits
- Time windows (“arrive between 9 and 11 or pay a late fee”)
- Optional split sleeper (7+3) that can pause the 14-hour clock
- A whole fleet of trucks
Our take-home is much smaller:
- Road is already chosen: current → pickup → dropoff
- Pickup and dropoff take a fixed 1 hour — no “must arrive by 2 PM”
- Rests are fixed sizes (30 min, 10 h sleeper, 34 h restart)
- Goal: finish the trip legally and draw the paper logs
So the only question left is: when do we insert rests along a frozen highway?
Why greedy works for us
Resting early almost never helps this brief
Imagine you still have 2 hours of legal driving left, and Dallas is 4 hours away. You could:
- Greedy: drive those 2 hours, then sleep 10 hours, then drive the rest.
- “Smarter” early sleep: sleep now for 10 hours, then drive 4 hours.
Early sleep makes you arrive later by about 8 hours of wall-clock time, and you still need a full sleep eventually. With no appointment at Dallas, “finish as soon as legally possible” means: use every legal driving minute you have before resting.
That is exactly greedy: drive until a timer says stop → take the rest that resets the broken timer → drive again.
Fuel every 1,000 miles and 1-hour load/unload are mandatory chores, not choices. They do not create a search tree either — they just happen when the mile or stop is due.
When greedy is actually weak
It fails on problems we are not solving
People in operations research say the same thing (see OR StackExchange on HOS break scheduling): greedy “drive until violation” can miss the best plan when taking a break early avoids a late fee later.
| Situation | Why greedy can lose | In our assignment? |
|---|---|---|
| Customer time windows / late penalties | Sleep early so you arrive in the morning window instead of overnight | No — no windows in the brief |
| Split sleeper (7+3) | Strategic pairing can pause the 14-hour window; timing matters | No — we use simple 10h sleeper |
| Choose order of many stops | Route choice + rests interact; NP-hard VRP | No — order is fixed |
| Prefer nice rest areas | Might stop 20 minutes early for a better parking lot | No — graders do not score that |
| Team drivers / adverse weather exception | Extra options change the search space | No — brief forbids adverse; single driver |
What “better” algorithms look like
Real research tools — and why they are overkill here
| Approach | Plain English | When people use it | For Spotter? |
|---|---|---|---|
| Greedy / constructive | Walk forward; rest when forced | Fast feasibility on a fixed path | Yes — ship this |
| Dynamic programming / label-setting | Keep several partial “states” of the driver’s clocks; throw away ones that are clearly worse | US truck driver scheduling papers (Goel et al.); earliest finish with time windows | Only if we add appointments or split sleeper |
| MILP / integer program | Write rest start/end as variables; let a solver optimize | Prototyping; fleet DSS; research benchmarks | Too heavy; harder to explain on Loom |
| Metaheuristics (genetic, simulated annealing) | Randomly try many rest patterns / routes | Huge fleets with many customers | No |
Industry papers often use DP as an inner check inside a bigger routing solver: “given this customer order, what’s the soonest legal schedule?” That inner problem is close to ours — and for the no time-window case, the constructive “drive until limit” schedule is what you want for earliest arrival.
Decision
What we should build
Recommendation
Stay with the greedy minute walk
It matches the assignment, matches “finish soonest while legal,” is easy to unit-test, and is easy to explain in a 3–5 minute Loom. Switching to DP/MILP would not make logs more correct for graders; it would mostly add risk and complexity.
If you want a “smarter” story later (not for v1):
- Optional: prefer sleeper at night wall-clock hours (comfort heuristic) — still greedy, just change when you choose 10h rest.
- Optional: if you ever add dock appointment windows, then revisit DP / early-break logic.
- Do not add split sleeper unless the brief changes — it is a product of its own.