Mixed integer programming with decomposition to solve a workforce scheduling and routing problem

Laesanklang, Wasakorn; Landa-Silva, Dario; Castillo-Salazar, J. Arturo

Abstract

We propose an approach based on mixed integer programming (MIP) with decomposition to solve a workforce scheduling and routing problem, in which a set of workers should be assigned to tasks that are distributed across different geographical locations. This problem arises from a number of home care planning scenarios in the UK, faced by our industrial partner. We present a mixed integer programming model that incorporates important real-world features of the problem such as defined geographical regions and flexibility in the workers? availability. Given the size of the real-world instances, we propose to decompose the problem based on geographical areas. We show that the quality of the overall solution is affected by the ordering in which the sub-problems are tackled. Hence, we investigate different ordering strategies to solve the sub-problems and show that such decomposition approach is a very promising technique to produce high-quality solutions in practical computational times using an exact optimization method.

Citation

Laesanklang, W., Landa-Silva, D., & Castillo-Salazar, J. A. (2015). Mixed integer programming with decomposition to solve a workforce scheduling and routing problem.

• Conference Name: International Conference on Operations Research and Enterprise Systems (ICORES 2015)
• End Date: Jan 12, 2015
• Publication Date: Jan 1, 2015
• Deposit Date: Jan 21, 2016
• Publicly Available Date: Jan 21, 2016
• Peer Reviewed: Peer Reviewed
• Keywords: Workforce scheduling, Routing problem, Home care scheduling, Mixed integer programming, Problem decomposition
• Public URL: https://nottingham-repository.worktribe.com/output/988621
• Publisher URL: http://www.scitepress.org/DigitalLibrary/Link.aspx?doi=10.5220/0005223602830293
• Additional Information: Published in: Proceedings of the International Conference on Operations Research and Enterprise Systems ISBN 9789897580758, pp. 283-293. DOI: 10.5220/0005223602830293