考虑区域限制的卡车搭载无人机车辆路径问题研究

Research on Vehicle Routing Problem with Truck and Drone Considering Regional Restriction

无人机参与配送是解决末端物流难题的重要途径之一。卡车搭载无人机协同配送模式,克服了无人机载重量小、续航时间短的弊端,成为无人机参与末端物流配送的重要形式之一。在疫区、灾区进行应急配送时,经常遇到由于道路毁坏或封锁、区域污染,导致部分路段车辆或无人机无法通行的情况。在非应急配送中,也可能存在车辆限行和空域禁飞等区域限制措施。区域限制给卡车搭载无人机物流配送路径优化问题带来了很大挑战。论文构建了区域限制条件下卡车搭载无人机车辆路径问题的混合整数线性规划模型,提出了一种结合最短路算法和禁忌搜索算法的混合算法,基于标准算例库设计测试集并进行测试实验,实验结果表明混合算法具有较好的计算性能。

As the new force of modern transportation system, drone has many irreplaceable advantages, such as its high efficiency and flexibility, easy control, low energy consumption, and no occupation of road resources. But it is also restricted by many factors, such as the flight distance, complex flight environment and the law and policy barriers, which leads to the failure of drone to carry out the large-scale logistics distribution tasks. Therefore, the logistics operation mode of collaborating with truck has become the inevitable choice for the large-scale application of drone in terminal logistics distribution, emergency items distribution, military air transportation and other fields. This new logistics operation mode brings great challenges to the theory and practice of vehicle routing problem. In recent three years, scholars begin to pay more attention to this issue.VRP-TDR(Vehicle Routing Problem with Truck and Drone Considering Regional Restriction) is a new optimization problem, which not only needs to solve the problem of routing decision of drone and vehicles, but the synchronization problem in the separation and convergence operation of drone and vehicles. In this paper, the routing optimization problem of the collaborative distribution between drone and vehicles is extended from the traveling salesman problem(TSP) to the vehicle routing problem. At the same time, the situation of regional restriction is considered, and a complete linear mixed integer programming model is formed. The Tabu Search with Short-path(the SPTS) algorithm is designed to solve VRP-TDR model. The main idea is to use tabu search algorithm to optimize the truck route and the shortest path algorithm to optimize the corresponding drone route. The SPTS stimulates human brain’s short-term memory function to gradually seek the optimal solution in the overall situation. In order to avoid invalid cycle calculation, tabu criteria are added. At the same time, the amnesty criteria are designed to receive poor solutions, which ensures the search of effective routings in different ranges.At present, there is no standard data test for VRP-TDR, and the previous studies only give the demonstration example of VRP-TDR. So, based on the data base of VRP calculation examples, this paper builds the VRP-TDR test set by adding the information related to drone, and calculates SPTS algorithm’s calculation performance and speed to the test set, which can provide a reliable heuristic algorithm to solve this kind of problems. The effectiveness of SPTS algorithm is tested through extensive computational experiments. A good foundation is provided for the further research. For example, according to the characteristics of different logistics systems, less constraints of the model can be included, or the objective function of the model can be changed to form an extended VRP-TDR model.