RoutingSolver is based on
three simple principles:
Do many small changes
with problem knowledge
Small changes. Given a certain solution, RoutingSolver tries to find small modifications that yield an improvement. In the world of heuristics, this technique is also called local search. Local search has proven to be the cornerstone of many solutions techniques for various combinatorial optimisation problems, and its success is widely acknowledged. For instance, it could try to exchange the route position of two customers (a swap), or remove a customer from one route and insert it into another (a relocation). Such modifications are also called moves. RoutingSolver uses three generic moves to find improvements.
Efficiency. Improving changes need to be found under thousands or millions of possible options. RoutingSolver attempts to investigate as many promising changes as possible in minimal time to optimise performance. Unpromising moves are filtered out by pruning and sequential search. Through pruning, only moves are considered which connect close nodes, while sequential search deconstructs moves into small parts to speed up the evaluation. Paired with an efficient implementation, these techniques allow to evaluate up to 10 million moves per second.
Problem knowledge. After many changes we will eventually find a solution, for which no more improving moves can be found (a local optimum). In this situation RoutingSolver tries to remove 'bad' edges between customers. We found in an experimental study that bad edges are costly and make routes 'wide'. After a certain number of bad edges have been removed, the local search can continue.