In public transit, the multi-depot electric vehicle scheduling problem (MDEVSP) involves assigning a fleet of electric buses to a set of timetabled trips while addressing constraints related to battery recharging. A common approach to solving this problem leverages column generation, wherein a master problem identifies a base solution, and subproblems generate additional schedules to enhance it. These subproblems are often modeled as shortest path problems on a graph, where nodes represent trips and potential recharging opportunities. Prior works have used time-space networks with dynamic selection of recharging opportunities. However, this network type introduces practical limitations, such as the inability to enforce ad-hoc constraints on trip sequences. Recently, Gerbaux et al. (2025) proposed a machine-learning-based method to accelerate the resolution of the subproblems by heuristically reducing their size. While effective, this approach raises concerns in industrial applications, including data privacy for customers and compliance with legal regulations. In this context, we propose a novel approach to model the subproblems within a column-generation-based algorithm for the MDEVSP. Our contributions are as follows: (1) A new graph formulation that preselects recharging opportunities, offering greater flexibility in trip assignment and enabling the integration of ad-hoc constraints; (2) A constructive meta-heuristic, based on a greedy randomized adaptive search procedure, to reduce the subproblem size without relying on machine learning or historical data; (3) Additional pruning rules to further reduce the subproblem size. Experimental results, conducted on hundreds of realistic instances derived from real bus lines in Montreal, show that our approach achieves comparable performance to the state-of-the-art method by Gerbaux et al. (2025), while avoiding the use of machine learning.