Coverage-Based Service Vehicle Routing when only some Tasks are Known in Advance

Abstract

In this paper we deal with a common problem found in the operations of security and preventive/corrective maintenance services: that of routing a number of mobile resources (vehicles) to perform foreseen and unforeseen tasks during a shift. We define the (Stochastic Service Team Orienteering Problem) SSTOP as the problem of making a routing strategy to maximize the expected weighted number of tasks served within the specified time-windows. To obtain solutions to this problem, we propose to solve successively the Coverage Team Orienteering Problem with Time Windows (C-TOPTW). The C-TOPTW considers information related to known tasks and also information about the arrival process of new unforeseen tasks. We find that the information about the arrival process of new unforeseen tasks is of value in generating routes for vehicles to maximize the expected proportion of tasks accomplished within the specified time windows.