How often does one of your trucks get back to the yard after the shift ends? And when it does, is that bad luck, or the plan?

Septic pump-out is a clear case. A truck leaves the yard with an empty 3,000-gallon tank and a list of houses. Nobody knows the gallons until the lid is open: the tank may be bigger than code requires, or there may be a second one. When the truck fills up, it drives back to unload, and the day gets longer. A plan built on the average house looks fine on paper and still runs past the shift on many days.

This is post #2 in a series on award-winning operations research theses, applied outside the setting the authors studied. This one is about planning routes when you only learn how much work a stop is once you get there. Below, the thesis first, then my experiment, then what it cost.

The two-minute version, narrated by Renan with an AI voice clone of his own voice.
Read the video transcript

How often does one of your trucks get back after the shift ends? Bad luck, or the plan? Take a septic truck. Nobody knows the gallons until the lid is open. When the tank fills, it drives back to unload, and the day runs long.

This is post two in my series: award-winning operations research theses, applied to small businesses. Alexandre Florio's thesis, from the University of Vienna, won the 2021 EURO Doctoral Dissertation Award. I use a chapter he wrote with Richard Hartl, Stefan Minner and Juan-José Salazar-González.

The idea I borrow: don't ask how long a route takes on average. Ask the chance it ends on time, and keep only routes that fit the ten-hour shift on ninety-five percent of days. Plus a rule for each stop: unload early when the detour is cheap.

My test: a made-up pump-out company in Cherokee County, Georgia. Twenty-four jobs a day, and a technician's day may last ten hours, yard to yard.

House sizes and Georgia's tank rule are real. The gallons are my assumption: thirteen hundred on average, so two houses fit in the truck, and a third usually doesn't.

Look at one truck. The average-house plan gives it seven jobs, and half its days run past ten point four hours. The thesis plan gives it six, and only a three percent chance of running long.

Over sixteen simulated days, how often did a truck finish past ten hours? Lower is better. Planning on the average house: sixty-two percent of days. A fifteen percent buffer: twenty-five percent. The thesis method: about five percent, one day in twenty.

The catch: it needed a fifth truck every day. And the truck isn't all of it: the average plan on five trucks still ran long on forty-two percent of days. If late only means overtime, the truck probably isn't worth it. If the disposal site closes, it may be.

If you want to try it, log the gallons and the time on site for every job. And check each route's chance of running past the shift, not its average length.

The full write-up and the code are on bisdecisions.com. Thanks to Alexandre Florio and his coauthors for the research behind it.

What the thesis did

Alexandre Florio's PhD thesis, Models and Solution Methods for Stochastic Vehicle Routing Problems (University of Vienna, 2019, supervised by Richard Hartl), won the 2021 EURO Doctoral Dissertation Award, presented at the EURO 2021 conference in Athens.123 Its full text is not publicly released, so I worked from the published paper behind its part on probabilistic duration constraints.

In plain words, the part I used changes two things. First, it doesn't ask how long a route takes on average; it asks what the chance is that the route ends on time, and keeps only routes that fit the time limit with a set probability (here, 95% of days). Second, for each stop, it decides in advance whether the truck should go unload before it's full, when the detour is cheap.

The method, for readers who work in routing

The chapter I borrow was written while Florio was at the University of Vienna's Department of Business Decisions and Analytics, with his supervisor Richard Hartl, Stefan Minner (Technical University of Munich) and Juan-José Salazar-González (Universidad de La Laguna).4 Customers' demands are revealed only on arrival, and a vehicle may go back to the depot to restock mid-route. Restocking is optimal: after each customer, a threshold on the load left decides whether to go on or restock first, computed with a classic dynamic program.7 The trips back are random, so the route's duration is random too. The paper requires each route to finish within its limit with a set probability, and minimizes total expected travel time. It drops the usual cap on expected demand per route, so a route may plan for more than one vehicle load.

The method is a branch-and-price algorithm (it builds candidate routes one at a time and searches over which ones to use). Feasibility is checked with a one-sided Chebyshev bound, Monte Carlo simulation, or the exact distribution of the duration. On literature instances, against an earlier heuristic that used the simpler detour-to-depot rule and capped expected demand per route, their solutions cost less in 22 of 23 instances and used fewer vehicles in 13. Stricter levels (90% to 98%) and more variable demand raised costs and sometimes the number of routes.

A companion paper from the thesis, with Hartl and Minner, found that the stochastic model pays most when each vehicle visits few customers.56 A septic truck visits about five. The septic application below is mine, not the authors'.

