Abstract
The Technician Routing and Scheduling Problem (TRSP) consists in routing staff to serve requests for service, taking into account time windows, skills, tools, and spare parts. Typical applications include maintenance operations and staff routing in telecoms, public utilities, and in the health care industry. In this paper, we present a formal definition of the TRSP, discuss its relation with the Vehicle Routing Problem with Time Windows (VRPTW), and review related research. From a methodological perspective, we describe a matheuristic composed of a constructive heuristic, a parallel Adaptive Large Neighborhood Search, and a mathematical programming based post-optimization procedure that successfully tackles the TRSP. We validate the matheuristic on the Solomon VRPTW instances, where we achieve an average gap of \(0.23\,\%\), and matched 44 out of 55 optimal solutions. Finally, we illustrate how the matheuristic successfully solves a set of TRSP instances extended from the Solomon benchmark.
Similar content being viewed by others
Notes
Note that we truncate the distances to one decimal, as it is common practice when solving the Solomon instances [15] with the distance minimization as solely objective.
In addition, it is important to note that 7 optimal solutions were not known at the time of their study, using the same values the average gap for our approach is of \(0.16\,\%\).
References
Akjiratikarl, C., Yenradee, P., Drake, P.R.: PSO-based algorithm for home care worker scheduling in the UK. Compu. Ind. Eng. 53(4), 559–583 (2007)
Bertels, S., Fahle, T.: A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem. Comput. Operat. Res. 33(10), 2866–2890 (2006)
Bredström, D., Rönnqvist, M.: Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. Eur. J. Operat. Res. 191(1), 19–31 (2008)
Cordeau, J.F., Laporte, G., Pasin, F., Ropke, S.: Scheduling technicians and tasks in a telecommunications company. J. Sched. 13(4), 393–409 (2010)
Eveborn, P., Flisberg, P., Rönnqvist, M.: LAPS CARE—an operational system for staff planning of home care. Eur. J. Operat. Res. 171(3), 962–976 (2006)
Hashimoto, H., Boussier, S., Vasquez, M., Wilbaut, C.: A GRASP-based approach for technicians and interventions scheduling for telecommunications. Ann. Operat. Res. 183, 143–161 (2011)
Kovacs, A., Parragh, S., Doerner, K., Hartl, R.: Adaptive large neighborhood search for service technician routing and scheduling problems. J. Sched. :1–22 (2011). doi:10.1007/s10951-011-0246-9
Parragh, S.N.: Solving a real-world service technician routing and scheduling problem. In Proceedings of the Seventh Triennial Symposium on Transportation Analysis (TRISTAN VII) (2010)
Pillac, V., Guéret, C., Medaglia, A.L.: A parallel matheuristic for the technician routing and scheduling problem: supplementary material (online) (2011). http://hdl.handle.net/1992/1145
Pisinger, D., Ropke, S.: A general heuristic for vehicle routing problems. Comput. Operat. Res. 34(8), 2403–2435 (2007)
Potvin, J.Y., Rousseau, J.M.: A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. Eur. J. Operat. Res. 66(3), 331–340 (1993)
Prins, C.: Two memetic algorithms for heterogeneous fleet vehicle routing problems. Eng. Appl. Artif. Intell. 22(6), 916–928 (2009)
Savelsbergh, M.: The vehicle routing problem with time windows: minimizing route duration. INFORMS J. Comput. 4(2), 146–154 (1992)
Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Principles and Practice of Constraint Programming—CP98. Lecture Notes in Computer Science vol. 1520, pp. 417–431 (1998)
Solomon, M.M.: Algorithms for the vehicle-routing and scheduling problems with time window constraints. Operat. Res. 35(2), 254–265 (1987)
Tang, H., Miller-Hooks, E., Tomastik, R.: Scheduling technicians for planned maintenance of geographically distributed equipment. Transp. Res. Part E: Log. Transp. Rev. 43(5), 591–609 (2007)
Tsang, E., Voudouris, C.: Fast local search and guided local search and their application to British Telecom’s workforce scheduling problem. Operat. Res. Lett. 20(3), 119–127 (1997)
Vidal, T., Crainic, T., Gendreau, M., Prins, C.: A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows. Comput. Operat. Res. 40(1), 475–489 (2013)
Villegas, J.G.: Vehicle routing problems with trailers. 4OR: Q. J. Operat. Res. (2012). doi:10.1007/s10288-011-0186-4
Xu, J., Chiu, S.: Effective heuristic procedures for a field technician scheduling problem. J. Heurist. 7(5), 495–509 (2001)
Acknowledgments
Financial support for this work was provided by the CPER (Contrat de Projet Etat Region) Vallée du Libre (France); and the Centro de Estudios Interdisciplinarios Básicos y Aplicados en Complejidad (CEIBA, Colombia). This support is gratefully acknowledged. The authors would also like to thank Olivier Péton from the Ecole des Mines de Nantes and the anonymous reviewers for their insightful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pillac, V., Guéret, C. & Medaglia, A.L. A parallel matheuristic for the technician routing and scheduling problem. Optim Lett 7, 1525–1535 (2013). https://doi.org/10.1007/s11590-012-0567-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-012-0567-4