The Multi-Period Workforce Scheduling and Routing Problem

G. Guastaroba, J.-F. Côté and L.C. Coelho

Omega, 2021, vol. 102, issue C

Abstract: Motivated by the problem faced by a company that provides installation and maintenance services of electrical infrastructures, we study the Multi-Period Workforce Scheduling and Routing Problem (MPWSRP). A set of jobs requiring a service is given. A given set of workers, each proficient in a number of skills, is available to serve the jobs. Each job requires a team of workers providing the required skills, and is associated with a given priority level. A service time, which might span over multiple time periods, is associated with each job, and depends on the number of workers that have been assigned. The MPWSRP calls for determining an optimal dispatch plan to serve the given set of jobs by routing a number of teams over a finite planning horizon. The MPWSRP is a highly complex combinatorial optimization problem where routing, scheduling, and assignment decisions have to be taken simultaneously. We cast the MPWSRP as a Mixed-Integer Linear Program (MILP). As an off-the-shelf solver can solve only small-size instances of the proposed MILP in reasonable computing times, we devise an Adaptive Large Neighborhood Search (ALNS) heuristic and a three-phase Decomposition Algorithm (DA) to solve large-size instances. Extensive computational experiments are conducted on a large set of instances comprising up to 100 jobs, 20 workers, and 20 time periods. The results show that ALNS is competitive with the solver on the small-size instances, producing solutions of similar average quality in considerably shorter computing times. In addition, they point out that ALNS consistently outperforms the DA in terms of solution quality. Further computational experiments are conducted applying our ALNS and DA on a set of large-size instances. Finally, a case study using real data sets is provided.

Keywords: Workforce routing and scheduling; Multi-period planning; Mixed-integer linear programming; Adaptive large neighborhood search; Matheuristic (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048320306563
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:102:y:2021:i:c:s0305048320306563

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2020.102302

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().