Skip to main content
SpringerLink
Log in

Workforce scheduling and routing problems: literature survey and computational study

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In the context of workforce scheduling, there are many scenarios in which personnel must carry out tasks at different locations hence requiring some form of transportation. Examples of these type of scenarios include nurses visiting patients at home, technicians carrying out repairs at customers’ locations and security guards performing rounds at different premises, etc. We refer to these scenarios as workforce scheduling and routing problems (WSRP) as they usually involve the scheduling of personnel combined with some form of routing in order to ensure that employees arrive on time at the locations where tasks need to be performed. The first part of this paper presents a survey which attempts to identify the common features of WSRP scenarios and the solution methods applied when tackling these problems. The second part of the paper presents a study on the computational difficulty of solving these type of problems. For this, five data sets are gathered from the literature and some adaptations are made in order to incorporate the key features that our survey identifies as commonly arising in WSRP scenarios. The computational study provides an insight into the structure of the adapted test instances, an insight into the effect that problem features have when solving the instances using mathematical programming, and some benchmark computation times using the Gurobi solver running on a standard personal computer.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

References

  • Akjiratikarl, C., Yenradee, P., & Drake, P. R. (2006). An improved particle swarm optimization algorithm for care worker scheduling. In Proceedings of the 7th Asia Pacific industrial engineering and management systems conference, Bangkok, Thailand (pp. 457–466).

  • Akjiratikarl, C., Yenradee, P., & Drake, P. R. (2007). Pso-based algorithm for home care worker scheduling in the UK. Computers & Industrial Engineering, 53(4), 559–583.

    Article  Google Scholar 

  • Alfares, H. K. (2004). Survey, categorization and comparison of recent tour scheduling literature. Annals of Operations Research, 127(1–4), 145–175.

    Article  Google Scholar 

  • Baker, K. R. (1976). Workforce allocation in cyclical scheduling problems: A survey. Journal of the Operational Research Society, 27(1), 155–167.

    Article  Google Scholar 

  • Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329.

    Article  Google Scholar 

  • Begur, S. V., Miller, D. M., & Weaver, J. R. (1997). An integrated spatial dss for scheduling and routing home-health-care nurses. Interfaces, 27(4), 35–48.

    Article  Google Scholar 

  • Bertels, S., & Fahle, T. (2006). A hybrid setup for a hybrid scenario: Combining heuristics for the home health care problem. Computers and Operations Research, 33(10), 2866–2890.

    Article  Google Scholar 

  • Blais, M., Lapierre, S. D., & Laporte, G. (2003). Solving a home-care districting problem in a urban setting. Journal of the Operational Research Society, 54(11), 1141–1147.

    Article  Google Scholar 

  • Borsani, V., Matta, A., Sommaruga, F., & Beschi, G. (2006). A home care scheduling model for human resources. In Proceedings of the international conference on service systems and service management (Vol. 1, pp. 449–454).

  • Brandão, J., & Mercer, A. (1997). A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal of Operational Research, 100(1), 180–191.

    Article  Google Scholar 

  • Brandão, J., & Mercer, A. (1998). The multi-trip vehicule routing problem. Journal of the Operational Research Society, 49(8), 799–805.

    Article  Google Scholar 

  • Bredström, D., & Rönnqvist, M. (2007). A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. NHH Dept of Finance & Management Science Discussion Paper No 2227/7.

  • Bredström, D., & Rönnqvist, M. (2008). Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. European Journal of Operational Research, 191(1), 19–31.

    Article  Google Scholar 

  • Castro-Gutierrez, J., Landa-Silva, D., & Moreno-Perez, J. (2011). Nature of real-world multi-objective vehicle routing with evolutionary algorithms. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics (SMC) (pp. 257–264).

  • Cheang, B., Li, H., Lim, A., & Rodrigues, B. (2003). Nurse rostering problems a bibliographic survey. European Journal of Operational Research, 151(3), 447–460.

    Article  Google Scholar 

  • Cheng, E., & Rich, J. L. (1998). A home health care routing and scheduling problem. Technical report CAAM TR98-04. Rice University.

  • Chuin Lau, H., & Gunawan, A. (2012). The patrol scheduling problem. In Proceedings of the 9th international conference on the practice and theory of automated timetabling (PATAT 2012), Son, Norway (pp. 175–192).

  • Cordeau, J. F., Laporte, G., Pasin, F., & Ropke, S. (2010). Scheduling technicians and tasks in a telecommunications company. Journal of Scheduling, 13(4), 393–409.

    Article  Google Scholar 

  • De Angelis, V. (1998). Planning home assistance for aids patients in the city of Rome, Italy. Interfaces, 28(3), 75–83.

    Article  Google Scholar 

  • Desaulniers, G., Lavigne, J., & Soumis, F. (1998). Multi-depot vehicle scheduling problems with time windows and waiting costs. European Journal of Operational Research, 111(3), 479–494.

    Article  Google Scholar 

  • Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations research, 40(2), 342–354.

    Article  Google Scholar 

  • Desrosiers, J., & Lübbecke, M. E. (2005). A primer in column generation. In G. Desaulniers, J. Desrosiers, & M. M. Solomon (Eds.), Column generation, Chap. 1 (pp. 1–32). Berlin: Springer.

  • Dohn, A., Rasmussen, M. S., Justesen, T., & Larsen, J. (2008). The home care crew scheduling problem. In K. Sheibani (Eds.), Proceedings of the 1st international conference on applied operational research. (ICAOR’08), Yerevan, Armenia. Lecture Notes in Management Science, (Vol. 1, pp. 1–8).

  • Dohn, A., Kolind, E., & Clausen, J. (2009). The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach. Computers & Operations Research, 36(4), 1145–1157.

    Article  Google Scholar 

  • Eaton, S. C. (2003). If you can use them: Flexibility policies, organizational commitment, and perceived performance. Industrial Relations: A Journal of Economy and Society, 42(2), 145–167.

    Google Scholar 

  • Ernst, A., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3–27.

    Article  Google Scholar 

  • Eveborn, P., Flisberg, P., & Rönnqvist, M. (2006). Laps care an operational system for staff planning of home care. European Journal of Operational Research, 171(3), 962–976.

    Article  Google Scholar 

  • Eveborn, P., Rönnqvist, M., Einarsdóttir, H., Eklund, M., Lidén, K., & Almroth, M. (2009). Operations research improves quality and efficiency in home care. Interfaces, 39(1), 18–34.

    Article  Google Scholar 

  • Fischetti, M., Polo, C., & Scantamburlo, M. (2004). A local branching heuristic for mixed-integer programs with 2-level variables, with an application to a telecommunication network design problem. Networks, 44(2), 61–72.

    Article  Google Scholar 

  • Fosgerau, M., & Engelson, L. (2011). The value of travel time variance. Transportation Research Part B: Methodological, 45(1), 1–8.

    Article  Google Scholar 

  • Golembiewski, R., & Proehl, C, Jr. (1978). A survey of the empirical literature on flexible workhours: Character and consequences of a major innovation. Academy of Management Review, 3(4), 837–853.

    Google Scholar 

  • Günther, M., & Nissen, V. (2012). Application of particle swarm optimization to the british telecom workforce scheduling problem. In Proceedings of the 9th international conference on the practice and theory of automated timetabling (PATAT 2012), Son, Norway (pp. 242–256).

  • Itabashi, G., Chiba, M., Takahashi, K., & Kato, Y. (2006). A support system for home care service based on multi-agent system. Proceedings of the fifth international conference on information, communications and signal processing, 2005 (pp. 1052–1056).

  • Jara-Díaz, S. R. (2000). Allocation and valuation of travel time savings. In D. A. Hensher & K. J. Button (Eds.), Handbook of transport modelling, Chap. 18 (Vol. 1, pp. 303–318). New York: Elsevier Science B.V.

  • Kallehauge, B., Larsen, J., Madsen, O. B. G., & Solomon, M. M. (2005). Vehicle routing problem with time windows. In G. Desaulniers, J. Desrosiers, & M. M. Solomon (Eds.), Column generation, Chap. 3 (pp. 67–98). Berlin: Springer.

  • Kergosien, Y., Lente, C., & Billaut, J. C. (2009). Home health care problem, an extended multiple travelling salesman problem. In J. Blazewicz, M. Drozdowski, G. Kendall, & B. McCollum (Eds.), Proceedings of the 4th multidisciplinary international scheduling conference: Theory and applications (MISTA 2009), Dublin, Ireland (pp. 85–92).

  • Landa-Silva, D., Wang, Y., Donovan, P., & Kendall, G. (2011). Hybrid heuristic for multi-carrier transportation plans. Proceedins of the 9th metaheuristics international conference (MIC2011), Udine, Italy (pp. 221–229).

  • Li, Y., Lim, A., & Rodrigues, B. (2005). Manpower allocation with time windows and job-teaming constraints. Naval Research Logistics, 52(4), 302–311.

    Article  Google Scholar 

  • Lim, A., Rodrigues, B., & Song, L. (2004). Manpower allocation with time windows. Journal of the Operational Research Society, 55(11), 1178–1186.

    Article  Google Scholar 

  • Martínez-Sánchez, A., Pérez-Pérez, M., Luis-Carnicer, P., & Vela-Jiménez, M. (2007). Telework, human resource flexibility and firm performance. New Technology, Work and Employment, 22(3), 208–223.

    Article  Google Scholar 

  • Miller, H. (1976). Personnel scheduling in public systems: A survey. Socio-economic Planning Sciences, 10(6), 241–249.

    Article  Google Scholar 

  • Misir, M., Verbeeck, K., De Causmaecker, P., & Vanden Bergue, G. (2010). Hyper-heuristics with a dynamic heuristic set for the home care scheduling problem. In Proceedings of IEEE congress on evolutionary computation (CEC) (pp 18–23).

  • Misir, M., Smet, P., Verbeeck, K., & Vanden Bergue, G. (2011). Security personnel routing and rostering: A hyper-heuristic approach. Proceedings of the 3rd International Conference on Applied Operational Research, ICAOR11, Istanbul, Turkey (pp. 193–206).

  • Raff, S. (1983). Routing and scheduling of vehicles and crews: The state of the art. Computers & Operations Research, 10(2), 63–211.

    Article  Google Scholar 

  • Rasmussen, M. S., Justesen, T., Dohn, A., & Larsen, J. (2012). The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies. European Journal of Operational Research, 219(3), 598–610.

    Article  Google Scholar 

  • Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455–472.

    Article  Google Scholar 

  • Salani, M., & Vaca, I. (2011). Branch and price for the vehicle routing problem with discrete split deliverables and time windows. European Journal of Operational Research, 213(3), 470–477.

    Article  Google Scholar 

  • Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time windows constraints. Operations Research, 35(2), 254–265.

    Article  Google Scholar 

Download references

Acknowledgments

We acknowledge the authors (Castro-Gutierrez et al. 2011; Rasmussen et al. 2012; Misir et al. 2011; Günther and Nissen 2012) who kindly provided us the original data sets to perform this study.

Author information

Authors and Affiliations

  1. ASAP Research Group, School of Computer Science, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, NG8 1BB, United Kingdom

    J. Arturo Castillo-Salazar, Dario Landa-Silva & Rong Qu

Authors
  1. J. Arturo Castillo-Salazar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dario Landa-Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rong Qu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. Arturo Castillo-Salazar.

Additional information

The author acknowledges CONACYT for its financial support.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Castillo-Salazar, J.A., Landa-Silva, D. & Qu, R. Workforce scheduling and routing problems: literature survey and computational study. Ann Oper Res 239, 39–67 (2016). https://doi.org/10.1007/s10479-014-1687-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-014-1687-2

Keywords

Search

Navigation