The main goal of our work is to investigate speed-up techniques and implement them in the high-quality solution method for approximating the Traveling Salesman Problem (TSP) that arises numerous times when solving the Vehicle Routing Problem (VRP). In VRPs, partitioning customers in disjoint sets (i.e. routes) becomes especially problematic when the given constraints restrict not only the vehicle's capacity, but also the maximum travel distance permitted for a single vehicle, as is the case in the VeRoLog Challenge 2019. Due to this maximal traveled distance constraint, each time a set of customers in a single route is modified (e.g. by one inter-route operator), a new TSP for this route has to be solved in order to check if the the upper bound is exceeded.
In our approach, we used the logic of the Iterated Local Search (ILS) with adequate initialization methods and efficient implementation techniques. This techniques allowd us to exclude low-quality solutions before performing any further transformation and therefore contribute to the faster convergence towards the optimal solution. We mainly focused on enhancing the time efficiency of the well-known local search method 2-opt by calculating upper and lower bounds. Our experiments carried out on instances from the TSLIB show that more than 90% of the moves can be omitted by implementing our checks.
An independent assessment and comparison with other implementation methods was carried out on the optil.io platform, where we reached the top of the optil.io ranking in the ongoing TSP challenge.