A 2-stage method for a field service routing problem with stochastic travel and service times

•We introduce the field service routing problem with stochastic travel and service times.•We propose a two-stage method for solving this new problem.•In the planning stage, we build routes with mandatory and then we insert optional customers.•In the execution stage, we use dynamic programming algorithms to define the optimal policy to face stochasticity.

In this paper, we consider a specific variant of the field service routing problem. It consists in determining vehicle routes in a single period to serve two types of customers: mandatory and optional. Mandatory customers have to be served within a specified time window whereas optional customers may be served (or not) within the planning horizon. For more realism, we assume that service as well as travel times are stochastic and also that there are multiple depots. The objective is to visit as many optional customers as possible while minimizing the total travel time. To tackle this problem, we propose a 2-stage solution method: the planning stage and the execution stage. We decompose the planning stage into two phases: the design of a skeleton of mandatory customers and the insertion of optional customers in this skeleton. In the execution stage, we proceed to a real-time modification of the planned routes to face stochastic travel and service times and to enable time windows to be respected.