Synchronising electric vehicle fleet’s routing and recharging with recharge pile renting at external stations: a column generation-based approach

While deploying electric vehicle (EV) fleet, the local logistics company faces challenges in ensuring an efficient and cost-effective recharging supports, but the reliance on public recharge infrastructure often causes uncertain queuing times. Given the correlations between fleet’s operation and the number of piles rented from external stations, this paper investigates an exclusive recharge pile renting problem at external recharge stations, integrating with fleet’s routing and recharge scheduling. A mixed-integer linear program is formulated, minimizing the recharge piles’ renting costs and fleet’s operational expenses. EVs’ partial recharge approach is modelled to capture energy management features. A tailored column generation-based approach is designed. The master problem optimizes the external stations to collaborate with and the number of piles to rent, which is affected by fleet’s routes and recharge schedules optimized in the subproblem. An improved label-correcting algorithm with two proposed heuristic strategies is designed, enabling EVs to recharge energy amounts flexibly with a set of alternative recharge schedules for respective route. Computational experiments validate that the proposed strategies reduce pile renting costs by up to 33.3%, and reduces total operational costs by up to 9.90% compared to full recharging. Managerial insights reveal the impacts of exclusive piles’ renting and partial recharge approach.