Year of Graduation
Real-Life Vehicle Routing Problem
Applied Mathematics and Information Science
The purpose of the work consisted in the development of an effective heuristic for the solution of Real-life vehicle routing problem. Having investigated the literature concerning this problem, the conclusion has been drawn that one of the most popular statement of this problem is the vehicle routing problem with capacity constraints, time windows and heterogeneous fleet of vehicles. Articles about this concrete subject haven't been found in the Russian and foreign magazines therefore such statement of the problem seemed actual. In this regard, creation of the algorithm that can in reasonable time find a near optimal solution of the vehicle routing problem with hard and soft time windows and heterogeneous fleet of vehicles became the result of the work. On the different stages of the algorithm development intermediary results were compared with the best known published ones. Experiments have shown that the developed local search for the vehicle routing problem with hard and soft time windows shows on average of 1-2% deviation from the published solutions. The performance results of the developed algorithm version for the vehicle routing problem with hard time windows and heterogeneous fleet of vehicles differ on average by 6% from best published. The quality of the developed algorithm for the solution of the vehicle routing problem with hard time windows and heterogeneous fleet of vehicles was checked on 672 instances generated on the basis of Solomon instances. It has turned out that the accuracy of results depends on the size of soft windows – the more the window, the better the solution.