Joint routing and charging for electric trucks with station-varying charging power and electricity price

Truck electrification is a key strategy to reduce carbon emissions in the freight transportation sector. However, long-haul shipping tasks of electric trucks face great operational challenges, due to inadequate battery capacity, overlong charging time, and insufficient charging opportunity. To minimize the overall operational cost while guaranteeing no driving range violation in long-distance trips, this paper considers a joint routing-charging problem for individual electric trucks. This problem takes into account the variations in charging power and electricity price at different charging stations and allows partialrecharging to make decisions of minimizing the sum of shipping time, charging time, and out-of-pocket charging cost. Two mixed integer linear programming models are formulated, one based on original node-arc networks and another on station-subpath metanetworks, and a Benders decomposition algorithm is designed and implemented for each of these formulations. For the Benderssubproblem, a so-called recursive path-splitting algorithm that is of the polynomial-time complexity is proposed to computethe optimal charging decisions along a given route, while the Benders master problem is reformulated as a special multi-objective shortest path problem and solved by a multi-criterion label-correcting algorithm. Computational experiments demonstratethat all the proposed Benders decomposition procedures outperform Gurobi, while the metanetwork-based decomposition algorithm enjoys significant computing time savings compared to the network-based algorithm. Through a case study of a national highwaynetwork, we also justify that separating routing and charging decisions or ignoring station-varying charging specifications inevitably results in much higher system costs.