Shortest Route for Electric Vehicle Routing Problem Using Branch and Cut Algorithm

Abstract

This study addresses the Electric Vehicle Shortest Route Problem (EV SRP) formulated as a range-constrained Travelling Salesman Problem (TSP) using the Branch and Cut (B&C) algorithm, an exact optimization method designed to iteratively improve linear programming solutions by eliminating infeasible subtours and enforcing route feasibility. The routing network was modeled using five strategic EV charging station locations across Johor, including highway rest stops, urban charging hubs, and commercial-area stations. Results from simulation show that the B&C algorithm successfully generated a fully connected and feasible shortest EV tour with a total distance of 205.60 kilometers while requiring one optimal charging stop at Batu Pahat Mall to ensure completion under the 150-kilometer battery constraint. The study further evaluates the algorithm’s performance in guaranteeing feasibility through subtour elimination and battery-aware branching, highlighting its advantage over conventional shortest-path methods that do not inherently prevent disconnected cycles in TSP routing. The findings demonstrate the effectiveness of the Branch and Cut algorithm in producing feasible, optimized, and energy-valid EV routes within a manageable state-level charging network, offering practical insights for EV route planning and establishing a foundation for future expansion into larger Malaysian charging infrastructures.