Vehicle-Dependent Spoilage as a Small Markov Chain in Time-Windowed Routing

Some cargo is alive or chemically fragile: blood products, cell therapies, biologics, fresh food. For this cargo a delivery deadline is not a fixed number written on an order. It is the moment the cargo stops being usable, and that moment is random. It also depends on which vehicle carries the item, because refrigeration classes differ, and on how many times the cargo door is opened before the item is dropped off. Current routing methods handle only pieces of this. Heterogeneous-fleet solvers treat cargo as inert. Stochastic time-window solvers assume identical vehicles. Perishability models evaluate a single deterministic purchaser. This proposal models each item's condition as a small discrete Markov chain, a random process that jumps between a few quality levels such as "fine," "degraded," and "spoiled." The chain's transition probabilities depend on the vehicle class, the duration of each leg, and each door opening. A route's spoilage risk then becomes a product of small matrices. Products of matrices can be computed piece by piece and combined, so the calculation fits inside the fast segment-concatenation tricks that modern local-search routing solvers already use.

The scientific question sits underneath the algorithm. Systems biology keeps finding that two-state "on/off" abstractions break down when the underlying process accumulates damage gradually. We ask the same question of routing: when is a binary viable/spoiled state enough to make good routing decisions, and how many levels are needed once damage accumulates? The prediction is specific. The binary chain should be sufficient when spoilage hazard is memoryless. It should fail, by a measurable amount, when viability depends on cumulative exposure crossing a threshold.

Core Claim

Let item $i$ carry a distribution $\pi_i$ over $k$ quality levels. Each travel leg $a$ driven by vehicle class $v$ applies a transition matrix $P_v(\tau_a)$, where $\tau_a$ is the leg duration. Each intermediate stop applies a door-opening shock matrix $D_v$. For a route prefix ending at the drop-off of item $i$, the probability the item arrives usable is

$$ \Pr(\text{viable}_i) = \pi_i^{\top} \, P_v(\tau_1) D_v P_v(\tau_2) D_v \cdots P_v(\tau_{m}) \, \mathbf{1}_{\text{usable}}, $$

where $\mathbf{1}_{\text{usable}}$ is the indicator vector of acceptable levels. We impose the chance constraint $\Pr(\text{viable}_i) \ge 1-\epsilon$ for a service level $\epsilon$, alongside ordinary customer time windows and capacities.

Because the product is associative, a local-search move that joins a route prefix to a suffix needs only the stored $k \times k$ matrices for each segment. With $k \le 4$, this costs a few dozen multiplications per move. The claim has two parts. First, this vehicle- and route-dependent spoilage constraint can be enforced inside a heterogeneous time-window local search at close to the speed of ordinary time-window checks. Second, the right choice of $k$ is predictable from the physics of degradation. The case $k=2$ is exact under memoryless hazard, while threshold-type cumulative damage requires $k \ge 3$.

Why This Gap Is Real

Several papers motivate the problem. Contextual Stochastic Vehicle Routing with Time Windows solves stochastic-travel-time routing with time windows exactly using branch-price-and-cut. It shows that scenario methods capturing variance beat mean-based prediction. It assumes a homogeneous fleet, draws its randomness from synthetic traffic regimes, and reports runtimes that "increase drastically beyond 50 customers." The traveling purchaser problem for perishable foods models exponential deterioration and identifies loading-door opening as the main spoilage driver. That finding tells us spoilage depends on the route prefix, not only on elapsed time. The paper uses one purchaser and deterministic kinetics. Cooperative Operation of the Fleet Operator and Incentive-Aware Customers in an On-Demand Delivery System: A Bilevel Approach shows how tight deadlines make routes brittle and prevent consolidation. Spoilage deadlines tighten windows in the same way. Goods Consumed During Transit in Split Delivery Vehicle Routing Problems: Modeling and Solution treats time as a resource that the vehicle consumes. We push that view one step further, so that time consumes the cargo.

On heterogeneity, three neural lines break the identical-vehicle assumption but keep cargo inert and travel deterministic. Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem uses one decoder to choose a vehicle and another to choose the next customer, and has no time windows. CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems and USPR: Learning a Unified Solver for Profiled Routing encode vehicle-client affinities and hard binary zoning masks. In our setting the natural "profile" is a refrigeration class. That profile does not simply forbid assignments. It changes the probability that an assignment succeeds.

The biological literature both supplies the method and constrains it. Scalable optimal Bayesian classification of single-cell trajectories under regulatory model uncertainty tracks hidden binary states under noisy observation with a particle filter. We borrow the idea of a small hidden discrete chain beneath continuous reality, but use it to make decisions rather than to classify. Anti-cancer drug administration in cancer treatment under stochastic disturbances approximates chance constraints by Monte Carlo sampling. That is our scenario baseline and our ground-truth evaluator. Julia L. Fleck shows that schedules optimized for the average biological trajectory are brittle, which is exactly the failure a mean-spoilage deadline would reproduce.

Other work warns against trusting two states. Information flow and optimization in transcriptional regulation shows graded signals carry more than one bit. DNA methylation of distal regulatory sites characterizes dysregulation of cancer genes describes "dimmer switch" regulation. These findings are why $k$ is a studied variable here rather than being fixed at 2.

