Research On Heuristic Algorithms And Their Applications In The Vehicle Routing Problem

There exists a kind of problems called NP-complete in the nature.For combinatorial explosion of solution space is met in the search for objective solutions to these problems,that solving the large scale NP-complete problems has been one of the bot-tleneck problems in the field of computer science and artificial intelligence.It is hard for classical optimization methods,like branch-and-bound and dynamic programming, to find the optimal solutions to such problems,so heuristic methods are usually employed, which can find nearly optimal solutions within quite rational time.Vehicle routing problem is a NP-complete problem.There are many cases in real life that can be abstracted as this problem,such as vehicle scheduling in logistics distribution,bus routing,mail or newspaper delivery,airline or railway timetabling,waste collection and school bus routing.Therefore,it makes sense to study heuristics for solving the vehicle routing problem from the aspect of both theory and practice.Several heuristics and their applications in some variants of the vehicle routing problem are studied in this thesis.Hybrid metaheuristics are proposed by combining the search strategies belonging to different metaheuristics and applied to the capacitated vehicle routing problem,the open vehicle routing problem,the fleet size and mixed vehicle routing problem and the vehicle routing problem with simultaneous delivery and pickup.The work of this dissertation is supported bv the National Basic Research Program(973 Program) of China under grant No.2006CB705500.The main contributions of this dissertation are described as follows.(1) As for the capacitated vehicle routing problem(CVRP),a hybrid iterated local search algorithm HILS is proposed,which combines the iterated local search and variable neighborhood descent.In the variable neighborhood descent procedure. multi-neighborhood operators are employed to diversify the search,while a restricted neighborhood is proposed based on the idea of granular neighborhood to reduce unnecessary search and increase the search efficiency.A perturbation strategy is designed based on the cross-exchange operator.The structure of the HILS is quite simple.It is easy to be implemented and flexible.Computational experiments are carried out on 34 benchmark problems to discuss the parameters setting and the effect of the main components on the performance of the HILS. The experimental results show that the proposed HILS can effectively solve the capacitated vehicle routing problem,and its performance is competitive with other state-of-the-art heuristic methods for the CVRP.(2) As for the open vehicle routing problem(OVRP),an extended version of the hybrid iterated local search algorithm eHILS is proposed.In the eHILS,solutions with less vehicles are preferred to be accepted during the variable neighborhood descent procedure,by which the demand of double level objectives of the OVRP can be satisfied.Computational results on 16 benchmark problems show that the HILS can obtain the best known solutions to 13 problems,and 3 of them are new.which demonstrates the effectiveness of the eHILS.(3) As for the fleet size and mixed vehicle routing problem(FSMVRP),a heuristic VNS_FSM is proposed based on variable neighborhood search.In the VNS_FSM, the neighborhood structures combination is designed to implement the shaking, and a new vehicle type adjustment method is presented.Computational experiments are carried out on benchmark problems to validate the effectiveness of the proposed VND_FSM.The correct solutions to problems G₀7 to G₁2 are given.Experimental results show that the proposed heuristic VNS_FSM can obtain the best known solutions to most benchmark problems.The VNS_FSM performs quite competitively or even better when compared with other state-of-the -art heuristics,which indicates that the proposed VNS_FSM is one of the best algorithms for the FSMVRP.(4) As for the vehicle routing problem with simultaneous delivery and pickup(VRPSDP), a hybrid ant colony optimization algorithm HACS is proposed which combines the ant colony optimization and variable neighborhood descent.Based on the analysis on the solution feasibility,a new constructive method for feasible solutions is proposed,i.e.,a weakly feasible solution is firstly built,which is then transferred to be a strongly feasible one.The advantage of this method is that it is not only very simple,but also can be effectively avoid using too many vehicles.An insertion-based constructive method is proposed to improve the original method of ant colony optimization for generating weekly solutions.Variable neighborhood descent is utilized to improve the best solution of the solution population, with the expect to speed the algorithm convergence.Experimental results on 55 benchmark problems show that the proposed HACS can obtain the best know solutions to 52 problem,44 of which are new.which indicates that the HACS is effective.Besides.when compared with three latest heuristics,the proposed HACS is quite competitive or even better,which indicates that the proposed HACS is one of the best algorithms for solving the VRPSDP.