Modeling and Solving the Traveling Salesman Problem with Speed Optimization for a Plug-In Hybrid Electric Vehicle.

This article investigates a variant of the Traveling Salesman Problem (TSP) that incorporates speed optimization and operation mode selection for plug-in hybrid electric vehicles (PHEVs), aiming to minimize total energy consumption cost. Two mixed-integer nonlinear programming models are developed—one with continuous speed variables and another with discretized speeds—and are solved using a branch-and-cut algorithm enhanced by valid inequalities to improve computational efficiency. Extensive computational experiments demonstrate that the proposed joint optimization of route, speed, and operation modes outperforms sequential methods and fixed-speed models, achieving optimal solutions for realistically sized instances within reasonable times. The study also extends the model to include charging stations at customer locations, showing potential further reductions in energy costs despite increased problem complexity. The models and solution methods are applicable to hybrid electric vehicles (HEVs) as well and outperform existing heuristic approaches in both solution quality and runtime.