  Motivated by widespread electrification targets, this paper studies an
electric routing-scheduling problem (ERSP) that jointly optimizes
routing-scheduling and charging decisions. The ERSP is formulated as a
semi-infinite set-partitioning model, where continuous charging decisions
result in infinitely-many path-based variables. To solve it, we develop a
column generation algorithm with a bi-level label-setting algorithm to
decompose the pricing problem into (i) a first-level procedure to generate
subpaths between charging stations, and (ii) a second-level procedure to
combine subpaths into paths. We formalize subpath-based domination properties
to establish the finite convergence and exactness of the column generation
algorithm. We prove that the methodology can handle modeling extensions with
heterogeneous charging costs (via dynamic re-optimization of charging
decisions) and algorithm extensions to tighten the relaxation using ng-routes
and limited-memory subset-row inequalities (via augmented domination criteria).
Computational results show that the methodology scales to large instances,
outperforming state-of-the-art column generation algorithms. From a practical
standpoint, the methodology achieves significant cost reductions by jointly
optimizing routing-scheduling and charging decisions and by capturing
heterogeneous charging costs.
