TL;DR
This paper introduces the Multi-Period Inspector Scheduling Problem (MPISP), a complex real-world challenge where inspectors must visit multiple locations over several days, with unique constraints like needing to recuperate at a site rather than returning to a depot daily. To tackle this, the authors developed a sophisticated Tabu Search algorithm, demonstrating its effectiveness in finding high-quality solutions for this novel problem.
What Problem Does This Paper Address?
Imagine a company that needs to inspect products at numerous supplier locations across Asia. This isn't a simple delivery route problem; it's a multi-period inspector scheduling problem (MPISP). Inspectors don't just go from point A to point B and return to base each day. Instead, they operate over multiple "periods" (think days or shifts), and at the end of each period, they must stay at their last visited location for "recuperation" before starting the next period's route. This is a significant departure from traditional vehicle routing problems where a return to the depot is standard.
Furthermore, if an inspector can't reach their next destination within the current period's time window, they have two options: wait at their current location until the next period begins, or travel to an intermediate "waypoint" that's closer to their ultimate destination. This adds complexity because travel times are no longer fixed; they depend on departure times and the period's length. The core challenge is to schedule these inspectors to complete as much inspection workload as possible while adhering to all these practical constraints, including individual workload limits and supplier-specific time windows.
Methods
The authors propose a Tabu Search algorithm to solve the MPISP. This is a metaheuristic, meaning it's a high-level strategy that guides a search process to find good solutions, especially for complex optimization problems where finding the absolute best solution is computationally infeasible.
Here's a breakdown of their approach:
- Shortest Transit Time Calculation: A novel method is developed to accurately calculate the shortest travel time between any two locations, considering the inspector's departure time and the constraints of the working periods. This is crucial because travel times are dynamic.
- Tabu Search Framework: The core of their solution is a Tabu Search algorithm. This involves:
- Initialization: Generating an initial feasible solution.
- Local Search with Tabu Moves: Iteratively improving the solution by making small changes (moves) and using a "tabu list" to prevent the algorithm from revisiting recently explored solutions, thus avoiding getting stuck in local optima.
- Ejection Pool Algorithm: A mechanism to handle unserved suppliers by trying to "eject" them from existing routes and re-insert them, or by ejecting existing suppliers to make space.
- Perturbation: Periodically introducing larger changes to the solution to escape local optima and explore new regions of the search space.
- Fitness Function: A multi-component fitness function is used to evaluate solutions, prioritizing total workload, then minimizing the difficulty of incorporating unserved suppliers, and finally minimizing route free times.
- Constrained Knapsack Model: To provide an upper bound for the problem, the authors formulate a mixed-integer programming model based on a constrained knapsack problem. This helps in evaluating the quality of the solutions found by their Tabu Search algorithm.
Datasets
The paper evaluates its algorithm on two types of datasets:
- TOPTW Instances: Standard instances from the Team Orienteering Problem with Time Windows literature, used to benchmark the algorithm's performance on a related problem.
- MPISP Instances: A new set of 672 MPISP instances generated from Solomon's VRPTW instances. These are specifically designed to test the proposed algorithm on the novel MPISP problem.
Key Insights and Ideas
- Dynamic Travel Times are Key: The most significant insight is that traditional fixed travel times are insufficient for MPISP. The dynamic nature of travel, influenced by period lengths and departure times, necessitates a specialized approach to calculating shortest transit times.
- Recuperation at Site is a Game Changer: The requirement for inspectors to recuperate at their last visited location, rather than returning to a central depot daily, fundamentally alters route planning and creates new optimization challenges.
- Waypoints as a Flexible Tool: The introduction of "waypoint" functionality, allowing inspectors to use intermediate locations to optimize travel, adds another layer of complexity and flexibility to the routing problem.
- Tabu Search is Well-Suited: The multi-component Tabu Search framework, with its local search, ejection pool, and perturbation strategies, proves to be a robust approach for navigating the complex solution space of the MPISP.
Key Results
The paper reports strong performance for their proposed Tabu Search algorithm:
- TOPTW Performance: The algorithm achieved comparable results to state-of-the-art algorithms on TOPTW instances, demonstrating its general effectiveness on related routing problems.
- MPISP Performance: For the newly introduced MPISP instances, the algorithm consistently generated high-quality solutions, achieving average ratios close to the upper bounds derived from the knapsack model. For instance, on 370 TOPTW instances, the average ratio was 0.9980, and on 672 MPISP instances, the results were also highly competitive.
- Component Analysis: The analysis of the algorithm's components showed that the ejection pool played a critical role in improving solution quality.
Limitations and Future Work
- No Direct Comparison for MPISP: As MPISP is a new problem, the authors could not compare their algorithm against existing specialized MPISP solvers. Their results serve as a benchmark for future research.
- Stochastic Nature: The Tabu Search algorithm is stochastic, meaning results can vary slightly between runs. While they ran instances multiple times, this inherent variability is a characteristic of such algorithms.
- Future Research Directions: The authors suggest future work could explore variants of existing vehicle routing models that incorporate time windows and waypoint concepts, as these are practical considerations. Further research could also focus on developing exact algorithms or more advanced heuristics for the MPISP.
Summary updated