Optimizing Manpower Allocation for Ground Handling Tasks in Airports using Column Generation

Anders Dohn Hansen, Esben Kolind

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    The Manpower Allocation Problem with Time Windows, Job-Teaming Constraints and a limited number of teams (m-MAPTWTC) is the problem of assigning m teams to a number of tasks, where both teams and tasks are restricted by time windows outside which operation is not possible. Tasks may require several individual teams to cooperate. Cooperating teams have to be synchronized with each other. Due to the limited number of teams, some tasks may have to be left unassigned. The objective is to maximize the number of assigned tasks. The problem arises in various crew scheduling contexts where cooperation between teams/workers, possibly with different skills, is required. This study focuses on the scheduling of ground handling tasks in some of Europe's major airports. Any daily schedule must comply with the time windows and skill requirements of tasks, transportation time between locations, the working hours of the staff, synchronization requirements between teams, and union regulations. The problem is solved using column generation in a Branch-and-Price framework. Synchronization between teams is enforced by branching on time windows. The resource constrained shortest path subproblem is solved by a label setting algorithm. 12 authentic data sets from two of Europe's major airports are used for testing. Optimal solutions are found for 11 of the test instances. Keywords: Manpower allocation, crew scheduling, vehicle routing with time windows, synchronization, column generation, Branch-and-Price, time window branching, set partitioning, set covering, integer programming.
    Original languageEnglish
    Title of host publicationORSNZ'08 - Proceedings : 43rd Annual Conference of the Operational Research Society of New Zealand
    Publication date2008
    Pages2-11
    Publication statusPublished - 2008
    Event43rd Annual Conference of the Operational Research Society of New Zealand -
    Duration: 1 Jan 2008 → …

    Conference

    Conference43rd Annual Conference of the Operational Research Society of New Zealand
    Period01/01/2008 → …

    Fingerprint Dive into the research topics of 'Optimizing Manpower Allocation for Ground Handling Tasks in Airports using Column Generation'. Together they form a unique fingerprint.

    Cite this