×

zbMATH — the first resource for mathematics

Branch-and-price approaches for the multiperiod technician routing and scheduling problem. (English) Zbl 1394.90315
Summary: This paper addresses a technician routing and scheduling problem motivated by the case of an external maintenance provider. Technicians are proficient in different skills and paired into teams to perform maintenance tasks. Tasks are skill constrained and have time windows that may span multiple days. The objective is to determine the daily assignment of technicians into teams, of teams to tasks, and of teams to daily routes such that the operation costs are minimized. We propose a mixed integer program and a branch-and-price algorithm to solve this problem. Exploiting the structure of the problem, alternative formulations are used for the column generation-phase of the algorithm. Using real-world data from an external maintenance provider, we conduct numerical studies to evaluate the performance of our proposed solution approaches.

MSC:
90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akjiratikarl, C.; Yenradee, P.; Drake, P. R., Pso-based algorithm for home care worker scheduling in the UK, Computers & Industrial Engineering, 53, 4, 559-583, (2007)
[2] Barrera, D.; Velasco, N.; Amaya, C.-A., A network-based approach to the multi-activity combined timetabling and crew scheduling problem: workforce scheduling for public health policy implementation, Computers & Industrial Engineering, 63, 4, 802-812, (2012)
[3] Bertels, S.; Fahle, T., A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem, Computers & Operations Research, 33, 10, 2866-2890, (2006) · Zbl 1086.90533
[4] Blakeley, F.; Arguello, B.; Cao, B.; Hall, W.; Knolmajer, J., Optimizing periodic maintenance operations for schindler elevator corporation, Interfaces, 33, 1, 67-79, (2003)
[5] Bode, C.; Irnich, S., The shortest-path problem with resource constraints with -loop elimination and its application to the capacitated arc-routing problem, European Journal of Operational Research, 238, 2, 415-426, (2014) · Zbl 1338.90423
[6] Bostel, N.; Dejax, P.; Guez, P.; Tricoire, F., Multiperiod planning and routing on a rolling horizon for field force optimization logistics, (Golden, B.; Raghavan, S.; Wasil, E., The vehicle routing problem: Latest advances and new challenges, chapter 3, Operations research/computer science interfaces, Vol. 43, (2008), Springer US Boston, MA), 503-525 · Zbl 1187.90040
[7] Boussier, S.; Feillet, D.; Gendreau, M., An exact algorithm for team orienteering problems, 4OR, 5, 3, 211-230, (2006) · Zbl 1211.90029
[8] Castillo-Salazar, J. A.; Landa-Silva, D.; Qu, R., Workforce scheduling and routing problems: literature survey and computational study, Annals of Operations Research, 239, 1, 1-29, (2014)
[9] Cheng, E.; Rich, J. L., A home health care routing and scheduling problem, Technical Report, (1998), Rice University
[10] Cordeau, J.-F.; Laporte, G.; Pasin, F.; Ropke, S., Scheduling technicians and tasks in a telecommunications company, Journal of Scheduling, 13, 4, 393-409, (2010) · Zbl 1231.90258
[11] Desrochers, M.; Desrosiers, J.; Solomon, M. M., A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, 40, 2, 342-354, (1992) · Zbl 0749.90025
[12] Dohn, A.; Kolind, E.; Clausen, J., The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach, Computers & Operations Research, 36, 4, 1145-1157, (2009) · Zbl 1162.90450
[13] Dror, M., Note on the complexity of the shortest path models for column generation in VRPTW, Operations Research, 42, 5, 977-978, (1994) · Zbl 0815.90064
[14] Ernst, A.; Jiang, H.; Krishnamoorthy, M., An annotated bibliography of personnel scheduling and rostering, Annals of Operations Research, 127, 1-4, 21-144, (2004) · Zbl 1090.90078
[15] Ernst, A.; Jiang, H.; Krishnamoorthy, M., Staff scheduling and rostering: A review of applications, methods and models, European Journal of Operational Research, 153, 1, 3-27, (2004) · Zbl 1053.90034
[16] Eveborn, P.; Flisberg, P.; Rönnqvist, M., Laps care- an operational system for staff planning of home care, European Journal of Operational Research, 171, 3, 962-976, (2006) · Zbl 1116.90373
[17] Feillet, D., A tutorial on column generation and branch-and-price for vehicle routing problems, 4OR, 8, 407-424, (2010) · Zbl 1208.90016
[18] Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems, Networks, 44, 3, 216-229, (2004) · Zbl 1056.90014
[19] Francis, P.; Smilowitz, K.; Tzur, M., The period vehicle routing problem with service choice, Transportation Science, 40, 4, 439-454, (2006)
[20] Francis, P. M.; Smilowitz, K. R.; Tzur, M., The period vehicle routing problem and its extensions, (Golden, B.; Raghavan, S.; Wasil, E., The vehicle routing problem: Latest advances and new challenges, chapter 1, Operations research/computer science interfaces, Vol. 43, (2008), Springer US Boston, MA), 73-102 · Zbl 1187.90049
[21] Gendreau, M.; Manerba, D.; Mansini, R., The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: A branch-and-price approach, European Journal of Operational Research, 248, 1, 59-71, (2016) · Zbl 1346.90112
[22] Google (2016). The Google Maps Distance Matrix API. https://developers.google.com/maps/documentation/distance-matrix/intro.
[23] Goossens, D.; Polyakovskiy, S.; Spieksma, F. C.R.; Woeginger, G. J., Between a rock and a hard place: the two-to-one assignment problem, Mathematical Methods of Operations Research, 76, 2, 223-237, (2012) · Zbl 1261.90023
[24] Ioachim, I.; Gélinas, S.; Desrosiers, J.; Soumis, F., A dynamic programming algorithm for the shortest path problem with time windows, Networks, 31, 3, 193-204, (1998) · Zbl 1002.90084
[25] Irnich, S., Resource extension functions: properties, inversion, and generalization to segments, OR Spectrum, 30, 1, 113-148, (2008) · Zbl 1133.90309
[26] Kohl, N.; Desrosiers, J., 2-path cuts for the vehicle routing problem with time windows, Transportation Science, 33, 1, 101-116, (1999) · Zbl 1004.90015
[27] Kovacs, A.a.; Parragh, S. N.; Doerner, K. F.; Hartl, R. F., Adaptive large neighborhood search for service Technician routing and scheduling problems, Journal of Scheduling, 15, 5, 579-600, (2011)
[28] Liberatore, F.; Righini, G.; Salani, M., A column generation algorithm for the vehicle routing problem with soft time windows, 4OR, 9, 1, 49-82, (2010) · Zbl 1225.90110
[29] Lim, A.; Rodrigues, B.; Song, L., Manpower allocation with time windows, Journal of the Operational Research Society, 55, 11, 1178-1186, (2004) · Zbl 1070.90067
[30] Pillac, V.; Guéret, C.; Medaglia, a. L., A parallel matheuristic for the Technician routing and scheduling problem, Optimization Letters, 7, 7, 1525-1535, (2012) · Zbl 1280.90013
[31] Savelsbergh, M. W.P., Local search in routing problems with time windows, Annals of Operations Research, 4, 1, 285-305, (1985)
[32] Solomon, M.; Desrosiers, J., Survey paper-time window constrained routing and scheduling problems, Transportation Science, 22, 1, 1-13, (1988) · Zbl 0638.90052
[33] Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35, 2, 254-265, (1987) · Zbl 0625.90047
[34] Souffriau, W.; Vansteenwegen, P.; Vanden Berghe, G.; Van Oudheusden, D., The multiconstraint team orienteering problem with multiple time windows, Transportation Science, 47, 1, 53-63, (2013)
[35] Tang, H.; Millerhooks, E.; Tomastik, R., Scheduling technicians for planned maintenance of geographically distributed equipment, Transportation Research Part E: Logistics and Transportation Review, 43, 5, 591-609, (2007)
[36] Van den Bergh, J.; Beliën, J.; De Bruecker, P.; Demeulemeester, E.; De Boeck, L., Personnel scheduling: A literature review, European Journal of Operational Research, 226, 3, 367-385, (2013) · Zbl 1292.90001
[37] Xu, J.; Chiu, S., Effective heuristic procedures for a field Technician scheduling problem, Journal of Heuristics, 7, 5, 495-509, (2001) · Zbl 1013.90061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.