A Multi-chromosome Genetic Algorithm For Multi-depot And Multi-type Vehicle Routing Problem

With the rapid development of social economy,large-scale logistics and transport enterprises and even the conglomerates in possession of various kinds of parking lots and vehicle models are emerging quickly.Mere consideration of basic vehicle routing problem that involves only one depot and one type of vehicle is insufficient to meet the needs of social development.Multi-depot and multi-type routing problem is in urgent need of solution.However,due to two constraint conditions of "multi-depot" and "multi-type",the vehicle routing problem,which is complex in its nature,becomes increasingly difficult to deal with.In this paper,aiming at improving the efficiency and the quality of the solution to the problem of multi-depot and multi-type routing,the mathematical model of the problem is established,and the multi-chromosome genetic algorithm is designed to carry out an explorative study on vehicle routing problem with multiple constraint conditions.The main contents of the thesis are as follows:(1)Given the basic description of the problem,the optimization target and constraint conditions of the problem are identified.The variables are represented by three subscripts respectively,and the corresponding mathematical model of vehicle flow is set up.(2)A multi-chromosome genetic algorithm,which is different from traditional genetic algorithm,is designed for multi-depot and multi-type routing problem and its mathematical models.Several key techniques of this algorithm are elaborated,and the specified steps of the algorithm are given.(3)The validity and feasibility of multi-chromosome genetic algorithm are verified by multi-group experiments of computational examples.A set of contrast experiments with traditional genetic algorithm is designed to help inspect the performance of multi-chromosome genetic algorithm.The experiments show that the multi-chromosome genetic algorithm features not only high search efficiency and fast convergence speed,but also high quality and stability of thesolution.The validity and practicality of the algorithm in solving the puzzle of multi-depot and multi-type routing are proved.This study is an intersect and combination of organization optimization technology and artificial intelligence,offering beneficial exploration about the solution to the hot and difficult problem of multi-depot and multi-type routing.The research results of the paper are the extension to the genetic algorithm.It can also be applied to other multi-constrained vehicle routing problems.