A national maintenance company outsources maintenance to numerous enterprises all over South Africa. Because their customer base is so large, the focus of this paper is only on the branch in the Gauteng region. Their technicians perform scheduled maintenance on variety of electronic devices, travelling to multiple customer locations in a day. Unscheduled jobs pop up and instead of re-planning routes, these jobs are simply added on top of the pile. Employees find themselves travelling back to areas they have already visited which is a waste of time and petrol. Workloads of employees are also unbalanced and so the company has both high overtime and idle time costs. The company requires a scheduling system which plans staffing in such a way as to reduce travel distances, balance the workloads of employees and satisfy customer demand. This problem was addressed by viewing and modelling it as a Travelling Salesman Problem. An initial solution was developed and thereafter a Genetic Algorithm is used to improve on this initial solution