Stabilized branch and price with dynamic parameter updating for discontinuous tour scheduling

Brunner, Jens O. ; Stolletz, Raik

Document Type: Article
Year of publication: 2014
The title of a journal, publication series: Computers & Operations Research
Volume: 44
Page range: 137-145
Place of publication: Oxford [u.a.]
Publishing house: Elsevier
ISSN: 0305-0548
Publication language: English
Institution: Business School > ABWL u. Produktion (Stolletz 2010-)
Subject: 650 Management
Keywords (English): Shift scheduling , Integer programming , Branch and price , Stabilized column generation , Check-in counter agents
Abstract: In this paper we address the problem of staff scheduling at check-in counters with time varying demand. The main objective is to minimize a cost function based on the assigned shifts for a given workforce subject to flexible labor regulations and flexible assignments of lunch breaks. To solve the problem we developed a branch and price algorithm that uses master variable branching. However, since convergence of the column generation subroutine was really slow, we integrated stabilization techniques to speed up the algorithm. We introduced a new dynamic parameter updating procedure for the stabilized column generation. Our computational results show the superior behavior of stabilized column generation compared to the non-stabilized version. Since slow convergence might occur at each node in the search tree and consequently reductions are realized at each node investigated. Furthermore, we perform an in-depth investigation of the updating parameters and give useful insights to choose them. Finally, we tackle realistic problem instances with up to 65 service workers and show the efficiency of the algorithm.

Dieser Eintrag ist Teil der Universitätsbibliographie.

Metadata export


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item