Research On Approximation Algorithm For Heterogeneous Vehicle Routing Problem

Vehicle routing problem is the basic route planning problem in graph theory, and has widely application in the postal system transport. Researching on the structure and properties of the vehicle routing problem and its variants, and designing feasible and efficient algorithm has been a hot research field in operation research.Heterogeneous vehicle routing problem is a important class of variant problem of vehicle routing problem, which considering the heterogeneity of the vehicle and customers. Heterogeneous vehicle routing problem is abstracted from more complicated route programing problem in real world, then it is widely concerned by researchers in recent years.First of all, this paper deeply researches the structure and properties of2-heterogeneous minimum spanning forest problem which is associated with heterogeneous vehicle routing problem. This paper constructs polynomial reduction from3-CNF satisfiability problem to2-heterogeneous minimum spanning forest problem, and prove the determination form of2-heterogeneous minimum spanning forest problem belongs to NP-complete. The conclusion is extended to k-heterogeneous minimum spanning forests problem, so as to determine the computational complexity of heterogeneous minimum spanning forest problem, which provides the theoretical foundation for designing approximation algorithm for this problem.Then, since vehicle routing problem belongs to NP-hard, it is difficult to design exact polynomial algorithm for it. Based on an approximation algorithm of2-heterogeneous minimum spanning forest problem, this paper constructs heuristic loop of vehicles routing, uses randomization technique on initial vehicle loading, and proposes the first randomization approximation algorithm, RAHVRP algorithm, for2-heterogeneous vehicle routing problem with customers’ demand is1. Time complexity of RAHVRP algorithm is polynomial, and approximation performance analysis of RAHVRP algorithm argues that approximation ratio of RAHVRP algorithm is (2+2n/min{Q1, Q2})α, where n is the number of customers, Q1and Q2are vehicle capacity, and a is the approximation ratio of approximation algorithm for2-heterogeneous minimum spanning forest problem. Based on the hypothesis that vehicle capacity is never greater than the number of customers, and selecting the minimum cost tour formed by all possible initial loading, this paper proposes DAHVRP algorithm, which derandomizes RAHVRP algorithm.Finally, this paper uses experiment to verify feasibility of RAHVRP algorithm and DAHVRP algorithm. Analysis of the experiment data verifies the approximate performance of the algorithm is consistent with the theoretical analysis. Experiment shows that the approximation performance of algorithm on random instances with no more than100customers is very good, and actual approximation ratio is less than3.2a.