کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6892676 | 1445455 | 2018 | 33 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Combining Benders decomposition and column generation for multi-activity tour scheduling
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 93, May 2018, Pages 151-165
Journal: Computers & Operations Research - Volume 93, May 2018, Pages 151-165
نویسندگان
Maria I. Restrepo, Bernard Gendron, Louis-Martin Rousseau,