Optimised forage harvester routes as solutions to a traveling salesman problem with clusters and time windows

In this work we study a variant of the traveling salesman problem with additional constraints of clusters, time windows, and processing times at the cities. We apply this model to a real-world problem related to an agricultural cooperative that needs to optimise the routes of several harvesters, and where getting the exact solution has been proved to be hopeless for large instances (see Carpente et al. (2010)). We introduce, implement and test two different heuristic algorithms based on tabu search and simulated annealing philosophy, respectively. An exhaustive experimental evaluation over several sets of real data shows that the simulated annealing approach exhibits a solid performance even on the most complex instances, while the tabu search based approach worsens with complexity.1 Moreover, the optimised schedules corresponded to important economic savings. For this reason the cooperative has already successfully adopted the proposed heuristic in its regular planning activities.