A Maturity-Aware Proximal ADMM with NG-Route Relaxation for Dynamic Inventory Reallocation in a Multi-Echelon Mandarin Cold-Chain Network

The Vehicle Routing Problem with Time Windows (VRPTW) takes on a structurally distinct form when the goods being routed undergo first-order quality decay during transport. In this setting, distance minimisation alone underestimates the true economic cost. A per-customer minimum-quality acceptance constraint further introduces a non-linear feasibility condition that does not appear in the classical formulation. This paper addresses such a setting in the context of loose-skin citrus fruit (e.g., mandarins) distribution, where stock has already undergone several days of cold storage at the origin warehouse, and remaining shelf life makes retail time windows binding rather than decorative. We formulate a Maturity-Aware Multi-Echelon Dynamic Reallocation Vehicle Routing Problem with Time Windows (MA-MEDR-VRPTW) on a three-echelon network (origin warehouse → distribution centres → stores) over a seven-day rolling horizon. A first contribution shows that the minimum-quality acceptance constraint admits an analytic transformation into a time-window tightening, which removes per-extension exponential evaluations from the subproblem solver. The algorithmic contribution is a proximal alternating direction method of multipliers (ADMM) with NG-route relaxation (padmm-ma) whose quality-loss weight is updated by a residual-balancing rule and is decoupled from the outer reallocation linear program (LP) through approximate dynamic-programming-style marginal costs. On twelve Solomon-derived mandarin instances (72 feasible algorithm–instance combinations), padmm-ma returns a mean seven-day cost of 12,638 CNY against 11,753 CNY for a subgradient baseline (+7.5%) at statistically indistinguishable arrival quality (paired Wilcoxon p=0.077 for q¯arr), while cutting mean wall-clock time from 350 to 23 seconds (about 15×). The method, therefore, reads as a fast operational heuristic for daily re-planning. An ablation, an exact-MIP benchmark on tractable subproblems, and a scale extension to n=100 customers round out the validation.