A Tree-Based Tabu Search Algorithm for the Manpower Allocation Problem with Time Windows and Job-Teaming Constraints

IJCAI 2013

TL;DR

This paper introduces a novel tree-based representation for the complex Manpower Allocation Problem with Time Windows and Job-Teaming Constraints (MAPTWTC). By leveraging this representation, they develop an efficient Tabu Search algorithm that significantly outperforms existing methods and even exact solvers like CPLEX on challenging benchmark instances.

What Problem Does This Paper Address?

The paper tackles the Manpower Allocation Problem with Time Windows and Job-Teaming Constraints (MAPTWTC). This is a real-world scheduling and routing challenge where organizations need to assign workers with specific skills to a set of tasks. The core difficulties lie in:

  • Time Windows: Each task must be started and completed within a specific time frame.
  • Job-Teaming: Tasks often require a specific combination of worker skills to be performed.
  • Synchronization: A task cannot begin until all required workers are available at the task location.
  • Minimizing Costs: The objective is to minimize the total cost, which includes labor costs (number of workers) and travel costs (distance traveled).

This problem is a combinatorial optimization problem, known to be NP-hard, meaning finding the absolute best solution becomes computationally infeasible for large instances. Existing approaches often struggle with scalability or finding high-quality solutions.

Methods

The authors propose a multi-pronged approach:

  1. Integer Programming (IP) Model: They first formulate the MAPTWTC using a compact integer programming model with a network flow structure. This model captures the problem's constraints and objective.
  2. Tree Representation: A key innovation is representing MAPTWTC solutions as trees. They demonstrate that an optimal solution can be derived from a specific type of tree. This transforms the search space from a vast set of schedules to a more manageable set of spanning trees.
  3. Minimum Cost Flow (MCF) Model: To evaluate a given tree representation, they use a minimum cost flow model for each worker type. This allows them to calculate the optimal cost associated with a particular tree structure.
  4. Tree-Based Tabu Search (TTS) Algorithm: They develop a Tabu Search meta-heuristic that operates directly on the tree representations. The algorithm explores the space of feasible trees, using tree-relocation operators (vertex-relocate and subtree-relocate) to generate neighboring solutions. A tabu list prevents cycling, and an aspiration criterion allows overriding the tabu status for promising moves. Diversification strategies are also employed to escape local optima.

Datasets

The authors evaluate their algorithm on two sets of instances:

  1. Hong Kong and Singapore Instances: These are instances generated based on geometric data from these cities, with task numbers ranging from 79 to 106 and 5 worker types.
  2. Solomon's VRPTW Instances: They adapt 56 well-known Solomon's VRPTW instances by setting them up for the MAPTWTC problem, also using 5 worker types.

Key Insights and Ideas

  • The Power of Tree Representation: The most significant insight is that the complex MAPTWTC problem can be effectively represented by trees. This drastically reduces the search space and allows for the development of specialized search algorithms.
  • Connecting Trees to Schedules: The paper establishes a clear link between tree structures and feasible manpower allocation schedules, mediated by minimum cost flow models. This connection is crucial for evaluating tree-based solutions.
  • Efficiency of Tree-Based Search: By focusing the search on trees, the authors can design efficient operators and leverage the properties of spanning trees to find high-quality solutions.
  • Dominance of Labor Cost: The experimental setup (setting $\alpha \gg \beta$) highlights that labor cost is the primary driver in their tested scenarios, influencing the optimization objectives.

Key Results

  • Superior Solution Quality: The proposed Tree-based Tabu Search (TTS) algorithm consistently finds better solutions than simulated annealing-based algorithms previously reported for this problem.
  • Competitive with Exact Solvers: TTS achieves comparable or superior results to CPLEX (an exact solver) within reasonable time limits. For some instances, CPLEX struggled with memory or took excessively long.
  • Significant Improvement over CPLEX: On the second set of instances, TTS was able to reduce the number of workers generated by CPLEX by an average of 4.1% after 10 minutes and 6.6% after 30 minutes of computation.
  • Scalability: The tree-based approach appears to scale well, outperforming CPLEX on larger instances where exact methods falter.

Limitations and Future Work

  • Computational Time for CPLEX: The paper notes that CPLEX encountered "Out of memory" exceptions for instances with over 150 tasks, highlighting the scalability limitations of exact methods for this problem.
  • Future Research Directions: The authors suggest exploring more sophisticated meta-heuristics that can further leverage the tree representation. They also mention that their work provides a new perspective on solving VRP variants with synchronization constraints.

Summary updated

BibTeX
@inproceedings{2013tree,
  title = {{A Tree-Based Tabu Search Algorithm for the Manpower Allocation Problem with Time Windows and Job-Teaming Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2013},
}
Figure