  This paper studies an extension of the rural postman problem with multiple
depots and rechargeable and reusable vehicles capable of multiple trips with
capacity constraints. This paper presents a new Mixed Integer Linear
Programming (MILP) formulation to find optimal solutions to the problem. The
paper also proposes a new heuristic called the multi-trip algorithm for the
problem whose solutions are compared against solutions of heuristics from
literature and the optimal solutions obtained from the MILP formulation by
testing them on both benchmark instances and real-world instances generated
from road maps. Results show that the proposed heuristic was able to solve all
the instances and produce better solutions than heuristics from the literature
on 37 of 39 total instances. Due to the high requirement of memory and compute
power, the Gurobi optimizer used for solving the MILP formulation, although it
produced optimal solutions, was only able to solve benchmark instances but not
real-world instances.
