The skill vehicle routing problem

Given a (complete) directed network, where a skill level s j is associated with each node j other than the depot, stating requirements for the associated service call, and given a set of available technicians, each one operating at a certain skill level, we address the problem of defining the tour of each technician, each one starting and ending at the depot, in such a way that each service requirement is fulfilled by exactly one technician, and proper skill level constraints are satisfied. These constraints state that the service requirement at node j can be operated by any technician having a skill level at least s j. Given travelling costs for the arcs of the network, which are skill level dependent, we want to determine a minimum cost set of tours which satisfy the skill level constraints. This problem, named Skill VRP, originates from a real application context and it specializes, to some extents, the Site Dependent VRP (SDVRP) and, thus, the Periodic VRP. Furthermore, it shows strict relationships with Home Care Scheduling problems. Various ILP formulations are proposed for Skill VRP, which are tested on a large suite of randomly generated instances. The obtained results show that the stated problem may be very difficult to solve exactly. However, some of the proposed models produce LP bounds which are very close to the optimum cost, and which can be determined in an efficient way. Thus, these ILP models constitute a very promising starting point for the solution of Skill VRP, and for the design of efficient cutting plane approaches for real application extensions.