Perishable Vehicle Routing

The goal of Perishable Vehicle Routing is getting fresh food to its destination before it spoils, balancing transportation costs with the value of remaining shelf life.

The VRPTW — Classical Formulation

The Vehicle Routing Problem with Time Windows (VRPTW) assigns a fleet of vehicles to service a set of customers $V = \{1, 2, \dots, n\}$ within specific time windows $[a_i, b_i]$ . Let $x_{ijk} = 1$ if vehicle $k$ travels from node $i$ to $j$ , and $t_{ik}$ be the arrival time.

Extensions for Perishability: Quality Decay

For fresh foods, standard VRPTW is extended to include quality decay. The quality $q_{ij}$ of a product traversing edge $(i,j)$ decays as a function of time $\Delta t_{ij}$ and temperature $T$ :

q_{ij} = q_i \cdot e^{-k(T) \Delta t_{ij}}

where $k(T)$ is the Arrhenius reaction rate for the specific food. This links directly to PerishableInventoryTheory where remaining shelf life determines value.

Multi-Compartment Vehicles

Grocery delivery often requires multi-compartment vehicles capable of maintaining frozen ( $-18^\circ\text{C}$ ), chilled ( $4^\circ\text{C}$ ), and ambient ( $20^\circ\text{C}$ ) zones. This adds a dimension to the vehicle capacity constraint:

\sum_{i \in V} d_{ic} x_{ijk} \leq C_{kc} \quad \forall k, \forall c \in \{F, C, A\}

Objective Functions

While standard routing minimizes distance, perishable routing optimizes a multi-objective function:

\min Z = w_1 \sum_{i,j,k} c_{ij} x_{ijk} + w_2 \sum_{i} W(q_i) - w_3 \sum_i RSL(q_i)

Where $c_{ij}$ is travel cost, $W$ is the waste cost, and $RSL$ is the remaining shelf life.

Solution Methods

Because the VRPTW is NP-hard, solving it with quality constraints requires advanced techniques:

Exact: Branch-and-price with specialized labeling algorithms for the pricing subproblem.
Heuristic: Adaptive Large Neighborhood Search (ALNS) and metaheuristics (e.g., genetic algorithms).

Real-Time Rerouting

Modern cold chains use IoT temperature sensors. If a sensor indicates a refrigeration failure or accelerated decay, real-time rerouting dynamically reassigns the truck to a closer distribution center (see ColdChainNetworkDesign).

Last-Mile for Fresh Food

Last-mile delivery is the most expensive and time-sensitive leg. Strategies include:

Dark Stores and Micro-Fulfillment Centers (MFCs): Placing inventory closer to the urban core.
Crowd-Shipping: Utilizing independent drivers for rapid point-to-point delivery of highly perishable items like hot food or fresh sushi.

Worked Example: A delivery route from a DC to 3 supermarkets. Total distance cost is $150. If routed A $\to$ B $\to$ C, arrival at C is at $t=4$ hours, resulting in a $5\%$ quality drop for strawberries (valued at loss of $50). If routed C $\to$ B $\to$ A, distance cost increases to $180, but arrival at C is $t=1$ hour, dropping quality loss to $10. The optimal route changes based on the combined transportation and spoilage cost ($ 200 vs $190).