The surge in e-commerce and urban logistics has heightened the demand for efficient and sustainable last-mile delivery solutions. Drone-assisted vehicle routing offers significant potential but faces challenges such as limited drone range, payload constraints, and the need to balance environmental and service quality objectives. This paper formulates the Multi-Objective Optimization Vehicle Routing Problem with Drones (MOO-VRPD), which jointly minimizes greenhouse gas emissions and customer dissatisfaction. To address its NP-hard nature, we introduce a hybrid algorithm, NSGA-II-VNS, which combines the global exploration capabilities of evolutionary search with the local refinement of Variable Neighborhood Search. By maintaining a diverse set of Pareto-optimal solutions and systematically enhancing them through structured neighborhood exploration, NSGA-II-VNS achieves a robust balance between exploration and exploitation. Comprehensive experiments on benchmark datasets demonstrate the algorithm’s effectiveness in producing high-quality solutions that reduce emissions while improving delivery satisfaction, underscoring its potential for advancing sustainable drone-assisted logistics.