A Problem Space Search Metaheuristic with Adaptive Regret Insertion for Sustainable Low-Carbon Vehicle Routing

This study investigates a sustainable vehicle-routing problem in which a heterogeneous fleet serves geographically dispersed customer demands from a central distribution facility. The problem simultaneously minimizes transportation costs and CO2 emissions, with deliveries performed by either in-house or externally rented vehicles. A bi-objective mixed-integer programming (MIP) model is formulated, and two lexicographic anchor solutions are generated using opposite objective-priority orderings. A tailored Problem Space Search (PSS) metaheuristic is evaluated on five application-informed simulated datasets containing 10–50 nodes. Six parameter configurations combining m ∈ {10, 20} and β ∈ {0.15, 0.20, 0.25} are evaluated using 30 random seeds. For cases where CPLEX certifies primary-objective optimality, the mean PSS deviation ranges from 0.00% to 7.81%, while the best PSS run remains within 3.20% of the optimum in every case. On the 50-node instance, each PSS run improves the time-limited CPLEX primary incumbent under both priority orderings, although unresolved CPLEX gaps preclude near-optimality claims. PSS also improves the embedded heuristic in most cases, while increasing m generally improves solution quality at additional computational cost. The results demonstrate the computational effectiveness of PSS for the sustainable fleet-assignment and routing instances examined.