ENS.VRSP: Efficient Neighborhood Search in Vehicle Routing and Scheduling

• Applicants: Professor Dr. Stefan Irnich; Professor Dr. Michael Schneider
• Subject Area: Accounting and Finance
• Term: from 2016 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 315139873

The intended project aims at generating new insights and developing new methods in the field of neighborhood search for vehicle-routingand scheduling problems (VRSP). VRSP can be described in a generic fashion as follows: Given a set of transportation requests and a fleet of vehicles, the task is to find a set of vehicle routes that fulfill all (or a selection) of the transportation requests with the given fleet at minimum cost. In particular, we have to decide which vehicle performs which requests in which order such that the resulting vehicle routes are feasible. It is strongly assumed that VRSP cannot be solved to optimality in a time that depends polynomially on the input size of the problem instance, i.e., they are NP-hard. Therefore, VRSP are frequently addressed by heuristic algorithms, which are distinguished into construction and improvement methods. Among the improvement methods, neighborhood searches play a major role: These methods iteratively and systematically modify a given solution in order to reach a better solution. Well-known examples of neighborhood searches are the 2-opt and the Lin-Kernighan method for solving the Traveling Salesman Problem. We believe that, despite the numerous publications on metaheuristics for VRSP, there is a strong need for additional research on the development and analysis of the basic components of neighborhood search. These basic components address fundamental aspects of neighborhood search, in particular, efficiently checking the feasibility and calculating the cost of the solutions modified by search moves as well as determining an appropriate order of search steps. To improve these components, we plan to combine concepts from the field of exact optimization (resources, resource extension functions) with modern approaches from the field of heuristics (granular search, time travel). This renders a cooperation between the proposers beneficial as their competence perfectly complements each other with regard to the intended research. The basic components are not restricted to specific methods or specific VRSP but are widely applicable. The intended insights are therefore strongly relevant: They allow for significant performance improvements of numerous different solution methods for a large number of practically and scientifically relevant problems.

• DFG Programme: Research Grants