Title: Polynomial formulation and heuristic based approach for the k-travelling repairman problem

Authors: Imen Ome Ezzine; Sonda Elloumi

Addresses: University of Sfax, GIAD/FSEG-Sfax, Route de l'aérodrome Km 4, BP 1088-3018 Sfax, Tunisia. ' University of Sfax, GIAD/FSEG-Sfax, Route de l'aérodrome Km 4, BP 1081 SFAX 3018, Tunisia

Abstract: 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.

Keywords: polynomial mathematical formulation; integer programming; k-TRP; travelling repairman problem; balanced k-means; clustering algorithms; heuristics.

DOI: 10.1504/IJMOR.2012.048928

International Journal of Mathematics in Operational Research, 2012 Vol.4 No.5, pp.503 - 514

Published online: 23 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article