Polynomial formulation and heuristic based approach for the \(k\)-travelling repairman problem (Q1753757)

Summary: In this paper, we propose a polynomial linear integer formulation for the \(k\)-travelling 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.