A greedy randomised search heuristic for time-constrained vehicle scheduling and the incorporation of a learning strateg
- PDF / 555,199 Bytes
- 9 Pages / 595 x 842 pts (A4) Page_size
- 44 Downloads / 161 Views
#1998 Operational Research Society Ltd. All rights reserved. 0160-5682/98 $12.00 http://www.stockton-press.co.uk/jor
A greedy randomised search heuristic for timeconstrained vehicle scheduling and the incorporation of a learning strategy JB Atkinson University of North London In this paper, a greedy randomised heuristic is applied to a complex vehicle-scheduling problem with tight time windows and additional constraints. Two forms of adaptive search are identi®ed, which are referred to as local and global adaptation. In both cases, the calculation of the greedy function is modi®ed by an amount which measures heuristically the quality of the partial solution that is obtained when a decision is made. One use of global adaptation is an approach which is referred to as a learning strategy since it involves an attempt to learn from previous mistakes by an appropriate updating of the greedy function from one run of the heuristic to the next. Such a learning strategy forms the main focus of this paper. Experimental results show that it is potentially a powerful heuristic device, since it greatly enhanced the effectiveness of those methods that had previously been applied to this problem; that is, a greedy randomized heuristic which also incorporated a look-ahead strategy and a version of the well-known savings method. It is suggested that learning strategies of the general type introduced in this paper have potential for application to other combinatorial optimisation problems. Keywords: GRASP; heuristics; learning strategy; time windows; vehicle scheduling
Introduction This paper is primarily concerned with vehicle scheduling, but the general methodology used is also applicable to a wide range of combinatorial optimisation problems (COPs) arising in management systems and operations. An extensive bibliography of research on vehicle scheduling1 re¯ects the large amount of research that has been carried out, principally from an OR perspective. Recent research has also included contributions from the AI community (see, Nygard et al2 and Potvin et al3). The particular problem considered here, and for convenience referred to below as problem VSP, is closely related to a standard routing problem known as the Vehicle Routing Problem with Time Windows (VRPTW), which can be stated as follows. A set of customers at known geographical locations has to be supplied by a ¯eet of vehicles from a single depot. Each customer has a speci®c demand that must be satis®ed during a particular period of time, called a time window, and each vehicle has a capacity which limits the total number of customer demands that it can carry at one time. In addition, each route must supply a subset of the customers and start and ®nish at the depot,
Correspondence: JB Atkinson, School of Communications Technology and Mathematical Sciences, University of North London, Holloway Road, London N7 8DB, UK. email: [email protected]
while satisfying the vehicle capacity and time-window constraints. The objective is usually to ®nd a set of routes whose total le
Data Loading...
