Heuristics and Optimization
July 12th, 2011 2:20 pm Category: Optimization, by: Joe Litko
You might think the title should be ‘Heuristics or Optimization’, implying a choice. But often the two approaches work well together with heuristics speeding an optimization process. The Wikipedia definition of heuristic calls it an experienced-based technique for problem solving, learning, and discovery. Wikipedia also mentions using heuristics to find a good enough solution and describes them as ‘strategies using readily accessible, though loosely applicable, information to control problem solving.’
Those descriptions do not emphasize another aspect of heuristics – there is generally an underlying concept that informs the heuristic. There is a good reason why we think it will work well in the majority of cases. For example, an angle sweep heuristic is often used when designing routes for pickup and delivery from a central hub. Those routes are candidates for selection in a formal optimization. The designed routes look a lot like the petals of a daisy.
The heuristic starts out by heading north and picking locations close to that direction on the way out and back. How far out the route goes is a property of vehicle capacity or time limitations. The next route to be generated starts out slightly east of north and follows the same limitations and usually overlaps many of the locations on the first route. Once the entire compass has been swept, the best set of routes to cover all locations is selected by an optimization. In the example the heuristic becomes a front end for the optimization.
Another example comes from a driver scheduling problem. Suppose a set of drivers must pick up some commodity from a set of locations for processing at a central plant. Each trip in this example is an out-and-back because of the nature of the commodity, i.e. only one location can be visited. Drivers pick up multiple loads in a day, and each location requires multiple visits. The pickup times are fixed because of other problem features. One approach is to simply allow all combination of driver-load-location pairings and let an optimizer grind away.
But there are other desirable features of the solution: equalizing number of loads among drivers, and keeping driver dead time between loads to a minimum. Specifying all the driver loads by some simple heuristic, e.g. send a driver out for the next load as soon as possible, usually ends up with some loads that cannot be covered. A totally greedy approach fails.
An approach that seems to work well in this case is to consider some drivers for early loads and some for late loads. Work from the front of the early loads assigning each of the early drivers the first two loads they can feasibly complete. Then work from the end of the late loads assigning the last two loads of the late drivers as the last two loads they can feasibly complete.
The loads in the middle and the drivers that are not considered early or late are handled by the optimization. Notice that the heuristic does well on the driver gaps and guarantees that most drivers automatically get two loads, which is a good base in this application. It also serves to speed the optimization by reducing the pairings to be searched while preserving enough flexibility to get a solution.
Furthermore, the heuristic is flexible in that one can choose how many drivers to consider early or late and how many of their loads to nail down heuristically. Most importantly the heuristic gets better solutions than the optimization finds in any reasonable time. So while the optimization must have that best solution out there, it will not find it in the time frame the scheduler has to work within.
My experience is that flexibility is one of the key properties in any good heuristic. Adaptability to new situations is also a feature of good heuristics. One final example illustrating adaptability is based on an algorithm called ‘Toyoda’s Algorithm’. I have applied this particular idea to a number of situations.
In this example it is applied to sequencing the unloading of containers at a port. Each container holds a selection of parts which have to be processed by various work centers prior to shipment out of the port. A manifest shows the selection of the parts and it is known how much work is associated with a given part at a work center. Not every work center can process every part type. The objective is to get all the work centers to end their day at the same time and to keep all the work centers busy throughout the day.
The approach is easy to understand in two dimensions. The X and Y axis represent the available work time of two work centers, e.g. eight hours. The arrows represent the amount of work delivered to a work center by a given container. The dashed line is the ‘ideal path’ — equal amount of work at each work center throughout the day.
The heuristic simply needs to loop through all available containers at each iteration and always try to get back onto the ideal path. Penalties for deviation are totally flexible in that small deviations can be without penalty while sizable ones are some function that penalizes them heavily. Other problem features can be captured, e.g., buffer space at a work center, and incorporated in the penalty function. This is not a formal optimization, but it is speedy and good enough for the real world application.
The watchwords seem to be these. Look for the important features of a good solution. See if a simple rule or concept will drive the solution toward these good features. This is especially true when there is little or no economic benefit to the optimal solution. Try to develop a heuristic that is flexible in adapting to normal variance in instances of the data and can be tuned to choose between competing objectives.