Thesis of Sixtine Binart

Real-time optimization of technician tours

The field service routing problem consists in assigning the visits of technicians to clients in order to satisfy their requests for service activities such as maintenance. When planning service routes, companies have to face hazardous travel and service times. Therefore, in this thesis, we deal with a variant of the single-period field service routing problem in which travel and service times are stochastic. It is the field service routing problem with multiple depots, time windows, stochastic travel and service times and priority within customers (distinguishing mandatory and optional customers). To solve this problem, we propose three different methods. In the first one, we first build routes containing only mandatory customers and then, we insert optional customers in these routes. The second one is a heuristic method based on column generation consisting in generating a set of valuable routes for each vehicle and then in selecting one route per vehicle. The last method is a branch and price algorithm, based on the second method, in which the subproblem consists in finding feasible routes for a given vehicle, whereas the master problem consists in selecting routes while ensuring that customer's priority is respected. After each of these methods, in order to evaluate the quality of these solutions regarding stochasticity, we use a dynamic programming algorithm and we proceed to a set of simulations of the real-time execution of the service activities over the period. All our experimentations have been made on problems coming from realistic data.

Jury

Thesis of the team OSL defended on 28/03/2014