  The rise of battery-powered vehicles has led to many new technical and
methodological hurdles. Among these, the efficient planning of an electric
fleet to fulfill passenger transportation requests still represents a major
challenge. This is due to the specific constraints of electric vehicles, bound
by their battery autonomy and necessity of recharge planning, and the large
scale of the operations, which challenges existing optimization algorithms. The
purpose of this paper is to introduce a scalable column generation approach for
routing and scheduling in this context. Our algorithm relies on four main
ingredients: (i) a multigraph reformulation of the problem based on a
characterization of non-dominated charging arcs, (ii) an efficient
bi-directional pricing algorithm using tight backward bounds, (iii)
sparsification approaches permitting to decrease the size of the subjacent
graphs dramatically, and (iv) a diving heuristic, which locates near-optimal
solutions in a fraction of the time needed for a complete branch-and-price.
Through extensive computational experiments, we demonstrate that our approach
significantly outperforms previous algorithms for this setting, leading to
accurate solutions for problems counting several hundreds of requests.
