A local search algorithm to combined maintenance routing optimization problem for vehicles subject to failures

This work focuses on the problem of planning and scheduling preventive maintenance operations where the vehicles travel over long distances between locations in a difficult environment favoring a probability of failure of critical components. We consider a set of customers that are geographically distributed over a region and a set of vehicles to serve the customers. These vehicles are subject to unforeseen failures that result in downtime and hence loss of productivity. To reduce the occurrence of these unforeseen downtimes, a Preventive Maintenance (PM) operation is scheduled with a certain frequency. When a vehicle fails suddenly, the maintenance crew travel to the vehicle locations and must perform a repair operation, called Corrective Maintenance (CM). Given a planning horizon, this problem consists in determining a routing-maintenance policy for all vehicles and customers. The problem aims to minimize the total routing costs (e.g., distances, times, etc.) plus maintenance cost for the routing view. To solve this problem, we use a solution approach which integrates the model called the Combined Maintenance and Routing Model (CMR) into the local search (LS) approach. Firstly, with the assumption of zero waiting times, we determine a maintenance schedule with CMR model. Secondly, using the output from the CMR, a LS is executed to find the routes to serve all customers and perform the scheduled PM operations for the vehicles. We present some results, comparing with the mixed integer programming model for a set of instances with our proposed method.