Last-mile delivery has been a critical bottleneck in the logistics area due to its high operating costs. The differences between urban and rural delivery scenarios further contribute to high operating costs in last-mile delivery. In this paper, a bi-level programming model is built for the multi-period heterogeneous fleet vehicle routing problem with self-pickup point selection (MHFVRP-SPS) in urban and rural last-mile delivery scenarios. This model fully considers two decision-makers and the interaction of their decisions. To solve the MHFVRP-SPS in urban and rural last-mile delivery scenarios, an offline learning algorithm is first designed to partition the delivery area into regions, which can reduce the size and difficulty of the problem and ensure the workload balance between the regions. Then, a novel bi-level particle swarm-adaptive large neighborhood search (BL-PSO-ALNS) algorithm is designed to solve the MHFVRP-SPS for each region. The results of a real case show: the offline learning algorithm can effectively balance the workload between the regions and has good performance in clustering performance and balancing performance; the BL-PSO-ALNS algorithm can effectively optimize the operating cost, the vehicle mileages, and the vehicle full load rate in urban and rural terminal delivery operations, and has good convergence; an increase in the number of regional divisions or the capacity of self-pickup points does not always reduce operating costs, decision-makers need to make sound decisions about the range of both. These findings can provide important decision guidance for urban and rural last-mile delivery operations.