zbMATH — the first resource for mathematics

Polynomial formulation and heuristic based approach for the \(k\)-travelling repairman problem. (English) Zbl 1390.90580
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.

90C27 Combinatorial optimization
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI