A large-scale neighborhood search algorithm for multi-activity tour scheduling problems

Rana Shariat () and Kai Huang ()
Additional contact information
Rana Shariat: McMaster University
Kai Huang: McMaster University

Journal of Heuristics, 2024, vol. 30, issue 5, No 1, 225-267

Abstract: Abstract In this research, we study multi-activity tour scheduling problems with heterogeneous employees in a service sector where demand varies greatly during the day. The goal is to reduce the overall over- and under- coverage. The shifts and breaks defined with variable starting periods and duration make the problem flexible and hard to solve. To address the problem, an integer programming (IP) model is first proposed. Due to the problem’s complexity, it is impossible to solve instances involving numerous employees and activities in a timely manner. So we propose a heuristic method based on a large neighborhood search algorithm. A combination of context-free grammar (CFG) and resource-constrained shortest path problem is used to create weekly schedules. Moreover, we propose a constraint on task repetition that CFG is unable to express, so we incorporate an IP extension into our proposed algorithm. Importantly, our approach does not rely on any commercial solver like CPLEX. Computational experiments are carried out on the industrial and randomly generated instances to evaluate the performance of the exact IP model solved by CPLEX and the proposed heuristic algorithm. Results reveal that our method outperforms CPLEX in both solution time and solution quality in larger instances.

Keywords: Multi-activity tour scheduling; Integer programming; Large neighborhood search; Context-free grammar (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-024-09527-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joheur:v:30:y:2024:i:5:d:10.1007_s10732-024-09527-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-024-09527-0

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().