Models and valid inequalities to asymmetric skill-based routing problems

Given a directed network, where a set of skills S-j is required to serve each node j, and given a set of available technicians, each one having abilities described through a set of skills, we study the problem of defining the tour of each technician in such a way that each service requirement is fulfilled by exactly one technician, and proper skill constraints are satisfied. These constraints state that the service requirement at node j can be operated by any technician having, at least, all the skills in Sj. Given travelling costs for the arcs of the network, which are technician dependent, we want to determine a set of tours of minimum cost which satisfy the skill constraints. This problem, named asymmetric skill VRP (A-SKVRP), originates from a real application arising in Field Service. Also, it is strongly related to Home Care applications. Starting from the preliminary results in Cappanera et al. (Network optimization. 5th international conference, INOC 2011, Hamburg, June 2011. Lecture notes in computer science, Springer, Berlin, vol 6701, pp 354-364, 2011), where a special case is addressed, we propose a hierarchy of three ILP flow-based models for A-SKVRP, which is based on increasing levels of disaggregation of the flow variables used to prevent subtours. The computational results of a first pool of experiments show that the LP bounds produced by the most disaggregated model are very tight, but at the expense of very large computational times in most cases. This becomes critical as the number of involved nodes and skills increases. Therefore, in the second part of our study, we enhance the LP bounds obtained with the weaker models by adding, in a cutting plane fashion, cut constraints. As a result of this enhancement, the intermediate model proves to be competitive against the most disaggregated model in computing tight lower bounds, especially as the number of the nodes and of the skills increases. This model combined with the proposed valid inequalities thus qualifies as an efficient tool to address skill-based routing problems arising in application contexts such as Field Service and Home Care.