Polynomial formulation and heuristic based approach for the k-Travelling Repairman Problem

In this paper, we propose a polynomial linear integer formulation for the k-traveling repairman problem (k-TRP) and a heuristic method. The latter is a k-means clustering algorithm used to efficiently assigning of customers to k groups. Two versions of k-means algorithm are tested: the k-means in its original version and the balanced k-means, which we propose in this context. After clustering, an optimised route is generated by a polynomial linear integer formulation for each customer in his allotted cluster. Computational results prove the efficiency of the proposed approach, especially when the balanced k-means algorithm is applied. Copyright © 2012 Inderscience Enterprises Ltd.