Branch-and-price and constraint programming for solving a real-life technician dispatching problem |
| |
Authors: | Cristián E Cortés Michel Gendreau Louis Martin Rousseau Sebastián Souyris Andrés Weintraub |
| |
Institution: | 1. Civil Engineering Department, Universidad de Chile, Blanco Encalada 2002, 5th Floor, Santiago, Chile;2. CIRRELT and MAGI, Ecole Polytechnique de Montréal, C.P. 6079, Succ. Centre-ville, Montreal, Quebec H3C 3A7, Canada;3. McCombs School of Business, University of Texas at Austin, 2110 Speedway Stop B6500, Austin, TX 78712, USA;4. Industrial Engineering Department, Universidad de Chile, Republica 701, Santiago, Chile |
| |
Abstract: | We consider a real problem faced by a large company providing repair services of office machines in Santiago, Chile. In a typical day about twenty technicians visit seventy customers in a predefined service area in Santiago. We design optimal routes for technicians by considering travel times, soft time windows for technician arrival times at client locations, and fixed repair times. 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 satisfy no more than five to six service requests per day. Different instances of the problem were solved to optimality in a reasonable computational time, and the results obtained compare favorably with the current practice. |
| |
Keywords: | Branch-and-price Constraint programming Routing Technician dispatch problem |
本文献已被 ScienceDirect 等数据库收录! |
|