Electric Vehicle Fleets: Scalable Route and Recharge Scheduling Through Column Generation
提出一种可扩展的列生成方法，用于大规模电动车队的路线与充电调度，通过多图重构、双向定价、稀疏化及启发式策略，在数百个请求的问题上显著优于现有算法。
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 because of 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 nondominated charging arcs, (ii) an efficient bidirectional 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. Funding: This work was supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 08528/2018-2 and 315361/2020-4], Coordenação de Aperfeiçoamento de Pessoal de Nível Superior [Finance Code 001], and Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro [Grants E-26/010.002232/2019 and E-26/202.790/2019]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.1199 .