Computational study for workforce scheduling and routing problems

Unknown, Conference object English OPEN
Castillo-Salazar, J. Arturo ; Landa-Silva, Dario ; Qu, Rong (2014)

We present a computational study on 112 instances of the Workforce Scheduling and Routing Problem (WSRP). This problem has applications in many service provider industries where employees visit customers to perform activities. Given their similarity, we adapt a mathematical programming model from the literature on vehicle routing problem with time windows (VRPTW) to conduct this computational study on the WSRP. We generate a set of WSRP instances from a well-known VRPTW data set. This work has three objectives. First, to investigate feasibility and optimality on a range of medium size WSRP instances with different distribution of visiting locations and including teaming and connected activities constraints. Second, to compare the generated WSRP instances to their counterpart VRPTW instances with respect to their difficulty. Third, to determine the computation time required by a mathematical programming solver to find feasible solutions for the generated WSRP instances. It is observed that although the solver can achieve feasible solutions for some instances, the current solver capabilities are still limited. Another observation is the WSRP instances present an increased degree of difficulty because of the additional constraints. The key contribution of this paper is to present some test instances and corresponding benchmark study for the WSRP.
  • References (21)
    21 references, page 1 of 3

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

    An, Y.-J., Kim, Y.-D., Jeong, B., and Kim, S.-D. (2012). Scheduling healthcare services in a home healthcare system. Journal of the Operational Research Society, 63:1589-1599.

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

    Bredstro¨ m, D. and Ro¨ nnqvist, M. (2008). Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. European Journal of Operational Research, 191(1):19-31.

    Castillo-Salazar, J. A., Landa-Silva, D., and Qu, R. (2012). A survey on workforce scheduling and routing problems. In Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling, pages 283-302.

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

    Chuin Lau, H. and Gunawan, A. (2012). The patrol scheduling problem. In Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling, pages 175-192.

    Chuin Lau, H., Sim, M., and Meng Teo, K. (2003). Vehicle routing problem with time windows and a limited number of vehicles. European Journal of Operational Research, 148:559-569.

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

    Dondo, R. and Cerda´, J. (2007). A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European Journal of Operational Research, 176:1478- 1507.

  • Metrics
    No metrics available
Share - Bookmark