The Routing-and-Driving Problem for Plug-in Hybrid Electric Vehicles

The routing-and-driving problem for plug-in hybrid electric vehicles (PHEVs) is an extension of the vehicle routing problem with time windows, where routing involves determining optimal routes and recharging decisions for a fleet of PHEVs, whereas driving involves choosing the speed and operating mode on each road segment traveled by a vehicle. Specifically, four driving modes are considered: fuel only, electricity only, a combination of fuel and electricity, and energy recuperation, which returns energy to the battery. We consider two variants of the problem where the speed variables are either continuous, which results in a nonlinear model, or discrete, which represents the case when speeds are chosen from a predetermined set. To solve these two models, we propose a set of valid inequalities to strengthen the continuous linear programming relaxation, and we use a tailored branch-and-cut algorithm. Extensive computational experiments demonstrate the efficiency of the proposed solution methods, which can optimally solve instances with a realistic number of customers and recharging stations. In addition, we show that incorporating speed optimization can significantly reduce the energy consumption costs of a PHEV fleet compared with using fixed speeds.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: This work was supported by the GuangDong Basic and Applied Basic Research Foundation [Grant 2026A1515030009].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1016) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.1016). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.