Vehicle Routing Problem With Time Windows And Its Algorithms

Vehicle Routing Problem with Time Windows (VRPTW) can be deemed as distribution vehicle scheduling abstract, which is the core of the management of logistics and distribution in practice. It's derived from VRP by added time window constraints. So it can be described as:Make vehicles serve customers from the depot and vehicles need to return to the depot after service. Still provisions, each customer can only be served by one vehicle once, and the service time must be in specified time window that customers appoint before. Optimization objective of problem is how to choose appropriate routes path, which meet the constraints, finish all the needs and holds minimum total cost or maximum total profit. In practice many transport management problems can be abstracted as VRPTW, such as bank cash truck scheduling, postal delivery problems, factory waste recycling, the school bus routing, JIT production scheduling, etc. The dissertation focus on the three typies VRPTW (basic Vehicle Routing Problem with Time Window, Pickup and Delivery Problem with Time Window, and Open Vehicle Routing Problem with Time Window and Work Time), the main research work are as follows:We present a thorough study on Insertion Detection Methods of VRPTW. The main work as below:Firstly, we propose the definition and classification method of Insertion Detection Methods, and review the related literatures. Secondly, we prove the Push Forward Insertion Detection Method (PFIDM) mathematical, analyze the computational complexity. Analysis shows that, the computational complexity of PFIDM is corresponding to traditional insertion detection method based on time window constraint detection. Thirdly, the Time Difference (TD) and the Time Difference Insertion Detection Method (TDIDM) are put forward. We prove the necessary and sufficient conditions and analyze the computational complexity of TDIDM, which shows that the computational complexity of TDIDM is better than the PFIDM and traditional insertion detection method based on time window constraint detection. The simulation tests support our conclusion.This dissertation is to study the construction heuristics of VRPTW. Through introducing the classic insertion heuristics, we put forward the Time Difference Insertion Heuristics(TDIH); introduce the inspiration of heuristics, the algorithm framework. The simulation test the optimum parameters combination, compare this algorithm and classic insertion heuristics show that our solutions is better than the Solomon's insertion heuristics.Pickup and Delivery Problem with Time Windows (PDPTW) is also in-depth studied. We propose the Non Generation Genetic Algorithm (NGGA) to solve the PDPTW. Comparing to basic genetic algorithm, the proposed algorithm has the following features:The frist one is based on individual search mechanism. This mechanism can better keep excellent individual and the diversity of population. The second one is to improve the coding method. New code includes the earliest finish time, the late start time. This method not only includes customer ID, vehicle arriving customer order, but also can use TDIDM in cross process, mutation process, and initial solution generation process easily. The third one is to design the asymmetric matching cross operator, symmetrical matching cross operator, route cross and R1mutation operator, R2mutation operator which applicable to our NGGA. The simulation test shows that solutions of our algorithm are better than existing algorithms.Lastly, we discuss the open vehicle routing problem with work time and time windows, and its clonal selection algorithm. The main work is as the following:we present open vehicle routing problem with work time and time windows; establish the mixed integer programming model. Then the Non Generation Immune Clonal Selection Algorithm is put forward, the algorithm improved the clonal selection method, design R3mutation operator which suitable for this problem. The simulation test shows that the problem model is effective and the algorithm can get satisfactory solution within reasonable time.