Multi-Objective EV Routing with Recharging, Battery-Swapping, and K-Means Station Siting for Ride-Hailing Fleets in Medan City

Abstract

Electric vehicle adoption requires routing strategies that address travel efficiency and battery-energy constraints. This study develops a Multi-Objective Electric Vehicle Routing Problem (EVRP) model for two-wheeled electric ride-hailing services in Medan City, Indonesia. The model minimizes total travel distance and operational energy cost while incorporating recharging and battery-swapping strategies and identifying candidate sites for public charging stations (SPKLU) and battery-swapping stations (SPBKLU). It integrates route construction, battery-energy feasibility, recharge–swap assignment, multi-objective evaluation, and spatial clustering within one decision-support framework. Secondary data comprise one depot, 200 service points, four existing SPKLU, and nine existing SPBKLU. The Clarke–Wright Savings algorithm generates six routes, while the State of Charge (SOC) model evaluates battery feasibility. Twenty recharge–swap assignments are evaluated using the weighted sum method, and Pareto analysis identifies five non-dominated solutions. Under the cost-oriented weighting scenario, recharging is assigned to Routes 1, 4, and 6 and battery swapping to Routes 2, 3, and 5, yielding a travel distance of 327.79 km and an operational cost of IDR 39,131. This solution requires four SPKLU and three SPBKLU points, which K-Means clustering reduces to three and two candidate locations, respectively, providing guidance for battery-replenishment infrastructure planning.