Back to search

McMaster University

A Large-Scale Neighborhood Search Algorithm for Multi-Activity Tour Scheduling Problems

Abstract

dc:description.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. This problem relates to assigning the employees’ working days throughout the planning horizon and working periods on each working day. In each period, an activity type is given which requires certain skill of the employees. The goal is to reduce the overall over- and under-coverage for each period and activity. The shifts and breaks defined with variable starting slots and durations make the problem flexible and hard to solve. In order to address the problem, an integer programming (IP) approach is first proposed. Due to the problems’ high degree of flexibility, it is impossible to solve instances involving numerous employees and activities in a timely and efficient manner. This leads to the proposal of a heuristic method based on a large neighborhood search (LNS) algorithm. We first create the daily schedules by a context-free grammar (CFG). Then we solve a resource-constrained shortest path problem (RCSPP) to create weekly schedules. Heuristic search is performed on weekly schedules. Moreover, when a constraint on task repetition is added, a CFG is unable to express this constraint, so we incorporate an extension of the IP into our proposed algorithm. Importantly, our approach does not use any closed-source commercial solver like CPLEX. Computational experiments are carried out on the industrial and randomly generated instances to evaluate the performance of the IP solved by CPLEX and the proposed algorithm. Results reveal that our method outperforms CPLEX in both solution time and solution quality in larger instances.

Degree

thesis:*
Department dc:contributor.department
Computational Engineering and Science
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shariat, Rana
Advisor dc:contributor.advisor
  • Huang, Kai

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Shariat, Rana. A Large-Scale Neighborhood Search Algorithm for Multi-Activity Tour Scheduling Problems. 2022. http://hdl.handle.net/11375/28203