Article Preview
Top1. Introduction
Vehicle Routing Problem (VRP), first proposed by Dantzig and Ramser (1959), belong to a class of NP-hard problems in combinatorial optimization. Solomon (1987) introduced the time-window factor into VRP and proposed VRP with time window (VRPTW), also known as on-time vehicle routing problem. The realistic and theoretical research on multi-objective VRPTW is of great significance in the research community.
The VRPTW problem solving methods can be divided into two categories: the precise algorithm and the heuristic algorithm. The heuristic algorithm has the advantages of global search ability, high solution efficiency, and more practicality in solving large-scale discrete problems (Zhang and Li, 2007). Linear programming was added to solving the VRPTW and a new optimization algorithm was used to obtain a good result for the dataset with more customer points(Desrochers and Desrosiers, 1992); The two-stage genetic algorithm(GA) was applied to VRPTW, constructed a good initial solution combined with the pre-phase interpolation method, used the tabu search (TS) algorithm to conduct local search multiple times and replaced the searched solution with the new solution, and achieved good effect(Alvarenga and Mateus, 2004); The heuristic algorithm was used to solve the large-scale VRPTW, the design of a large area search method for testing a variety of vehicle routing problems, the experiments results show that about one-third of the cases in many cases have obtained the current optimal solutions, and also prove that such methods have a good effect in solving large-scale VRP (Pisinger and Ropke, 2007); In multi-objective hybrid evolutionary algorithm, chromosomes can be arbitrarily changed in length to greatly enhance their local optimization ability, which leads to a great improvement of the VRPTW solution(Tan, Yang and Goh, 2006); Based on realistic examples, the relationship between the five goals (number of vehicles, driving distance, finishing time, waiting time and delay time) were be discussed(Castro and Silva, 2011); Both the number of vehicles and the distance traveled were be considered, and obtained better results by using the improved non-dominated Sorting Genetic Algorithm (NSGA-II) algorithm (Wei and Tung, 2012).