Tabu search heuristic for real-life vehicle routing problem
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.