Combining Benders decomposition and column generation for multi-activity tour scheduling. (May 2018)

• Record Type: Journal Article
• Authors: Restrepo, Maria I.; Gendron, Bernard; Rousseau, Louis-Martin
• Is Part Of: Computers & operations research. Volume 93(2018)
• Page Start: 151
• Page End: 165
• Publication Date: 2018-05
• Subjects: Multi-activity tour scheduling problem -- Benders decomposition -- Column generation -- Context-free grammars; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.01.014
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We study the anonymous discontinuous multi-activity tour scheduling problem. We develop an innovative decomposition method to solve the problem. We show that our method is able to find high-quality solutions for weekly instances with up to 10 activities. Abstract: This paper presents a method that combines Benders decomposition and column generation to solve the multi-activity tour scheduling problem. The Benders decomposition approach iterates between a master problem that links daily shifts with tour patterns and a set of daily subproblems that assign work activities and breaks to the shifts. Due to its structure, the master problem is solved by column generation. We exploit the expressiveness of context-free grammars to model and solve the Benders subproblems. Computational results show that our method outperforms a branch-and-price approach and is able to find high-quality solutions for weekly instances dealing with up to ten work activities. The adaptation of the method to the shift scheduling problem (the special case defined on a single day) is also shown to outperform the solution of a grammar-based model by a state-of-the-art mixed-integer programming solver on instances with up to 30 work activities.