Abstract
Modern logistics systems require highly specialized skills, yet human factors like fatigue often introduce dynamic variables that traditional models ignore. This paper introduces a Skill Vehicle Routing Problem with Time Windows (Skill VRPTW) that accounts for dynamic service times driven by technician fatigue and costs dependent on both skill levels and cumulative work time. We propose a mixed-integer linear programming (MILP) model and an Iteratively Dynamic Neighborhood Search (IDNS) algorithm to solve this complex optimization problem. Computational experiments demonstrate that the IDNS algorithm efficiently provides near-optimal solutions, offering significant time savings over standard solvers for large-scale instances.
Introduction
In traditional logistics and service scheduling, task duration is typically treated as a constant. However, in real-world scenarios, human efficiency is not static. Technicians possess varying skill levels, and their performance inevitably declines due to fatigue from continuous work. Furthermore, labor costs are rarely flat; senior technicians command higher wages, and overtime thresholds introduce non-linear cost structures.
This research addresses these complexities by modeling the Skill Vehicle Routing Problem with Time Windows (Skill VRPTW) with two innovative variables: dynamic service times and time-skill-dependent costs. The goal is to optimize service routes and schedules while minimizing total costs, ensuring that tasks are matched with appropriately skilled workers within their specific time windows.
Modeling the Human Factor: Fatigue and Efficiency
A core contribution of this work is the integration of a fatigue model into the routing problem. Unlike static models, this approach recognizes that a technician's efficiency changes throughout the day. The researchers divide the work period into four distinct stages: the Adaptation Period, the Stable Period, the Fatigue Period, and the Overfatigue Period.
As shown in Figure 3, efficiency peaks during the stable period and drops significantly as the technician enters the overfatigue stage. By modeling the reciprocal of efficiency, the researchers maintain a linear and solvable framework while accurately reflecting that tasks take longer to complete as the workday progresses.
Time-Skill-Dependent Wage Structures
Beyond fatigue, the model incorporates a sophisticated wage structure. Wages are not just a product of hours worked; they are influenced by the technician's skill level and specific time thresholds that trigger higher pay rates (e.g., overtime).
Figure 6 illustrates this piecewise linear cost function. This allows the model to navigate the tradeoff between assigning a highly skilled (and more expensive) technician who can complete a task quickly versus a lower-skilled technician who costs less per hour but may take longer, potentially pushing the schedule into expensive overtime zones.
Methodology: The IDNS Algorithm
While small-scale versions of this problem can be solved using standard Mixed-Integer Linear Programming (MILP) solvers like CPLEX, the problem becomes computationally "explosive" as the number of tasks increases. To address this, the authors developed the Iteratively Dynamic Neighborhood Search (IDNS) algorithm.
The IDNS algorithm employs a "Fix-and-Optimize" strategy. It takes an initial solution and iteratively "unfixes" a small subset of variables (a neighborhood). A standard MIP solver then finds the optimal configuration for just that small neighborhood while the rest of the schedule remains frozen. To ensure the entire schedule is refined, the algorithm uses a Frequency Priority Policy (FPP), which tracks which nodes have been optimized least frequently and prioritizes them for the next iteration.
Key Results and Insights
The proposed model and algorithm were tested against a comprehensive set of generated instances ranging from 5 to 35 tasks. The results highlight several key findings:
- Computational Efficiency: For large-scale problems, the IDNS algorithm achieved high-quality solutions while requiring 90.8% less CPU time than the standard CPLEX solver.
- Solution Quality: IDNS identified the best-known solutions in 19 out of 20 large-scale instances, often outperforming the solver when restricted by a two-hour time limit.
- Workload Balancing: A significant managerial insight is that balancing workloads across a team can be more cost-effective than over-utilizing a single "star" technician. By preventing workers from reaching the "overfatigue" stage or high-overtime brackets, the total operational cost is reduced.
Conclusion
By accounting for the dynamic nature of human performance and complex wage structures, this research provides a more realistic framework for workforce scheduling in logistics. The IDNS algorithm offers a practical tool for decision-makers to manage specialized mobile workforces efficiently, balancing the need for speed, skill, and cost-effectiveness in increasingly complex service environments.
Summary updated