A Mode And A Hybrid Algorithm For VRPTW

Distribution plays an important role in logistic system, it is the integration of a series of logistic campaign in a narrow sense, and logistic distribution requires delivering the right commodities to the right place by the right method at the right time. Vehicle routing problem involves the design of a set of minimum-cost vehicle routes, delivering the right commodities to the right location by the very method at the very time. So vehicle routing problem represents a very important part of any logistic distribution systems and they are named as one of the most successful areas in Operations Research in the past decades.In this dissertation, the main research work and innovative points as follows:We firstly describe the characteristics and classification of these problems, and the state-of-the-art in the solution algorithms. On the base of reality, we purpose the research problem—vehicle routing problem with time window (VRPTW) and construct a mathematical model: defines an objective function. Meanwhile,we give a review of the past research on vehicle routing problems and their solution methods, establishing the base of algorithm in this dissertation. In this paper,we propose a two-stage optimization strategy for VRPTW. In the first step, for constructing a good initial solution ,this work used the stochastic PFIH, which based on the algorithm known as Push-Forward Insertion Heuristic (PFIH), guaranteeing the diversity of the initial solution,at the same time , give a limit in the process of the constructing initial solution, realizing the filtration of initial solution. The producing mechanism of the new solution is betterment of large neighbor search, then a different hybrid system based on the combination of SA and LNS is proposed to optimize the initial solution .In the second step,a regression iterative strategy is put forward to tune time windows for the customers and figure out the best time for each vehicle departing, it can make the total waiting time zero. Finally, this method is implemented on computer in VC++. It is proved by the experiment that the hybrid strategy can solve VRPTW efficiently and quickly .Comparing with other algorithms, it has practicality and effectiveness, simultaneously, author provide an efficient algorithm to solve VRPTW.