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.