  Time-dependent (or temporal) properties may arise in many practical static
network search problems, for example routing and scheduling of railway track
inspection where availability of track for inspection depends on the
rail-schedule. In the absence of side constraints this routing and scheduling
problem is a multi-agent rural postman problem on a temporal directed network;
having temporal attributes motivated from railway track unavailabilities. This
work presents a novel Mixed Integer Linear Programming (MILP) formulation model
for a Multi-agent Temporal Rural Postman Problem (MTRPP), and proposes theory
for temporal graphs to support the model. A modified Benders' decomposition
algorithm is also proposed to address the non-convex unavailability constraints
occurring in its sub-problems. Furthermore, a polynomial time algorithm is
designed to address this sub-problem, while restraining the NP-Hard part to the
master problem. A simulation study showing application in rail-track inspection
using track-based-agents is presented, alongside comparison study showing
improved results in smaller and sparser graphs compared to Time-Dependent Rural
Postman Problem (TDRPP) which is developed over temporal attributes arising due
to congestion in roadway networks.
