|
|||||||
|
||||||||
Meta-heuristic optimisers such as evolutionary algorithms (EAs), simulated annealing (SA), and tabu search (TS) have proved to be effective heuristic methods for solving combinatorial optimisation problems [1]. Despite these successes, it has been acknowledged that the design of meta-heuristic optimisers often is ``somewhat of an art'' [2], and invariably an ad hoc design process is adopted in practice. Furthermore, efforts to develop universally effective `black box' optimisation methods have been shown to be futile by both theoretical work [3], and practical experience [4]. In this context, the need for principled design approaches is necessary if the development and successful application of these techniques is to continue in future.
One essential component for a principled design approach to these optimisers is to devise frameworks which usefully guide the design process. We have proposed a knowledge-level view of the design of meta-heuristic optimisers and hence a series of design heuristics [5].
This approach however required further evaluation to fully assess its potential. The research undertook such a evaluation of these design principles on a problem of military relevance, namely the convoy movement problem.
In the convoy movement problem (CMP), a number of military convoys must be moved from specified starting points to a variety of target locations with time deadlines on their arrival. Each of these convoys must be routed subject to a number of constraints: no simultaneous occupation of road segments by more than a single convoy, no overtaking and each convoy must satisfy its deadline for reaching its target location. Subject to these objectives the primary objective is to minimise the completion time of the final convoy, that is, the time at which the last vehicle (or tail) of the last convoy reaches its target location. A full description can be found in [6].
In summary, both exact and meta-heuristic approaches to the convoy movement problem have been investigated with limited success. In contrast, a recent approach by UEA, based on Lagrangian relaxation (LR) has proved highly successful, and has been extended to solve larger data sets consisting of 160 and 330 convoys.
The project proposal argued that the original meta-heuristic implementations are not as effective as they could be and that there is significant room for improvement in meta-heuristic optimisers, possibly even over the LR approach. This suggests that the convoy movement problem will provide an appropriate testbed for the evaluation of the concepts of principled design suggested in Tuson [5].
