Multi-Trip Algorithm for Multi-Depot Rural Postman Problem With Rechargeable Vehicles

Abstract Autonomous vehicles have emerged as transformative technologies with vast implications across various domains, including surveillance. However, they are constrained by battery limitations, which can hinder their usability and efficiency. Designing algorithms to efficiently utilize them optimizing their battery usage, is crucial to unlocking their full potential. This paper addresses this challenge by studying an extension of the rural postman problem with multiple depots and rechargeable and reusable vehicles that can make multiple trips but have limited battery capacity. It presents a new Mixed Integer Linear Programming (MILP) formulation to find optimal solutions to the problem and proposes a new heuristic called the multi-trip (MT) algorithm. The paper describes the results of a study that tested the MT algorithm, other heuristics, and the MILP formulation on both benchmark instances and larger, real-world instances generated from road maps. Our results show that the MT algorithm found feasible solutions for every instance and produced better solutions than heuristics from the literature on 38 of the 39 instances that were tested. Due to its requirements for memory and computing time, the Gurobi optimizer used for solving the MILP formulation could not find optimal solutions for the largest instances that we tested. This research contributes to enhancing the efficiency and effectiveness of battery-operated unmanned by developing new heuristics to address the challenge of battery limitations.