Hybrid Metaheuristic Approaches for the Multi-Depot Rural Postman Problem With Rechargeable and Reusable Vehicles

Abstract

The limited battery life of unmanned autonomous vehicles and ground robots necessitates efficient routing strategies that enable periodic recharging to extend operational range. To address this issue, this paper studies an extension of the classical rural postman problem, where a fleet of rechargeable vehicles with limited battery capacity stationed at multiple depots must traverse required edges in a weighted graph through multiple trips, minimizing the total travel time. Existing heuristic approaches yield poor solutions with a high optimality gap due to the NP-hard nature of the problem. We propose a new Mixed Integer Linear Programming (MILP) formulation for the problem, which is used to obtain optimal vehicle routes and introduce new techniques to enhance existing metaheuristics, such as simulated annealing, tabu search, and genetic algorithm, to solve the problem. The routes obtained by testing the metaheuristics on benchmark and real-world instances based on roadmaps were compared to the optimal solution. Experimental results for benchmark instances showed that the simulated annealing and genetic algorithm kept the optimality gap within 1%. For real-world instances, simulated annealing and tabu search improved route quality by 54.1% and 49.9%, respectively, over routes obtained by only using heuristic approaches.

Keywords

• Multi-vehicle route planning
• capacity constraints
• metaheuristics
• rural postman problem
• rechargeable and reusable vehicles