Knowledge Level Formalisation of Neighbourhood Search Optimisation Techniques

EPSRC/DERA Research Grant GR/M77888 (Joint Grants Scheme)

Principal Investigator: Andrew Tuson

Duration: 1st Oct 1999 - 31st Dec 2002 (39 months)

Value: 50,000 pounds

Last Updated 22/4/2003

Overview

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. Work in [5] has proposed a knowledge-based systems (KBS) view of the design of meta-heuristic optimisers and hence a series of design heuristics.

This work aimed to extend [5] by developing the underlying formalism further, constructing a system that embodies these principles, and evaluating this approach on a problem of real-world relevance. For a copy of the original proposal click here. For a copy of the IGR click here.

The Test Problem

The VRP domain is relevant to both the optimisation and operational research (OR) communities, as well as practitioners involved with real-world problems [6,7]. For the purposes of this proposal, VRPs are considered in their wider sense, including extensions such as time windows (VRPTW) or deadlines (VRPTD). Additional reasons for the selection of the VRP domain are given below.

The domain has been studied extensively, and therefore there is a sizeable literature to draw upon and compare against.
Standard benchmark problem instances, i.e [8] and others, are available to support empirical investigations and facilitate meaningful comparison with earlier approaches.
The work in [5] examined a limited range (ordinal, nominal, and permutation) of representations. The VRP domain has a richer range of operator types thus allowing a realistic test of whether this formalisation is workable in practice.

Personnel

Andrew Tuson is the principal investigator for this project. The work was undertaken by Eddy Parkinson under a project studentship.

References

C.R. Reeves. Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publications, 1993.
C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimisation: Algorithms and Complexity. Prentice-Hall, 1982.
D.H. Wolpert and W.G. Macready. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1):67--82, 1997.
Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Artificial Intelligence. Springer-Verlag, New York, 1992.
A. L. Tuson. No Optimisation Without Representation: A Knowledge-Based System View of Evolutionary/Neighbourhood Search Optimisation. PhD thesis, Edinburgh University, 1999.
F. Semet and E. Taillard. Solving real-life vehicle routing problems effectively using taboo search. Annals of Ops. Res., 41, 1993.
C. A. Hjorring. The Vehicle Routing Problem and Local Search Metaheuristics. PhD thesis, The University of Auckland, New Zealand, 1995.
J. E. Beasley. OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069--1072, 1990.