Parcel lockers effectively resolve the mismatched handover times between customers and couriers. However, with the widespread deployment of parcel lockers, selecting a locker convenient for customer handover has become one of the key factors influencing satisfaction in last-mile delivery services. To address this challenge, this paper proposes a multi-vehicle coverage delivery problem considering customer satisfaction. At the problem level, a questionnaire survey approach was employed to model the customer satisfaction, thereby establishing the mathematical model for this problem. At the methodological level, a reinforcement learning-driven evolutionary algorithm is proposed. Firstly, a hybrid heuristic method is designed to generate a high-quality initial population. Secondly, nine neighbourhood operators and a greedy repair heuristic are devised based on the problem's characteristics to efficiently search for satisfactory feasible solutions. Subsequently, a reinforcement learning-driven search mechanism is proposed to adaptively select suitable operators. Finally, a state representation method based on a monotonic descent benchmark function is designed to guide the convergence process of the agent learning algorithm. Simulation results demonstrate that the proposed algorithm achieves high-quality solutions across problems of varying scales, exhibiting superior computational performance compared to benchmark algorithms and solvers. Ablation experiments reveal that the state function-guided reinforcement learning search mechanism enhances algorithmic performance by an average of 5%.