As part of the problem involves allocating which locations will be mown in a day and which will not, the first decision required is to decide which locations will be considered for inclusion in a route. From this selection, all the locations not in routes are placed in the pool of excess locations, from which locations can be swapped into and out of routes. Locations in the final excess pool will not be mown that day, but are likely to be included in a route the following day, as their grass length (and corresponding urgency) will have increased.
The mower routing and scheduling model follows most of the usual conventions of a typical time-constrained VRP, with the use of penalty functions as an extension to the usual distance-based objective function. The aim of the model is to construct routes that cover as many of the selected locations as possible, and to ensure that the mowing of the most urgent locations is scheduled within the expected finish time of the rounds. The lower the urgency of a location, and the closer it is to the depot, the later in the route it can be scheduled. Note, however, that it must always be preferable for a location to be placed in a route rather than in the pool of excess locations.
The four penalty functions in the model each serve a purpose. The Urgency Penalty penalises locations scheduled to have their mowing completed after the scheduled end of the eight-hour day based on their urgency, to ensure that the most urgent locations are mown within the scheduled eight hours. The Time to Depot Penalty ensures that locations scheduled after the eight-hour cut-off are relatively close to the depot. The Cricket Penalty strongly discourages cricket grounds from being scheduled after the eight-hour cut-off. Finally, the Pool of Excess Locations Penalty penalises locations that are not selected in any of the routes, based on their urgency.
The length of the routes is constrained to be less than or equal to the scheduled eight hours plus the two-hour buffer. The penalty on the pool of excess locations ensures that the slack on this constraint is minimised.
Due to the sheer size and nature of the problems we had to solve, 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. We based our initial heuristic on a tabu search for simple VRPs proposed by Barbarosoglu and Özgür (1999). Despite the popular idea that tabu search is better suited for VRPs, our tests found that solution times could be reduced significantly by using a simulated annealing move acceptance criterion rather than using a tabu list, without any noticeable loss in solution quality.
By the time we had finished adapting Barbarosoglu and Özgürs (1999) heuristic to create mowing rounds for City Care, only some of its original structure remained.
The first step was to construct a list of locations from which the heuristic would create its routes. If we were creating r routes, we ranked all the locations for a particular mower type in decreasing order of urgency, then selected the (8+2)r hours of most urgent mowing, and the next c (a constant) most urgent locations, to be on this list.
The original paper described two construction procedures, one random and one a nearest neighbour-type method, both of which we kept. Once the required r routes were constructed, the rest of the locations on the list were placed in the pool of excess locations. Please refer to the paper mentioned above for details of these two methods.
The search procedure, which we labelled the Route Search Method (RSM), involves iterating through two procedures and using a simulated annealing approach to neighbour acceptance. These procedures, the Basic Improvement Method (BIM) and Relative Improvement Method (RIM), incorporate different approaches to generating neighbouring solutions to the current solution. At the end of each iteration of RSM, the best neighbours found by BIM and RIM are compared, and the one with the lower of the two solution values is considered for acceptance. If the neighbour has an improved objective function value over the current solution, then it automatically becomes the current solution. Otherwise, the neighbour may be accepted if the standard simulated annealing criterion on the increase in objective function value (OFV) is met.
A single iteration of BIM involves swapping randomly-selected locations between two randomly-selected routes (or one randomly-selected route and the pool of excess locations), inserting the swapped locations into their destination routes, and performing a fully enumerated 2-opt procedure until no more improvements can be found. The insertion procedure finds the best feasible position in which to insert the moved location into the destination route, according to the penalty- and distance-based objective function. However, if one of the routes selected is the pool of excess locations (whereby order is irrelevant), the 2-opt procedure is not called after the locations are added to the pool. Multiple iterations of BIM are performed on the provided solution, with the resulting solution that has the lowest objective function value proposed as the neighbouring solution for consideration.
The key distinction between an iteration of RIM and an iteration of BIM lies in the way that RIM selects the locations to consider for swapping between the two chosen routes. Rather than randomly selecting the locations, RIM uses intelligent methods to make the selections, based on the position of each location relative to the centroid of its own route and that of the other route. The goal of this process is to remove locations from a route when they are relatively far from the other locations in that route and relatively close to the locations in the destination route.
Figure 1 below shows the overall structure of the heuristic. As explained above, both BIM and RIM incorporate the 2-opt and Insertion methods, each performed for a number of iterations. After constructing several solutions from each of the two construction methods, the First Improvement method develops each of them using RSM, to enable an educated decision as to which of the constructed solutions most warrants further consideration. The SASearch procedure brings together the whole process of finding routes for a single mower type, by incorporating the two construction methods, the First Improvement stage and the Major Improvement stage (which involves many iterations of RSM on a single solution in order to find the best routes possible).
The highest level of the heuristic involves the overall allocation of mower operators to types of mower. This process begins by running a preliminary SASearch process for each mower type, over a range of numbers of routes. For each of these solutions, a measure of their goodness is obtained by summing the urgencies of all locations for that particular mower type that have been left out of the routes. The allocations are then determined by considering first the standard configuration of mowers, and then investigating the marginal benefits of slight variations in these allocations. Following the allocation procedure, the cooling parameters are reset, and the solutions for the resulting allocation selected undertake a Final Intensification stage of the SASearch procedure.
Figure 1. The structure of the routing and scheduling heuristic
Barbarosoglu, G. and D. Özgür. 1999. A tabu search algorithm for the vehicle routing problem. Computers & Operations Research, 26: 255-270.
Return to Main Project Page