A Tabu Search Algorithm for the Multi-period Inspector Scheduling Problem

Hu Qin, Zizhen Zhang, Yubin Xie, Andrew Lim

Introduction

In logistics research, the Vehicle Routing Problem (VRP) typically involves a fleet of vehicles returning to a central depot daily. However, real-world scenarios often involve human agents, such as quality inspectors, who travel across large regions over multiple days. These inspectors stay in hotels and follow specific work-rest cycles, creating a complex scheduling challenge known as the Multi-period Inspector Scheduling Problem (MPISP). This paper introduces a Tabu Search algorithm designed to optimize these multi-day tours while accounting for time-dependent travel logic and human work constraints.

The Multi-period Inspector Scheduling Problem (MPISP)

The MPISP extends standard routing by incorporating multi-day horizons where inspectors do not necessarily return to a depot each night. Instead, they utilize "waypoints"—intermediate locations like hotels—to rest between work periods. This introduces two primary complexities:

  1. Hotel Selection and Recuperation: Inspectors must stop working at the end of a shift and resume the next day, often from their last service location or a nearby waypoint.
  2. Time-Dependent Transit: Travel feasibility depends on the time of day. If a trip cannot be completed before the workday ends, the inspector must either wait until the next period or travel to a waypoint closer to the destination.
Illustration of time-dependent travel logic showing working and downtime periods.

The objective is to maximize the total workload completed by a fixed team of inspectors, thereby minimizing the reliance on costly third-party outsourcing.

Methodology: Tabu Search and Waypoint Logic

The authors propose a multi-stage approach to solve the MPISP:

Time-Dependent Preprocessing

To handle the "wait vs. travel" decision, a modified Dijkstra’s algorithm calculates shortest transit times between all pairs of locations. This preprocessing transforms a static distance matrix into a dynamic temporal one, accounting for mandatory rest periods and the transition between working and downtime.

Tabu Search Framework

The core of the solution is a Tabu Search (TS) meta-heuristic. It explores the solution space using adapted routing operators like 2-opt and Relocate, tailored for multi-period feasibility. To avoid local optima, the algorithm maintains a "tabu list" of recently performed moves. The fitness function is lexicographical, prioritizing workload, then the ease of inserting unserved suppliers, and finally total free time.

Multi-period Scheduling and the Ejection Pool

A key feature is the Ejection Pool. When a job cannot be fitted into any existing schedule, it is placed in this pool. The algorithm periodically attempts to force these jobs into the schedule by "ejecting" less valuable tasks. This mechanism is crucial for navigating tight constraints and improving overall workload across the multi-period horizon.

Multi-period schedules for multiple inspectors and the set of unserved suppliers.

Experimental Evaluation

The algorithm was tested on two sets of benchmarks:

  • TOPTW Benchmarks: On 370 instances of the Team Orienteering Problem with Time Windows, the TS algorithm found the best-known solution in 272 cases, outperforming several state-of-the-art methods like ILS and SSA.
  • MPISP Instances: The researchers generated 672 new instances based on Solomon VRPTW benchmarks. The TS algorithm produced results remarkably close to a theoretical upper bound derived from a constrained knapsack integer programming model, often finding high-quality solutions in minutes.

Conclusion

The proposed Tabu Search algorithm effectively addresses the complexities of the Multi-period Inspector Scheduling Problem. By integrating time-dependent travel logic and an innovative ejection pool mechanism, the approach provides high-quality schedules in practical timeframes. Future work may extend this "waypoint" logic to other domains, such as electric vehicle routing with charging requirements or more complex labor regulation modeling.

Summary updated

BibTeX
@article{qin2015tabu,
  author = {Hu Qin and Zizhen Zhang and Yubin Xie and Andrew Lim},
  title = {{A Tabu Search Algorithm for the Multi-period Inspector Scheduling Problem}},
  journal = {Comput. Oper. Res.},
  year = {2015},
  doi = {10.1016/j.cor.2015.01.003},
}
Figure