Fernando Ordóñez, Cristián E. Cortés, Sebastián Souyris and Andrés Weintraub.

We consider the problem of dispatching technicians to service/repair geographically distributed equipment. This problem can be cast as a vehicle routing problem with time windows, where customers expect fast response and small delays. Estimates of the service time, however, can be subject to a significant amount of uncertainty due to misdiagnoses of the reason for failure or surprises during repair. It is therefore crucial to develop routes for the technicians that would be insensitive to substantial deviations from estimated service times.  In this paper we propose a robust formulation for vehicle routing problem with soft time windows and service time uncertainty. We present exact formulations and a column generation algorithm to solve it capable of solving real world sized instances. We evaluate the efficiency of the approach through computational experiments on real industry routing data.

Cristián E. Cortés, Michel Gendreau, Louis M. Rousseau, Sebastián Souyris and Andrés Weintraub. Under second review.

We consider a real problem faced by the repair services of Xerox in Santiago, Chile. In a typical day about twenty technicians visit seventy customers on a predefined service area in Santiago. The problem is modeled by considering travel times, soft time windows in technician arrival times at client locations and fixed repair times to design optimally routes for technicians. A Branch and Price algorithm was developed, using a constraint branching strategy proposed by Ryan and Foster along with Constraint Programming in the column generation phase. The column generation takes advantage of the fact that each technician can visit no more than five to six service requests per day. The problem was solved to optimality in reasonable computer time. Results obtained compare favorably with current practice.