Vehicle Routing Problem With Time Windows And The Study Of Heuristics

Vehicle Routing Problem is a class of optimization problems, of which the objective is to construct a set of feasible routes to reduce transportation costs. The correlative theories and methods have great application values for reducing the logistic cost, so they are always the hotspot of operations research and combinatorial optimization domains. In recent years, the vehicle routing problem has generated a lot of branches, such as open vehicle routing problem, multi-depot vehicle routing problem, pickup and delievery problem, vehicle routing problem with time window, periodic vehicle routing problem and so on, and many improvements have been achieved. While the vehicle routing problem has been widely applied to many aspects in real life and production, such as mail delievery, goods delievery and vehicles scheduling and so on, great benefit has been gained.In real life there is a class of vehicle routing problems: the customers have strict limit to their service time, and they hope they can be served in appointed time intervals, so the capacity constraint and the time constraint will be considered simultaneously while constructing the routes. This class of problems is called Vehicle Routing Problem with Time Window, in which the time intervals are called time window. Since the time window is introduced, the vehicle routing problem with time window is harder to solve, so it is always one of the most important branches in vehicle routing problems. The models and methods about vehicle routing problem with time window and its extended problems are studied in this paper, the main contributions of this paper are summarized as follows:(1) A rule called "First-expired-first-served" is proposed to solve the vehicle routing problem with time window and its extended problems. The vehicle routing problem with time window and its extended problems have been proved to be NP-Hard, and heuristic methods are usually used to gain satisfying solution. This paper studies the basic vehicle routing problem with single time window under time independent, analyzing many common algorithms and proposed a rule which is called first-expired-first-served. Then the corresponding heuristic algorithm is improved to solve the extended problems. Experimental results show that the algorithm has better performance in mostly conditions.(2) A model about the vehicle routing problem with multiple time windows is built and the heuristic algorithms are used to solve it. In real life such as parcel delievery, the customers often have serval time windows. Now the correlative research is few and the model of single time window can not be used to handle the problems correctly. This paper studies the characters of vehicle routing problem with multiple time windows, introduces the "virtual customers" concept to transfer the problem to vehicle routing problem with single time window, then builds a vehicle flow model about vehicle routing problem with multiple time windows and proposes heuristic algorithms.(3) The model about the vehicle routing problem with time window under time dependent is built and the heuristic algorithms are used to solve it. The basic vehicle routing problem with time window consider the speed as a constant, but in real life the speed is usually alterable along with the different time segments, which is called vehicle routing problem with time window under time dependent. Because the time-varied condition is closer to real condition, the correlative research has attracted more and more attention. This paper defines the speed as a time-piecewise function and builds the vehicle flow model of vehicle routing problem with time window under time dependent, and then uses the heuristic algorithms to solve the problem.(4) The simulated annealing algorithm is introduced to solve the extended problems of the vehicle routing problem with time window. This paper mends the simulated annealing algorithm to solve the extended problems of the vehicle routing problem with time window, and simplifies the neighborhood to improve the efficiency. Experimental results show that the improved simulated annealing algorithm can solve the vehicle routing problem with time window and its extended problems efficiently.