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

该计划旨在为车辆路线和调度问题（VRSP）的邻域搜索领域提供新的见解和开发新的方法。VRSP可以用一般的方式描述如下：给定一组运输请求和一个车队，任务是用给定的车队以最小的成本找到一组满足所有（或选择）运输请求的车辆路线。特别是，我们必须决定哪辆车以哪种顺序执行哪些请求，从而使最终的车辆路线是可行的。强烈假设VRSP不能在多项式依赖于问题实例的输入大小的时间内求解到最优，即它们是np困难的。因此，通常采用启发式算法来解决VRSP问题，启发式算法分为构建和改进两种方法。在这些改进方法中，邻域搜索起着重要的作用，这些方法迭代地、系统地修改给定的解，以达到更好的解。众所周知的邻域搜索的例子是解决旅行商问题的2-opt和Lin-Kernighan方法。我们认为，尽管有许多关于VRSP的元启发式的出版物，但仍需要对邻域搜索的基本组成部分进行进一步的研究和分析。这些基本组件解决了邻域搜索的基本问题，特别是有效地检查通过搜索移动修改的解的可行性和计算代价，以及确定适当的搜索步骤顺序。为了改进这些组件，我们计划将精确优化领域的概念（资源、资源扩展函数）与启发式领域的现代方法（粒度搜索、时间旅行）结合起来。这使得提议者之间的合作是有益的，因为他们的能力在预期的研究方面完全互补。基本组件不局限于特定的方法或特定的VRSP，而是广泛适用。因此，预期的见解具有很强的相关性：它们允许对大量实际和科学相关问题的许多不同解决方案方法进行显著的性能改进。

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.