This study addresses the Plug-in Hybrid Electric Vehicle Routing Problem (PHEVRP), an extension of the classical VRP that incorporates energy mode switching and partial charging strategies. We propose a novel routing model that integrates three energy modes—fuel-only, electric-only, and hybrid—along with partial recharging decisions to enhance energy flexibility and reduce operational costs. To overcome the computational challenges of large-scale instances, a Dantzig–Wolfe decomposition algorithm is designed to efficiently reduce the solution space via column generation. Experimental results demonstrate that the hybrid-mode with partial charging strategy consistently outperforms full-charging and single-mode approaches, especially in clustered customer scenarios. To further evaluate algorithmic performance, an Ant Colony Optimization (ACO) heuristic is introduced for comparison. While the full model fails to solve instances with more than 30 customers, the DW algorithm achieves high-quality solutions with optimality gaps typically below 3%. Compared to ACO, DW consistently provides better solution quality and is faster in most cases, though its computation time may vary due to pricing complexity.

This study investigates a variant of the shortest path problem (SPP) tailored for plug-in hybrid electric vehicles (PHEVs), incorporating two practical features: hybrid energy mode switching and partial charging. A novel modeling framework is proposed that enables PHEVs to dynamically switch between electricity and fuel along each edge and to recharge partially at charging stations. Unlike most prior studies that rely on more complex modeling approaches, this paper introduces a compact mixed-integer linear programming (MILP) model that remains directly solvable using commercial solvers such as Gurobi. To address large-scale networks, a customized labeling algorithm is developed for an efficient solution. Numerical results on benchmark networks show that the hybrid mode and partial charging can reduce total cost by up to 29.76% and significantly affect route choices. The proposed algorithm demonstrates strong scalability, solving instances with up to 33,000 nodes while maintaining near-optimal performance, with less than 5% deviation in smaller cases.