Dynamic Multiple Vehicle Routing under Energy Capacity Constraints

The multiple vehicle routing problem (mVRP) concerns the scheduling of multiple vehicles so as to visit some locations of interest. We study a dynamic version of mVRP where the travel costs are not a priori known and may vary at runtime. Moreover, we introduce energy-related constraints which make the problem more complex. Vehicles have only finite energy reserves, which gradually diminish as they move between different locations, but can also gain some energy at specific depot locations. The objective is to visit all locations of interest as fast as possible without any vehicle exhausting its energy. We propose an online algorithm based on the Large Neighbourhood Search (LNS) heuristic. We evaluate the algorithm for different topologies and degrees of vehicle autonomy. Our results show that it achieves significantly better results than an offline algorithm that produces a safe schedule based on worst-case cost estimates.