The Project Requirements
Benefits of Implementation
About the Authors
The Routing and Scheduling Model
The Routing and Scheduling Heuristic
The GRASS Program
City Care Limited is responsible for the maintenance of over 1500 parks, cemeteries and roadside berms owned by the Christchurch City Council. Mowing the grass at these locations costs City Care approximately $2 million a year, and it is therefore vital that this operation be as efficient as possible. We were approached by City Care in February 2002 and asked to provide a more efficient system for their grass-mowing operations than the manually-operated fixed-schedule system presently in use.
City Care is under contract with the Christchurch City Council to maintain the length of grass at the locations on its asset list at between 20mm and 60mm at all times, and for the length of the grass at cricket grounds to be less than 40mm during the summer season. While these are not strictly “hard” constraints, if the grass grows much longer, complaints may be received from the public or from the Council’s auditors. A further complication to the requirements is the fact that during the cricket season, the outfields at cricket parks must be mown on both a Monday and a Thursday (or Tuesday and Friday if there is not enough time on the previous day), to ensure the grass is short enough for midweek training and weekend matches.
In this environment, increasing efficiency is achieved through minimizing variable costs and increasing the quality of service provided. Our research identified two areas in which this could be achieved. Firstly, monitoring more closely the length of grass at each location would increase the chance of locations being mown only when necessary, thereby decreasing the cost of having them mown too often, and reducing complaints from mowing too infrequently. Secondly, creating an efficient routing system would reduce the travelling time of each mower operator, thereby reducing fuel costs and increasing the total time they are available to mow in a day. Due to the facts that the length of the routes is constrained by time and that not every location needs to be mown, the routing aspect of the project was a combination of two different types of documented Operations Research problems: the Vehicle Routing and Scheduling Problem (VRSP) and the Vehicle Routing and Allocation Problem (VRAP).
The problem we faced was to decide each day whether each location should be mown (based on how urgently it needed mowing), and, given the type of mower required for each location, what route each mower operator should take around Christchurch that day. The optimal assignment of mower types to individual locations was ruled outside the scope of this project.
The estimated set-up and mowing times for each location supplied were fairly fuzzy, and most likely to be overestimated. For this reason, City Care required that the daily routes constructed be a couple of hours longer than the eight hours the mower operators actually have available. If the mowing times were in fact accurate, then it would be important in the interests of efficiency that the operator had a relatively short trip back to the depot. Therefore, it was necessary that for the final two hours of each route, the later in the day the mowing at a location would be finished, the closer that location must be to the depot.
Due to this uncertainty in the mowing times, the later in the day a location is scheduled to be mown, the less likely it is actually to be mown that day. Therefore, the longer the grass is at a location, the more urgently it requires mowing, and the earlier in the day its mowing should be scheduled. In addition, as not all locations selected for the routing heuristic may be included in the final routes, the more urgently a location requires mowing the more its inclusion in a route should be encouraged.
The sheer size and nature of the problems we had to solve meant that it was obvious we would have to use a heuristic rather than an optimisation technique, with a higher-level procedure to determine the best daily allocation. The heuristic we developed for the scheduling and routing combined aspects from the literature and original techniques, and extended a heuristic structure developed by two Turkish researchers.
The Routing and Scheduling Model and Heuristic
Obviously, if City Care were to implement the results of this project, the routing and scheduling heuristic would have to be packaged inside an easy-to-use interface, and come with a clear and concise user manual. The program would have to store data on each of the different locations, house the grass-growth model for estimating the length of grass at each location, contain the heuristic and allocation methods, and illustrate the daily routes on a map. We decided that this complete program and user manual, ready for immediate implementation, would be the major deliverables to our client.
The GRASS Program
The heuristic performed extremely well both on the set of data for which it was built, and when the data set was manipulated to test for over-fitting. Figure 1 below illustrates the influence of the time of day / travel-time penalty on the heuristic. Note that the locations scheduled to be completed after eight hours are much closer to the depot than most of the other locations on the route.
Figure 1. The structure of a route in terms of travel time to depot
Figure 2 below shows a typical graph of location grass length against scheduled location finishing time, calculated for one of the mowers’ routes. Very seldom were any truly urgent locations scheduled in the last couple of hours of a route, and there were never any very urgent locations placed in the pool of excess locations either.
Figure 2. The structure of a route in terms of grass length / urgency
The routes of an optimal solution to a distance only-based VRP or TSP will have no crossovers, and the routes will look like petals of a flower centred at the depot. As minimising total distance travelled was not the only aim of this heuristic, we cannot say with certainty what the optimal solution will look like – crossovers inside a route may indeed be best. However, due to the use of the modified 2-opt procedure, crossovers in the routes are rare, and the flower structure is certainly evident from the map plots of all the routes for a particular type of mower. The daily rounds created for any type of mower can be printed out by our program, as shown in Figure 3 below.
Figure 3. Map of Christchurch showing daily rounds for one type of mower
Using the pool of excess locations and multiple selection criteria over and above travel time certainly aids in constructing intelligent routes, as Figures 2, 3 and 4 above show. For example, if a location were far away from most of the other locations mown by the same type of mower, including it in a route as soon as its length reaches 60mm would cost a great deal in terms of travelling time. However, our penalties are tuned to allow it to be left in the excess pool for a few days until either its urgency becomes too great, or other locations nearby become urgent and are put in a route together.
With schedule of iterations we selected for the heuristic, the entire procedure takes on average 140 minutes to run for the seven types of mowers currently held (the computers used to test the program were P3 663 MHz.). This solution time is perfectly acceptable to City Care, as the entire set of routes can be created overnight. The program offers a contingency for breakdowns, creating a single route of the most urgent locations, with a much faster solution time.
Implementation of our system would obviously lead to more accurate monitoring of grass lengths and more efficient routing and scheduling of grass mowers. This achieves the overall aims specified in Section 1. Aside from the calculable benefits to City Care, we foresee a reduction in the amount of labour-intensive and skilled work required to create routes for the grass mowers. The only human activity required to run our program is in the form of data entry: ticking boxes at the end of each round when locations are mown, and entering mowing times if desired.
Many of the activities currently performed in a haphazard manner are automated in our program. For example, if a mower breaks down in the middle of the day, the operator usually returns to the depot, picks up a new mower (often of a different type) and returns to complete their original round. Our system can create a new round for the number of hours left in the day, and assigns the type of mower that can most reduce total urgency. Further, if a complaint is received about the grass at a location, its length in the system can be greatly increased, to ensure that it is mown the following day. Similarly, if a particular location must be kept strictly below the upper length limit, all that is required for it to be mown more frequently is to increase its growth rate – the system will always think the grass at the location is longer than it actually is.
One benefit of the weekly routes used in the current system is that the operators know in advance which locations they are going to be visiting every day of the week, which may suit them better for planning their routes. However, sharing locations around the operators is a better practice for auditing. Further, implementing daily schedules offers the best solution to breakdowns and non-completion of rounds.
Using real distances by road instead of scaled Euclidean distances would create routes that are more logical than some of the current ones, particularly given Christchurch’s geographical features (e.g. the rivers and estuary). Further, using a time- or road- dependant travel speed instead of a single average speed would be desirable.
On a wet day, the rounds created are likely to be far too long, due to an up-to-fivefold increase in mowing times. Applying a user-specified scale factor to all the mowing times would be one way of increasing them on a wet day, but it would be preferable to use some link between the weather data and the mowing times. Further, the longer the length of the grass, the longer it takes to mow; modelling this relationship would increase the accuracy of the mowing time estimates. Our program does use a weighted average of the most recent mowing times for each location (as entered by the system user) to calculate that location’s expected mowing time, therefore we consider that current estimates should improve with time.
Incorporating the efficient assignment of mowers to parks into the heuristic would be a very large (and possibly intractable) extension to the current model, but would allow a more detailed vehicle requirements study.
Dominic Heritage, the Operations Researcher for City Care, compiled most of the data for this project, which saved us many hours of sifting through timesheets. Along with his colleagues, Steve Chandler and Mark Aydon, he also gave several hours’ assistance to us in explaining the requirements of the project and their current mowing operations.
Our project supervisors, Dr Shane Dye and Dr John Giffin, provided invaluable expertise and assisted us in many of areas of the project. Dr Ross James also provided significant help with our software and ideas for the application of the heuristic.
Paul Stewart and James Tipping completed this Honours Project in partial fulfilment of the requirements for Bachelor of Science with Honours degrees in Management Science. Paul is in his fourth year of study at the University of Canterbury, having focused on the fields of Management Science, Economics and Finance. James is in his fifth year at university, having completed a Bachelor of Commerce degree in Economics and also majoring in Statistics. Both Paul and James are planning to commence doctoral studies in the Department of Management in 2003.
Return to Contents