Research Program

We will build a hybrid genetic search with local-search moves for the heterogeneous time-windowed problem. Each route segment stores its time-window summary together with its product of spoilage matrices, one per item class. Feasibility and penalty evaluation of a move then combines stored summaries. We will fit the matrices $P_v(\tau)$ and $D_v$ by matching a ground-truth continuous degradation simulator. That simulator combines temperature-dependent random damage accumulation with random damage from each door opening and differs by refrigeration class. For each $k$, the fit is a least-squares match of level-occupancy probabilities over simulated trajectories. Quality levels are placed at quantiles of damage.

The analysis has a theoretical part. We will show that when the true hazard depends only on the current instant, lumping into viable/spoiled is exact, which is a standard Markov lumpability argument. We will then bound the error of the $k$-level lumping under threshold damage in terms of how finely the levels cover the damage range. The expected consequence is that decision error falls as the levels become finer. The empirical question is how fast, and whether $k=3$ already captures most of the benefit.

Baselines

The naive reference is a heterogeneous time-window solver that ignores spoilage and uses only customer windows, run with the same search code. It measures how much cargo is lost when biology is ignored.

The deterministic-deadline baseline converts spoilage into a fixed per-vehicle-class deadline, set at the $(1-\epsilon)$ quantile of simulated shelf life. It is then solved as an ordinary heterogeneous time-window problem with the same search. This is the obvious engineering answer, and it captures vehicle dependence. What it misses is the dependence on door openings along the route.

The strongest existing method is sample average approximation. It draws $S$ Monte Carlo spoilage scenarios from the ground-truth simulator and evaluates each move's chance constraint by counting, following the Monte Carlo chance-constraint approach of Anti-cancer drug administration in cancer treatment under stochastic disturbances and the scenario methods of Contextual Stochastic Vehicle Routing with Time Windows. The latter reports its conditional and residual variants coming "within 0.1% to 4% of the 'Full Information' benchmark" on augmented Solomon instances. That result is for homogeneous fleets and traffic noise. No reported result was found on Lacuna for heterogeneous-fleet routing with stochastic cargo spoilage.

The neural baseline is USPR retrained with a Monte Carlo spoilage penalty in its reward. On static profiled routing, USPR reports "a gap of only 4.02% relative to the high-performance HGS-PyVRP solver" (USPR), and CAMP reports 5.02% on soft preferences (CAMP).

Every method gets the same instances, the same ground-truth simulator for final evaluation, and the same wall-clock budget per instance. Scenario count $S$ and neural training time will be tuned on held-out instances under a matched tuning budget. Beating sample average approximation means matching its cost within 1% and its evaluated viability rate within 0.5 percentage points at a fraction of the time, or clearly exceeding it at equal time on instances with more than 100 customers.

Two ablations isolate the key ingredients. Sweeping $k$ from 2 to 4, and comparing against direct continuous simulation, isolates the abstraction. Replacing all vehicle-specific matrices with a fleet-average matrix isolates the value of breaking the identical-vehicle assumption.

Why not just…?

Why not just give each vehicle class a fixed spoilage deadline and run a standard heterogeneous time-window solver? This is the real threat, and it will win whenever spoilage is driven only by elapsed time. The perishable-purchaser study found door openings to be the dominant spoilage driver (The traveling purchaser problem for perishable foods). If that holds, an item's usable life depends on how many stops precede it, and no single deadline can express that. The experiment varies the share of damage coming from door shocks versus elapsed time. If fixed deadlines match our method across that range, we will report that the Markov formulation is unnecessary.

Why not just use sample average approximation, which is already near full-information quality? Its accuracy is not in doubt, and it serves as our quality reference. Its cost is. Every local-search move would re-evaluate $S$ scenarios for every item downstream of the change, which scales poorly exactly where Contextual Stochastic Vehicle Routing with Time Windows already struggles. Equal-time comparisons at 200 to 1,000 customers will show whether this cost matters in practice.

Why not just train a neural solver with a spoilage penalty? Neural profiled solvers are fast. However, their gaps widen on large and out-of-distribution instances; USPR reports 14.15% at 1,000 nodes (USPR). A penalty-shaped reward also gives no guarantee that the chance constraint is met. We will measure the neural baseline's violation rate as well as its cost.

Proposed Experiments

We will augment Solomon instances (R1, C1, RC1) with three refrigeration classes and item-level spoilage classes. PVRPLib-style zone and affinity profiles will provide further heterogeneous variants, and scaled instances will run up to 1,000 customers. Metrics are travel cost, the fraction of items delivered usable under 10,000 ground-truth simulations, the chance-constraint violation rate, and solve time.

The decisive check is a two-regime study. Under memoryless hazard, the binary chain should match sample average approximation. Under threshold damage, the binary chain should violate the service level, and $k=3$ should restore it. If $k=2$ succeeds in both regimes, the abstraction question has a boring answer, and we will report it as such. A second check is the fleet-averaged ablation, which tells us whether vehicle-dependent spoilage changes which vehicle serves which customer, measured by the assignment overlap between the two solutions. A third check is the door-shock sweep against fixed deadlines, which decides whether route-dependent spoilage is a real effect or a modeling nicety.