An Efficient Metaheuristic Approach for the Multi-Period Technician Routing and Scheduling Problem

A. Khattara, W. R. Cherif-Khettaf, M. Mostefai

Abstract


In this paper, we address a new variant of the Multi-Period Technician Routing and Scheduling Problem. This problem is motivated by a real-life industrial application in a telecommunication company. It is defined by a set of technicians having distinct skills that could perform a set of geographically scattered tasks over a multi-period horizon. Each task is subject to time constraints and must be done at most once over the horizon by one compatible technician. The objective is to minimize the total working time (composed by routing time, service time, and waiting time), the total cost engendered by the rejected tasks, and the total delay. Two variants of variable neighborhood descent are proposed, and three variants of variable neighborhood search to solve this problem. Computational experiments are conducted on benchmark instances from the literature. An analysis of the performance of the proposed local search procedures is given. The results show that our methods outperform the results of a mimetic method published in the literature.


Keywords


technician routing and scheduling problem (TRSP); variable neighborhood search (VNS); variable neighborhood descent (VND)

Full Text:

PDF

References


V. Pillac, C. Gueret, A. L. Medaglia, “A parallel matheuristic for the technician routing and scheduling problem”, Optimization Letters, Vol. 7, No. 7, pp. 1525-1535, 2013

J. Xu, S. Y. Chiu, “Effective heuristic procedures for a field technician scheduling problem”, Journal of Heuristics, Vol. 7, No. 5, pp. 495-509, 2001

E. Hadjiconstantinou, D. Roberts, “Routing under uncertainty: an application in the scheduling of field service engineers”, in: The vehicle Routing Problem, pp. 331-352, Society for Industrial and Applied Mathematics, 2001

E. Delage, Re-optimization of Technician Tours in Dynamic Environments with Stochastic Service Time, Ecole des Mines de Nantes, 2010

C. E. Cortes, F. Ordonez, S. Souyris, A. Weintraub, “Routing technicians under stochastic service times: a robust optimization approach”, TRISTAN VI: The Sixth Triennial Symposium on Transportation Analysis, Phuket Island, Thailand, June 10-15, 2007

V. Pillac, C. Gueret, A. Medaglia, “On the dynamic technician routing and scheduling problem”, 5th International Workshop on Freight Transportation and Logistics, Mykonos, Greece, May 21-25, 2012

X. Chen, B. W. Thomas, M. Hewitt, “Multi-Period Technician Scheduling with Experience-based Service Times and Stochastic Customers”, Computers and Operations Research, Vol. 82, No. C, pp. 1-14, 2017

W. Jaskowski, ROADEF Challenge 2007: Technicians and Interventions Scheduling for Telecommunications, Poznan University of Technology, 2007

F. Tricoire, Optimisation de Tournees de Vehicules et de Personnels de Maintenance: Application a la Distribution et au Traitement des Eaux, PhD Thesis, Universite de Nantes, 2006 (in French)

A. A. Kovacs, S. N. Parragh, K. F. Doerner, R. F. Hartl, “Adaptive large neighborhood search for service technician routing and scheduling problems”, Journal of Scheduling, Vol. 15, No. 5, pp. 579-600, 2012

N. Bostel, P. Dejax, P. Guez, F. Tricoire, “Multiperiod planning and routing on a rolling horizon for field force optimization logistics”, in: The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 503-525, Springer, 2008

F. Tricoire, N. Bostel, P. Dejax, P. Guez, “Exact and hybrid methods for the multiperiod field service routing problem”, Central European Journal of Operations Research, Vol. 21, No. 2, pp. 359-377, 2013

O. Braysy, “A reactive variable neighborhood search for the vehicle routing problem with time windows”, INFORMS Journal of Computing, Vol. 15, No. 4, pp. 347–368, 2003

M. Polacek, R. F. Hartl, K. Doerner, M. Reimann, “A variable neighborhood search for the multi depot vehicle routing problem with time windows”, Journal of Heuristics, Vol. 10, No. 6, pp. 613-627, 2004

S. Salhi, A. Imran, N. A. Wassan, “The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation”, Computers & Operations Research, Vol. 52B, pp. 315-325, 2014

M. Elbek, S. Wohlk, “A variable neighborhood search for the multi-period collection of recyclable materials”, European Journal of Operational Research, Vol. 249, No. 2, pp. 540-550, 2016

R. L. Pinheiro, D. Landa-Silva, J. Atkin, “A variable neighbourhood search for the workforce scheduling and routing problem”, in: Advances in Nature and Biologically Inspired Computing, pp. 247-259, Springer, 2016

N. Mladenovic, P. Hansen, “Variable neighborhood search”, Computers & Operations Research, Vol. 24, No. 11, pp. 1097-1100, 1997

P. Hansen, N. Mladenovic, “Variable neighborhood search: Principles and applications”, European Journal of Operational Research, Vol. 130, No. 3, pp. 449-467, 2001

P. Hansen, N. Mladenovic, J. A. M. Perez, “Variable neighbourhood search: methods and applications”, Annals of Operations Research, Vol. 175, No. 1, pp. 367-407, 2010

P. Hansen, N. Mladenovic, R. Todosijevic, S. Hanafi, “Variable neighborhood search: basics and variants”, EURO Journal on Computational Optimization, Vol. 5, No. 3, pp. 1-32, 2016

A. Mjirda, R. Todosijevic, S. Hanafi, P. Hansen, N. Mladenovic, “Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem”, International Transactions in Operational Research, Vol. 24, No. 3, pp. 615-633, 2016




eISSN: 1792-8036     pISSN: 2241-4487