The introduction of the peak-valley time-of-use (TOU) electricity price policy creates opportunities to further optimize delivery routes and charging strategies for logistics distribution services using electric vehicles. Accordingly, based on the TOU policy, this paper constructs an integer programming mathematical model with comprehensive cost objectives for the electric vehicle distribution route optimization problem with soft time windows in logistics. A genetic algorithm-adaptive large neighborhood search (GA-ALNS) is designed to solve the above problem. Numerical examples of different scales verify the effectiveness and applicability of the proposed algorithm. The impacts of the TOU policy on operational strategies are compared and analyzed from multiple perspectives, including operating costs, charging costs, charging schemes, and electricity prices in different cities. Model calculations and case analyses draw the following conclusions: GA-ALNS is more effective in solving the soft time window electric vehicle routing optimization problem under the TOU policy. The computational results reveal that the TOU policy expands the optional range of vehicle charging strategies as the number of customer nodes rises, effectively reducing the total operating cost. On the basis of these findings, several heuristic recommendations are put forward to provide theoretical support for logistics enterprises to make operational decisions for cost reduction.