Genetic Algorithms For Two Classes Of Vehicle Routing Problems

Both in the logistics field and scientific research, the vehicle routing problem is often taken into account. This problem is a typical combinatorial optimization problem, and not only is it very important in theoretical study, but has also important practical value and economic benefit. There exist various vehicle routing problems,and different mathematical models and algorithmic approaches are adopted for dealing with different type of problems. Considering the complexity of the problem,as main solution approaches, some intelligent algorithms, such as genetic algorithms,particle swarm optimization algorithms, and simulated annealing algorithms, etc,have been applied to solve the corresponding models. In this thesis, two genetic algorithms with local search techniques are developed for dealing two types of the vehicle routing problems, respectively. The detailed work is as follows:1. For the vehicle routing problem with capacity limitation, a genetic algorithm based on local searching technology is designed. In the proposed local search procedure, the sub-sequence of the customers is first chosen by using a probability selection scheme. Then the sub-sequence is optimized which makes current path improved. The experimental results show that the local search method can effectively improve the efficiency of the algorithm. In addition, in order to better produce new crossover offspring, a crossover operator based on the summation of two parent individuals is presented. The characteristics of the operators is that the same parent individuals can very likely generate one different offspring from the parent, which can make the algorithm efficiently generate new individuals in later runs and maintain the diversity of population.2. For the vehicle routing problem with time windows, in most of the existing researches, the "hard" time window constraints are often adopted, namely, the time window must be strictly met. In the thesis, the time constraints are soften, and based on a penalty function technique a bi-objective optimization model is presented. In this model, the time constraints are added and put into the objective function as a penalty term. After doing so, one can control the time constraint violation bychanging the penalty factor value. In addition, in order to efficiently solve the proposed model, a bi-objective genetic algorithm is developed by combining a new local search scheme. Numerical experiments show that this algorithm is feasible and efficient.