Adaptive Large Neighborhood Search

Abstract

There has already been a lot of research on Local Search Heuristics in Computer Science. Local Search improves an initial solution by manipulating rather small parts of the solution. Large Neighborhood Search (LNS) has a similar approach, but instead of marginal changes, huge parts of the solutions are changed. This is done by the combination of so-called destroy and repair methods. LNS is especially useful for problems with a tightly constrained search space, such as the Rich Pickup and Delivery Problem with Time Windows (RPDPTW). The RPDPTW is a logistic problem, in which a number of pickup and delivery requests have to be served by a fleet of vehicles. Furthermore, certain time, capacity and feasibility constraints have to be met. Adaptive Large Neighborhood Search (ALNS) is an extension of Large Neighborhood Search, that does not commit to one destroy and repair heuristic. Instead, it chooses in every iteration from a pool of heuristics based on past success. Even though it is a general heuristic, ALNS can compete with most specialized heuristics. Therefore, the goal of this thesis is a detailed description of the ALNS heuristic. A closer look at an application of ALNS is provided by the adaption to the Rich Pickup and Delivery Problem with Time Windows. The ALNS heuristic has also been implemented, extended, tuned and tested for different problem instances. The test results confirm the promising results obtained by other papers.