Skill Vehicle Routing Problem With Time Windows Considering Dynamic Service Times and Time-Skill-Dependent Costs

Xiaoyuan Yan, Boping Xiao, Yiyong Xiao, Zhonghao Zhao, Lin Ma, Naichao WangIEEE Access 2019 · DOI

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.

The four stages of working efficiency over cumulative working time: Adaptation, Stable, Fatigue, and Overfatigue.

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).

Piecewise linear wage structure showing how costs increase across different work periods based on skill and time.

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

Abstract

Service processes in modern logistic systems tend to be highly specialized and intellectualized. However, some casual and unexpected behavior may occur, causing specific dynamic interactions among their many constituents. As such, the optimization and modeling of complex problems have become increasingly tough. Besides, technicians typically need to possess appropriate skills that match assigned tasks. Faced with real service scenarios, however, employees inevitably suffer from an increasing level of fatigue attributed to continuous work, resulting in a gradual decrease in the efficiency of workers over time. In this situation, the service time for a given task can no longer be treated as a constant, but instead, it should be treated as dynamic. Moreover, highly skilled technicians are usually paid higher than the junior ones with basic or lower skill level, which introduces new challenges in the optimization of service task schedules' problem. In this paper, we first present the skill vehicle routing problem considering dynamic service times and time-skill-dependent costs, in which the efficiencies of the workers are dynamically affected by their fatigue levels, and the costs, i.e., salaries paid to the employees, are related to skill levels and continuous work time. Furthermore, we develop a comprehensive and general mixed-integer linear programming dynamic-based model to formulate the proposed problem, which is directly solvable by MIP solvers for small-sized problems. We also initiate an iteratively dynamic neighborhood search (IDNS) algorithm that combines iterative partial optimization with dynamic neighborhood search to efficiently solve large-sized problems with near-optimal solutions. The comprehensive computational experiments were performed on the problems of different sizes to test the effectiveness and efficiency of the proposed model and solution approach. Some useful managerial insights were obtained from the computational results that can help decision-makers to determine cost-effective service routes and schedules in complex transportation-related issues.
BibTeX
@inproceedings{yan2019skill,
  author = {Xiaoyuan Yan and Boping Xiao and Yiyong Xiao and Zhonghao Zhao and Lin Ma and Naichao Wang},
  title = {{Skill Vehicle Routing Problem With Time Windows Considering Dynamic Service Times and Time-Skill-Dependent Costs}},
  booktitle = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2919963},
}
Figure