PHEV Routing with Hybrid Energy and Partial Charging: Solved via Dantzig–Wolfe Decomposition

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.