In order to satisfy the user’s travel needs while efficiently completing the battery replacement for urban shared e-bikes system, considering the practical situation of multi-type imbalanced stations, multiple visits to stations, multi-depots and heterogeneous truck fleets, a mixed integer programming model for the joint optimization problem of repositioning and battery replacement for shared e-bike was constructed. A greedy-genetic hybrid heuristic algorithm was designed, initial solutions were generated efficiently by introducing the maximum operation number, the next station selection strategy and the operation priority. Several types of crossover and mutation operations were designed to enhance the optimization performance of the algorithm. A repair strategy based on optimal station replacement was proposed to quickly correct infeasible solutions. Experiments were carried out based on the shared electric bicycle data in Tongxiang city, Zhejiang province. The results show that the proposed algorithm outperforms the simulated annealing algorithm remarkably, compared with the single optimization, the joint optimization method reduces the total fleet repositioning duration, the latest repositioning time and the total number of station visits by 16.78%, 27.12% and 12.79%, respectively. By jointly optimizing the repositioning and battery replacement tasks, the total number of station visits can be reduced, and the nighttime operation duration can be effectively shortened. The research results can provide theoretical support and practical reference for the operation and management of shared electric bike enterprises.