A Novel Heuristic For Vehicle Routing Problem And Its Application In Injection Molding Scheduling

The vehicle routing problem(VRP) is one of the most widely studied combinatorial optimization problems. Injection molding scheduling(IMS),if modeled as a vehicle routing problem with time windows,can be solved with algorithm specifically designed to deal with the VRPs, and the heuristic is the mostly common algorithm for such problems. Existing heuristics which have widely been used may suffer from the deficiency of unsatisfactory performance and heavy computation burden. For large-scale optimization problems, problem reduction which transfers the large-scale optimization problems into smaller ones can be regarded as one of the effective solutions to the problem. This thesis focuses on the design of a novel heuristic for large-scale VRPs based on problem reduction and its application in the IMSs. The main work is listed as follows:1) A fast multi-neighborhood iterated local search algorithm(FMNILS) is proposed. It is known that the evaluation of neighborhood solutions accounts for most of the time used for a local search based algorithm. Therefore, a fast feasibility assessment strategy for the VRP neighborhood solutions is put forward. The strategy embeds such constraints as time windows, capacity as well as maximum traveling distance into client nodes information. The computational complexity of feasibility assessment for the neighborhood solution is reduced to O(1), which improves the computational efficiency of the algorithm. By constructing a biased instance for the original VRPs and using variable length coding for the feasible solutions, the VRPs can be solved with both the number of vehicles and the traveling costs being optimized simultaneously. Experimental results show that the proposed algorithm can obtain a satisfaction solution of VRPs in a short time.2) A reduction iterated local search(RILS) is put forward. Feasible solutions can be regard as a combination of a set of basic elements. The improvement of the basic elements will result in a better solution. Problem reduction refers to sealing down of a large-scale optimization problem through such techniques as fixing(solidifying) the better components(basic elements) in the feasible solutions. The selection of the better basic elements depends on the backbone frequency, and they form “virtual” customer nodes in a reduced VRP. The RILS is a population-based optimization algorithm. During the evolution of algorithm, the backbone frequency is extracted from the population, and the algorithm attempts to transform the original problem into a set of smaller size problem with smaller neighborhood, thus improving the efficiency of the algorithm. Experimental results show that the RILS can obtain better solutions than FMNILS.3) A novel algorithm common grounding optimization(CGO) is presented. The key point of the proposed algorithm is the suitable assessment of the basic elements. Therefore, the basic element acceptability is defined in terms of both the fitness of individual and the acceptable degree of basic element, and it is used to select the better basic elements. The excellent individual is constituted by the better elements, so the individual acceptability is defined, and it is used to guide the searching direction. During the evolution of the CGO, the common basic elements of individual solutions are reserved; other basic elements are still passed to the next iterations and evolved in successive iterations. With the increase of common basic elements, all individual solutions will eventually be the same which happens to be the near-optimal solution for the problem. CGO has the advantage of fast convergence and high accuracy, and it is efficient for large-scale capacity vehicles routing problem(CVRP).4) The FMNILS proposed in 1) is modified and applied to the IMSs. Injection molding scheduling problem is modeled as a vehicle routing problem with time windows. By introducing the machine code and time windows overlap detection methods the feasibility fast assessment for the IMS neighborhood solutions is introduced. The modified algorithm for IMSs has strong practicability, and it can obtain a satisfaction solution of IMS in a short time.