Researches On Genetic Algorithm For Multi-Objective Vehicle Routing Problem

As one of classical OR problems, vehicle routing problem (VRP) can be described as one of finding a set of routes for a fleet of vehicles which have to service a number of customers with different demand quantities from a central depot in order to achieve some purposes, such as to minimize the total distances of routes, to minimize the total costs of vehicles or to minimize the routing times of vehicles and so on. VRP has been widely applied into many fields in science and engineering applications and a lot of real-world transportation problems can be translated into different variants of VRP. Since VRP has been proved to be NP-hard, the large-scale VRPs have usually been solved using the intelligence-based optimization algorithms.With the development of economics, the progress of science technology and the diversification of people's individual demand, more and more practical applications require to consider multiple objectives, which is just the reason why multi-objective optimization problems has become one of research topics in OR community recently. However, it is noticeable that the researches on VRPs rarely consider multiple optimization objectives at present. Many research issues especially on the design of solution algorithm in multi-objective VRPs are worthy to be further researched.Based on the mechanism of system engineering, this thesis utilizes the relevant theories and methods from the fields of OR and evolutionary computation to study and investigate the design of a genetic algorithm (GA) based solution algorithm for multi-objective VRPs. The main contents of this thesis can be described as follows.(1)Reviews on the relevant research works. The research works on VRP and its solution algorithms, multi-objective optimization theories and methods are introduced in brief respectively.(2) Models on different VRPs. The models of a simple VRP and a VRP with time windows are given respectively and then a multi-objective VRP, which objectives are to minimize the total routing cost of vehicles and to maximize the total satisfaction degrees of customers respectively, are modeled mathematically.(3) Design of solution algorithms for VRPs. The solution algorithm for the single-objective VRP is investigated firstly, where three different coding schemes are compared their effects in the simulation experiments considering that coding is a major challenge GA met in solving VRP. Inspired by the algorithm mechanism of MOEA/D, which is known as one of classical multi-objective evolutionary algorithms, a new multi-objective GA is designed for multi-objective VRPs based on the above conclusions in GA for single-objective VRP.(4) Simulation experiments. The strength and weakness of the proposed multi-objective GA is to examine based on a set of multi-objective experimental cases, which are generated from the Benchmark problems in VRPLIB. In addition, several key parameters and operators are also evaluated their influence degrees upon the performance of proposed algorithm in the simulation experiments.(5) Conclusions. The research works in this thesis are summarized with discussions on the future work.