Multi-Objective Optimization for the Time-Dependent Green Vehicle Routing Problem with Time Windows

In the context of urban distribution, given the complexity of express delivery and the variability of distribution conditions, vehicle routing problems with time-dependent characteristics have received increasing attention. This study incorporates a cross-period travel time estimation method for road segments that accounts for temporal and weather-dependent variations in vehicle speed. Building upon this foundation, this study establishes an multi-objective optimization model for the green vehicle routing problem that systematically incorporates intricate constraints, including time-varing vehicle speed, fuel consumption, carbon emissions, and customer servive time windows. This model aims to achieve three primary objectives: (1) minimizing the fleet size, (2) minimizing the overall delivery expenses, which include fuel consumption and carbon emissions, and (3) maximizing the average customer satisfaction. To solve this model, we develop an improved Non-Dominated Sorting Genetic Algorithm III (INSGA-III). To effectively prevent the algorithm from becoming trapped in local optima, we propose a dual-criteria selection mechanism. Meanwhile, we introduce a destroy-and-repair variable neighborhood search strategy to enhance the algorithm’s optimization capability under complex constraints. Experimental evaluations conducted on Solomon benchmark instances as well as real-world case studies indicate that the proposed INSGA-III algorithm surpasses widely utilized multi-objective optimization methods across all assessed performance metrics. This highlights the significant potential of the presented INSGA-III algorithm for practical applications in urban delivery scenarios, which is closely linked to the sustainable development of cities.