The routing service order problem can be characterized as an adaptation of the vehicle routing problem with multi-compartments with limited and heterogeneous fleet. In this work a GRASP heuristic with path relinking is presented for solver the problem. Computational tests based on instances of the literature were performed. The results obtained were compared with three studies in the literature. The average cost obtained in the 14 tested instances is less than two of the works used as reference and provides new best solutions.