Load-Aware Metaheuristics for Green Multi-Depot Heterogeneous-Fleet Vehicle Routing: When Does the Load Term Matter?

Load-dependent fuel models are widely used in green vehicle routing together with dedicated metaheuristics. We examine when modeling the load changes decisions in the green multi-depot heterogeneous-fleet vehicle routing problem with time windows. In more than 1000 proven optimal solutions of a mixed-integer linear program on small instances, load-aware and load-independent optima coincide at benchmark demands and differ in one to three of nine instances under higher demand or tighter time windows. Most differences only reorder visits and change CO2 by about 1%; large differences arise only from changes in the vehicle mix, which a one-factor sensitivity analysis traces to higher demand combined with fixed costs or fuel rates favoring larger vehicles and which can lower or raise emissions. Under the assumed cost ratios, carbon prices near current allowance prices change no optimal solution. On 100-customer instances, a load-aware adaptive large neighborhood search first trails a hybrid genetic search by about 15%; a route-merge move reduces the gap to about one percentage point at equal running time. Within the same algorithm, the load-dependent objective yields only small gains over a load-independent surrogate, significant only on 200-customer instances. In the tested settings, fleet-level search matters more than the load term.