The paper (Florio et al., 2021)Septic pump-outs (my application)Customer demand, revealed on arrivalGallons pumped, known once the lid is openVehicle capacity3,000-gallon truck tankRestocking trip to the depotDrive back to unload at the disposal siteOptimal restocking policyUnload early when the next tank may not fitP(route duration ≤ limit) ≥ 95%P(technician's day ≤ 10 hours) ≥ 95%
The parts of the chapter's model I kept. The truck's tank is the capacity, the gallons pumped are the random demand, and unloading at the disposal site is the restocking trip. The day also includes time on site, which the paper's model doesn't have.

The septic trucks

A hypothetical pump-out company with a yard in Canton, Georgia, next to its disposal site, serving Cherokee County. Each day has 24 jobs at random points in the county. The real inputs are the share of Cherokee County homes by number of bedrooms, from the Census Bureau's American Community Survey,8 and Georgia's rule for minimum tank size: 1,000 gallons for up to four bedrooms, plus 250 for each extra bedroom.9 The rest is my assumption, labeled in the code: tank sizes above code, rinse water, a second tank or an oversized old system in 8% of homes, setup and pump times, 0 to 45 minutes to dig up the lid, and 20 minutes per unload. Drive times are straight-line distance times 1.3, at 45 km/h.

Probability of each pumped volume, house with 1–4 bedrooms · mean 1,300 gal0%10%20%30%truck tank 3,000 gal1,0001,5002,0002,5003,000Code minimum 1,000 gal (GA rule 511-3-1-.05) · red: second tank or oversized system (8%)
Gallons pumped at a house with up to four bedrooms, under my assumptions. The average is 1,300 gallons, so two houses fit in the truck and a third usually doesn't. About one house in twelve has a second tank or an oversized old system.

A technician's day may last 10 hours, yard to yard. I compared plans that a dispatcher would recognize with the chapter's method:

  • Average-day plan: plan every house at its average gallons and average time, place the unloads where they fit, and make the planned day fit in 10 hours. On the road, the driver pumps until the truck is full, then unloads.
  • Padded plan: the same, but the planned day must fit in 8.5 hours, a common 15% buffer.
  • Thesis method: the cost of each route is its expected driving and unloading time under the optimal unloading rule. Each route must fit in 10 hours with 95% probability.
Steps 2 and 3 follow the chapter; the paper finds routes by exact branch-and-price, I use a heuristicCandidate routescolumn generation(heuristic pricing)Expected costoptimal unloadingexact dynamic programDay-length checkP(day ≤ 10 h) ≥ 95%bounds, then exactPick the plancover every job oncefewest trucks, then costprices from the plan steer the next round of candidate routes
How the plans are built. Candidate routes come from column generation, a standard way to generate many good routes and pick the best set. The chapter's ideas sit in the middle: an exact expected cost under optimal unloading, and a check on the chance that the day fits.

For readers who work in routing, my version departs from the paper in a few ways. Its duration is travel time only; mine adds time on site, which grows with the gallons, a random dig time, and 20 minutes per unload. It has no cost per vehicle; mine does, so every planner first uses as few trucks as it can. My volumes are not Poisson. My routes come from a greedy heuristic, so they are good, not proven optimal,10 and my feasibility check uses the Chebyshev bound in both directions plus the exact distribution, without the Monte Carlo step. Every plan was scored on the same model and checked with 4,000 simulated days per plan and day.

What happened

Average-day plan · 4 trucksP(someone runs over 10 h) = 86%6 jobs · P(over 10 h) 7%4 jobs · P(over 10 h) 0%7 jobs · P(over 10 h) 64%7 jobs · P(over 10 h) 58%Thesis plan · 5 trucksP(someone runs over 10 h) = 5%2 jobs · P(over 10 h) 0%6 jobs · P(over 10 h) 0%6 jobs · P(over 10 h) 3%4 jobs · P(over 10 h) 0%6 jobs · P(over 10 h) 2%
Day 0. Left: the average-day plan uses 4 trucks, and two of them have a 58% to 64% chance of running past 10 hours. Right: the thesis plan uses 5 trucks, and none has more than a 3% chance. Lines are straight, not roads.

The number to watch is the share of days on which at least one truck finished past 10 hours. Lower is better: it is how often someone works late or a job slips. Over 16 days, the average-day plan used 4 trucks a day, and on 62% of days (about 2 in 3) at least one of them ran past 10 hours, with 35 minutes of overtime per day on average. In 56 of its 64 truck-days, the chance of running long was above 5%.

The thesis method used 5 trucks every day. At least one truck ran past 10 hours on 4.6% of days, about 1 day in 20, with about one minute of overtime per day. Driving and unloading came to 878 minutes per day, against 934 for the average-day plan.

Chance that at least one truck runs past 10 hours, average over 16 daystrucks per day · expected overtime and driving + unloading minutes per dayAverage-day plan4 trucks · 34.9 min OT · 934 min61.5%Same, forced to 5 trucks5 trucks · 20.1 min OT · 917 min42.1%Padded plan (85% of shift)4.9 trucks · 8.5 min OT · 967 min25%Thesis method, 95%5 trucks · 1.1 min OT · 878 min4.6%All plans scored on the same stochastic model; Monte Carlo (4,000 days each) agrees within 0.2 points
Chance that at least one truck runs past 10 hours, averaged over 16 days, with trucks used, expected overtime and driving plus unloading time per day.

Is it just the fifth truck? Here, not entirely. When I forced the average-day plan to use 5 trucks, a truck still ran long on 42% of days: it balances the average day, not the risk. The padded plan also used about 5 trucks (79 truck-days against 80) and still ran long on 25% of days (1 in 4), with 967 minutes of driving and unloading.

Chance of each day length (10-minute bins), same area of the county, day 00%5%10%past 10 hours4 h6 h8 h10 h12 hAverage-day plan, 7 jobs · median 10.4 h · 64% overThesis plan, 6 jobs · median 8.4 h · 3% over
One truck's day, in the same part of the county. The average-day plan packs 7 jobs into a route whose median day is 10.4 hours. The thesis plan's 6-job route has a median of 8.4 hours and a 3% chance of running past 10.
One 6-job route (day 0). After each job: go unload first if fewer gallons than this areleft in the 3,000-gal tank. Every next house is expected to need 1,300 gal.after job 1< 200 gal · yard 27 min awayafter job 2never · yard 26 min awayafter job 3never · yard 23 min awayafter job 4< 450 gal · yard 9 min awayafter job 5< 1,000 gal · yard 9 min awayNear the yard, unloading early is cheap, so the threshold rises (1,000 gal after job 5).Far from it, the truck presses on and unloads only if it must.
The optimal unloading rule along one thesis route: a threshold per stop, as in the paper. Unload first if fewer gallons than this are left. On this route, the threshold rises to 1,000 gallons near the yard, where an early trip costs little.

What didn't matter, and what it cost

Most of the time savings came from the unloading rule, not the routes: the average-day plan, driven with the optimal rule, also needed 878 minutes a day. On the thesis's own routes, the rule saved 3% against pumping until full. That fits the paper and its companion: optimal restocking adds little on routes capped at a full vehicle, and more when routes may plan beyond it.46

The probability requirement is what cut the risk here. Requiring only the expected day to fit in 10 hours kept 4 trucks, and a truck ran long on 48% of days. At 90% per truck, the method used 4.8 trucks a day and a truck ran long on 16% of days. Going from 95% to 98% cost no extra truck and brought it to 1.3%. The paper also found that stricter levels sometimes need more routes.

And the method doesn't create capacity: it needed a fifth truck every day. If running long only costs overtime wages, 35 minutes a day is probably cheaper than a truck. The truck pays off when the end of the day is hard, like a disposal site that closes or a job pushed to tomorrow. I didn't model those costs.

If you want to try it

  • Log the gallons pumped and the time on site for every job. Everything here depends on those distributions, and mine are assumptions.
  • If late days are what hurts, check each route's chance of running past the shift, not its average length. Here, that check is what moved the risk.
  • An unloading threshold per stop is cheap to try. Here it saved about 6% of driving and unloading time on the average-day routes.
  • If you pad routes, compare the padded plan's risk route by route. Here a flat 15% buffer used as many trucks and still ran long one day in four.

What would change this conclusion

  • Overtime that only costs wages. Then a fifth truck likely costs more than it saves.
  • Better tank records. Less volume uncertainty leaves the method less to fix; more variable volumes push the other way, as in the paper's tests.
  • More jobs per truck. With 15 or more customers per route, the companion paper found the stochastic model adds little. Here routes had about five.
  • Real roads and traffic. My drive times are straight-line estimates, without traffic's own randomness.

Caveats

The tank volumes, service times and job locations are synthetic; only the bedroom shares and the code minimum are real. There are no time windows, and the yard is also the disposal site. My route generation is a heuristic, and my model adds service and unloading times the paper doesn't have. The experiment covers 16 days of one hypothetical company. The code and results are public.11

Drafted with AI assistance (Claude). The experiment ran on my machine, and every number above is in the repository.