A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem

摘要

This article focuses on the mechanism of evaluating solution neighborhoods, an algorithmic aspect which plays a crucial role on the efficiency of local-search based approaches. In specific, it presents a strategy for reducing the computational complexity required for applying local search to tackle various combinatorial optimization problems. The value of this contribution is two-fold. It helps practitioners design efficient local search implementations, and it facilitates the application of robust commercial local search-based algorithms to practical instances of very large size. The central rationale underlying the proposed complexity reduction strategy is straightforward: when a local search operator is applied to a given solution, only a limited part of this solution is modified. Thus, to exhaustively examine the neighborhood of the new solution, only the tentative moves that refer to the modified solution part have to be evaluated. To reduce the complexity of neighborhood evaluation, the static move descriptor (SMD) data structures are introduced, which encode local search moves in a systematic and solution independent manner. The proposed strategy is applied to the vehicle routing problem (VRP) which is of high importance both from the practical and theoretical viewpoints. The use of the SMD concept, for encoding three commonly applied quadratic local search operators, results into a VRP local search method which exhibits an almost linearithmic complexity in respect to the instance size. Furthermore, exploiting the SMD representation of tentative moves, a metaheuristic strategy is proposed, which is aimed at diversifying the conducted search via a simple penalization policy. The proposed metaheuristic was tested on various large and very large scale VRP benchmark instances. It produced fine results, and managed to improve several best known solutions. The method was also executed on real-world instances of 3000 customers, the data of which reflects the actual geographic distribution of customers within four major cities.