The global shift towards sustainable transportation is centered around the growth of electric vehicles (EVs) primarily due to their zero tailpipe emissions. To facilitate the seamless transition from non-EVs to EVs and to alleviate the range anxiety experienced by EV users, substantial improvements in charging infrastructure is required. This involves the development of new fast charging stations and battery-swapping facilities. This research focuses on a step ahead and proposes an innovative solution by providing recharging and battery swapping services to EV users at their preferred time and location with mobile EV recharging and mobile battery swapping vans. The problem is formulated as a Multi-Depot Capacitated Vehicle Routing Problem (VRP) considering Hard Time Windows and Simultaneous Pickup and Delivery, using integer linear programming. The objective is to minimize the total cost of routing the recharging and battery swapping vans from charging stations to customer locations by satisfying the customer’s requirements effectively. The proposed mathematical formulation was tested on a small set of 8 customers and solved using Gurobi solver. Furthermore, this NP-hard problem is tackled by developing heuristics known as large neighborhood search aimed at scalability for larger instances of the problem. The heuristics was successfully implemented and tested for the same small set of 8 customers and a larger instance with two sets (100,200) customers and different depots generated randomly. Therefore, this study introduces an innovative approach to tackle challenges related to EV adoption thereby contributing to a more sustainable and accessible future for electric mobility.