Synchronized Planning of Interdependent Resources in Transport Logistics

本课题的目标是在前期工作的基础上，对多同步约束车辆路径问题(VRPMS)的建模和精确启发式求解领域的研究做出贡献。运输请求包括将一定数量的货物递送到指定的客户(地点)。为此，提供了一套装载能力有限的车辆。VRPM与其他VRP的不同之处在于，可用于满足运输请求的资源(即车辆、驾驶员和集装箱)是相互依赖的，并且它们的使用必须在几个方面同步：除了需要决定应该由哪种资源(S)来执行哪种请求(S)之外，VRPM还具有关于时间、空间和空间的同步要求，并且它们的使用必须在几个方面同步VRPS已经被科学地研究了多年。这种持续的研究活动的一个原因是VRP带来的数学和信息挑战。另一个原因是车辆路径具有相当大的实际意义。然而，到目前为止，VRPMS在很大程度上被科学忽视了。这主要是因为单纯的请求满足同步并不会导致资源之间的相互依赖，而多个同步需求会导致复杂的相互依赖关系，这很难通过算法来处理。VRPM在食品配送、家庭护理人员调度以及零担业务、包裹递送服务和城市物流中的多式联运中都有应用。对于VRP的求解，一方面使用精确的离散优化方法，另一方面使用启发式和元启发式方法。后者不能保证找到最优解决方案，但它们被使用了，因为现实世界大小的问题实例仍然不能在合理的时间内一致地准确地解决。因此，计划项目的交付是：-针对一般VRPM的通用启发式的实施-针对一般VRPM的精确算法的实施-关于用于解决不同类型的VRPMS的解决程序的性能的理论、数学证明和经验、统计验证的陈述

Based on own previous work, the objective of the planned project is to contribute to research in the field of modelling and exact and heuristic solution of vehicle routing problems with multiple synchronization constraints (VRPMSs).In the basic problem of vehicle routing, a set of transport requests is given. A transport request consists in delivering a certain amount of a good to a specified customer (location). To this end, a set of vehicles with limited loading capacity is available. The problem is to determine a cost-minimal routing plan, that is, to group transport requests into clusters that can be performed by one vehicle each, and to set the sequence of the requests in each cluster, so that the overall travelled distance or the number of necessary vehicles is minimized.VRPMSs differ from other VRPs in that the resources available to fulfil the transport requests, that is, vehicles, drivers and containers, are interdependent, and that their use must be synchronized in several respects: Beside the requirement to decide which resource(s) should perform which request(s), VRPMSs possess synchronization requirements with regard to time, space, and load.VRPs have been scientifically studied for years. One reason for this continued research activity is the mathematical and informational challenge that VRPs pose. Another reason is the considerable practical relevance of vehicle routing. VRPMSs, however, have been largely neglected by science so far. This is mostly due to the fact that a mere synchronization of request fulfilment does not induce interdependencies between resources, whereas multiple synchronization requirements lead to intricate interdependencies that are not easy to handle algorithmically.Applications of VRPMSs can be found in food distribution, home care staff dispatching and multi-modal transport in the less-than-truckload business, parcel delivery services, and city logistics.For solving VRPs, on the one hand, exact methods of discrete optimization are used, on the other hand, heuristics and metaheuristics are applied. The latter do not guarantee finding optimal solutions, but they are used, because problem instances of real-world size can still not be consistently solved exactly in reasonable time. Therefore, the deliveries of the planned project are:- An implementation of a generic heuristic for general VRPMSs- An implementation of an exact algorithm for general VRPMSs- Theoretical, mathematically proven and empirical, statistically validated statements on the performance of the solution procedures for solving different types of VRPMSs