Vehicle Scheduling Problem And Its Genetic Algorithm

Vehicle scheduling problem is to seek the optimal vehicle path so as to minimizetransport costs, in case of meet customer demand.Genetic algorithm is a search algorithm by simulate natural biological evolution,because strong capacity of global search and better robustness, it is an efectivemethod to solve the vehicle scheduling problem. This paper introduces the basicconcepts of genetic algorithms and the basic theory, and the selection operation,crossover operation and mutation operation of genetic algorithm are introduced indetail in this paper. The improved genetic algorithm is proposed based on thecharacteristics of vehicle scheduling problem.In this paper,combined the genetic algorithm and the vehicle scheduling prob-lems together, established a mathematical model based on minimum cost. Accordingto the problem of feasible solution structure, puts forward the corresponding geneticalgorithm, this algorithm adopts the priority coding and get feasible solution by de-coding. Crossover and mutation method is improved to get better results, thussolving the problem. Finally, empirical analysis verify the feasibility and validity ofvehicle scheduling model based on cost minimization transportation and the geneticalgorithm improved.The thesis consists of fve chapters:The frst chapter introduces the background, signifcance, and research status ofvehicle scheduling problem. The current research on vehicle scheduling problem canbe divided into single feld, Multi-depot and with time windows three categories.This chapter introduces several common models on the three kinds, respectivelybased on the shortest path, based on the shortest time and based on the minimum cost model.The second chapter, introduces the theory of genetic algorithm and the algo-rithm fow chart. According to the fow chart, it introduces the characteristics andprinciples of each operation. The selection operation, crossover operation and mu-tation operation are introduced in detail.The third chapter, studies multi-depot multi-type vehicle scheduling problem,andgives the minimum cost model. The cost includes two parts, transportation and thedriver’s salary. In the model, the driver wages are introduced,which can refect ac-tual reaction. The improved genetic algorithm are gave, using priority encoding tocustomers, by decoding can skillfully handle the problem that which car park sentwhat kind of motorcycle and service for which several customer. Through examplecalculation to verify the feasibility and efectiveness of the algorithm.The fourth chapter, researches on large-scale vehicle scheduling problem basedon partition, gives partition clustering method based on the geometric center ofdistribution center, the method reduce Multiple-depot problem to several single-depot problem cleverly, greatly reduced the complexity and computation of theproblem. Thu gives the minimum cost model. For genetic algorithm based oncoding and decoding is proposed subsection cross and subsection metamorphosis, itis well to retain the genetic characteristics of the father generation. Combined withthe examples comparison, contrasts partition and no-operation, the results show thesuperiority of genetic algorithm based on partition.The ffth chapter, studies the vehicle scheduling problem with time windows.First introduces the concepts of the hard time window and soft time windows, andthe penalty functions is used to solve the vehicle scheduling problem with hard timewindows and with soft time windows. Thu based on the minimum cost model andthe improved genetic algorithm solves vehicle scheduling problem. Example results show that this method is efective to solve this kind of problem.The sixth chapter, summary.