A Genetic Clustering Method for the Multi-Depot Vehicle Routing Problem
A clustering method based on a genetic algorithm for solving the multi-depot routing problem is proposed. An efficient post optimiser enhanced by reduction tests is embedded into the search to further improve the solutions. Preliminary results, based on a
- PDF / 858,039 Bytes
- 4 Pages / 595.278 x 793.684 pts Page_size
- 96 Downloads / 181 Views
1
S. Salhi1 , S. R. Thangiah2 and F. Rahman 2 Management Mathematics Group, School of Mathematics and Statistics, University of Birmingham, UK. 2 Computer Science Department, Slippery Rock University, USA.
Abstract A clustering method based on a genetic algorithm for solving the multi-depot routing problem is proposed. An efficient post optimiser enhanced by reduction tests is embedded into the search to further improve the solutions. Preliminary results, based on a set of problems given in the literature, are encouraging.
1
Introduction
In this paper we introduce an adaptive clustering method based on geometric shapes using genetic algorithms for solving vehicle routing problems with multi-depots. The classical vehicle routing problem (VRP) consists of a set of customers, with known location and demand, and a set of vehicles, with a limited capacity, that are to service the customers from a central location refered to as a depot. The routing problem is to service all the customers without overloading the trucks while minimizing the total distance travelled and using the minimum number of trucks. Heuristic approaches as well as exact methods exist for the VRP [4,6]. The multi-depot vehicle routing problem (MDVRP) is an extension of the classical vehicle routing problem with vehicles starting from different depots. The constraints of the problem, are similar to the ones of the VRP besides that each vehicle starts and finishes the delivery from the same depot. The primary objective of the problem is to minimize the total number of vehicles used, in addition to minimizing the distance travelled by the vehicles. This problem seems to suffer from a shortage of published work although, in practice, it is unlikely that a distribution system operates from one single depot only. The MDVRP problem can be formulated as a mixed integer linear program [8]. It can be shown that exact methods are suitable for problems of limited size only. Heuristics seem to offer the best way to find good solutions to this large NP-hard
G. D. Smith et al., Artificial Neural Nets and Genetic Algorithms © Springer-Verlag Wien 1998
problem. One commonly used technique for solving the MDVRP is a two phase approach; the customers are first allocated to their nearest depots and then for each depot the VRP is solved. Refinements are usually added to improve the obtained solutions. Past work on MDVRP is summarised in [11]. Chao, Golden and Wasil [1] developed a composite heuristic where a slight deterioration in the objective function is allowed in their one point move procedure. Refinements are also added. Renaud, Laporte and Boctor [9] use diversification and intensification in the implementation of their tabu search based method. Salhi and Sari [11] developed a multi-level composite heuristic which is enhanced by suitable reduction tests. The idea is to avoid local optimality by using a different improvement procedure whenever a local optima is encountered. This approach has produced competitive results while requiring only a fraction, say 20%
Data Loading...
