Регистрация / Вход
Прислать материал

Tabu search heuristic for real-life vehicle routing problem

Name
Ivan
Surname
Grechikhin
Scientific organization
NRU HSE
Academic degree
Bachelor
Position
Student
Scientific discipline
Information technologies
Topic
Tabu search heuristic for real-life vehicle routing problem
Abstract
Vehicle Routing Problem is famous and popular problem in logistics and transportation, and the variety of such problems is explained by the fact that it occurs a lot in real-life situations. In this work, Site-Dependent Truck and Trailer Routing Problem with hard and soft Time Windows and Split Deliveries is considered (SDTTRPTWSD). Vehicle Routing Problem is NP-hard combinatorial optimization problem and finding an exact optimal solution is impossible. Tabu Search Heuristic is suggested as an algorithm for solving SDTTRPTWSD.
Keywords
Vehicle Routing Problem, Tabu, Heuristic
Summary

The considered mathematical model is the same as in the article of Batsyn M., Ponomarenko A. (2014): Heuristic for a Real-life Truck and
Trailer Routing Problem. However, the current work takes a different approach for program architecture is different. In this work, the program architecture for solving the Site-Dependent Truck and Trailer Routing Problem with hard and soft Time Windows and Split Deliveries (SDTTRPTWSD) problem is adapted for Heuristic with Tabu Search elements. Generally, it means that this architecture uses operations of deletion and insertion and both are evenly valued. Also, the algorithm employs greedy heuristic for initial solution; this greedy solution does not have a requriement to be obtained fast and to have a considerably good cost, because the heuristic with tabu elements is supposed to improve the initial solution significantly. 

The base of the new algorithm is in two different representations of the route in program. First representation is Route Points, which are logical pieces of any route - every Route Point is a point that is visited by vehicle in this route. Second representation is Actions - atomic events such as travel from one point to another or process of unload at some point. By using these representations and intercation between them, the algorithm achieves the simplification and unification of the problem.

As for results, tests on real data show that the new algorithm architecture is capable of receiving a satisfactory results. In comparison with old architecture greedy algorithm, which is described in Batsyn M., Ponomarenko A. (2014), the costs for different real data days are generally improved by 5%. This number is substantial as it allows to save some real money for companies with such real problems. Also, there is an actual possibility to change the program in order to consider another TTRP or VRP problem or problem, which can be represented similarly.