Roadside maintenance is a significant challenge for many territories worldwide. For safety reasons, these roadsides have to be maintained regularly, which has a substantial economic impact requiring a significant investment of staff and material. This paper addresses the problem of planning optimal trajectories of mowing machines within a dedicated territory in order to meet several objective criteria such as: minimising the travel distance, the number of mowing machines, as well as minimising the time and the cost associated with each yearly operation. Firstly, we define the mathematical methodology of the multi-objective criteria that we need to calculate. Secondly, we propose a clustering approach based on the k-means algorithm in order to identify the best sub-sectors of road sections that each technical centre needs to plan in order and maintain using existing equipment. Thirdly, we apply an optimal routing between each cluster based on TomTom API routing and identify the distance used to formulate our multi-objective optimisation criteria to minimise the cost and the use time associated with various mowing scenarios. Finally, we analyse the best setup to satisfy all criteria in the current case study area and present future projections of a local versus global optimisation approach.