• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Real-Life Vehicle Routing Problem

Student: Komosko Larisa

Supervisor: Mikhail Vladimirovich Batsyn

Faculty: Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod)

Educational Programme: Applied Mathematics and Information Science (Master)

Year of Graduation: 2016

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.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses