Branch-and-price and constraint programming for solving a real-life technician dispatching problem

Cortés CE.; Gendreau, M; Rousseau, LM; Souyris S; Weintraub A.

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. (C) 2014 Elsevier B.V. All rights reserved.

Más información

Título según WOS: Branch-and-price and constraint programming for solving a real-life technician dispatching problem
Título según SCOPUS: Branch-and-price and constraint programming for solving a real-life technician dispatching problem
Título de la Revista: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volumen: 238
Número: 1
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2014
Página de inicio: 300
Página final: 312
Idioma: English
DOI:

10.1016/j.ejor.2014.03.006

Notas: ISI, SCOPUS