考量途中起降之卡車與無人機混合配送模式最佳化

Optimization of Trucks and Drones in Tandem Delivery Network Considering En Route Operations

張安妮(An-Ni Chang)

指導教授 ： 朱致遠

國立臺灣大學/工學院/土木工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202201707

摘要

在電商快速發展下，物流需求大幅提升，物流業者希望在增加包裹配送效率的 同時也能夠降低配送成本，因此逐步興起使用卡車搭配無人機同時進行配送之新 型態配送模式，無人機於飛行時較不會排放廢氣，且不受地面交通及地形限制，用 於物流有助於提高配送效率，然而無人機卻有續航力不足的問題，因此將其搭載於 卡車上，讓無人機於卡車上提取包裹以進行配送，配送完成後亦回到卡車降落進行 下一次配送準備，透過兩者之搭配拓展無人機的服務範圍。
過往已有許多相關文獻研究卡車搭配無人機混合配送模式，然而大多數文獻 將無人機起飛及降落位置限制於節點，即僅能於倉庫或卡車服務之顧客位置才能 夠進行無人機起降操作，無法發揮卡車搭配無人機混合配送模式之最大效益。
基於以上原因，本研究放寬無人機僅能於節點起降之限制，使無人機可於卡車 行駛之路線途中起降，增加無人機使用上的彈性與效率，進而達到縮短總配送完成 時間之目的。本研究透過建立數學規劃模型求解問題，目標為最小化總配送時間， 由於數學模型在大規模問題下求解能力有限，因此發展以數學模型為基礎之啟發 式演算法加快求解速度。
本研究利用不同規模大小之案例進行測試，展現演算法之求解品質與效率。演 算法於小規模問題能夠得到與最佳解相近的解，且在較大規模之問題中透過其求 解速度快之優勢，在短時間內求得較數學模型更佳的可行解。此外，將本研究之模 式與一般限制無人機僅能於節點起降之模式比較，發現在無人機續航力有限的情 況下，考量途中起降有助於節省總配送時間並增加無人機使用率，而在無人機相對 速度較快時，節省總配送時間之效益將更加顯著。

關鍵字

車輛途程問題 ； 無人機 ； 途中起降 ； 數學規劃 ； 啟發式演算法

並列摘要

With the rapid development of e-commerce, the demand for logistics has increased significantly. Logistics operators hope to increase distribution efficiency and reduce distribution costs. Accordingly, a new type of distribution mode that uses trucks and drones for simultaneous distribution is gradually emerging. Drones emit less exhaust gas when flying and are not restricted by traffic and terrain. The use of drones in logistics can help improve distribution efficiency. However, the limited endurance of drones is a problem, which limits the service range of drones. Therefore, put the drone on the truck and let the drone pick up the package on the truck for delivery. After the delivery is completed, it will return to the truck to land for the next delivery preparation. Through the combination of trucks and drones, it can make up for the lack of drone endurance.
In the past, there have been many related literatures on the hybrid distribution mode of truck ride-on drones. However, most literature assumes that drones can only be launched and recovered at nodes, i.e. only at warehouses or customer locations served by trucks. This assumption cannot maximize the benefits of the hybrid delivery model of trucks and drones.
Hence, in this study, this assumption is relaxed so that the drone can be launched and recovered on the route of the truck, which is called en route operation. In this way, the flexibility and efficiency of the use of drones can be increased, thereby achieving the purpose of shortening the total delivery time. A mathematical programming model is built to solve this problem, and the goal is to minimize the total delivery time. In addition, due to the limited performance of mathematical models in solving large-scale problems, this study develops a mathematical model-based heuristic algorithm to speed up the solution.
Case studies demonstrate the solution quality and efficiency of the algorithm with cases of different scales. Algorithms can obtain solutions similar to mathematical models for small-scale problems. For larger-scale problems, due to the fast solution speed of the algorithm, a better feasible solution than the mathematical model can be obtained in a short time. Moreover, the model of this study is compared with the model that generally restricts the launch and recovery of drones only at nodes. It was found that when the drone has endurance limitations, en-route operations can help save total delivery time and increase drone usage. Furthermore, the savings in total delivery time are even more pronounced when drones are faster than trucks.

並列關鍵字

Vehicle Routing Problem ； Drone ； En Route ； Mathematical Programming ； Heuristic Algorithm

參考文獻

[1] Agatz, N., Bouman, P., Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4), 965-981.

[2] Ghilas, V., Demir, E., Van Woensel, T. (2016). The pickup and delivery problem with time windows and scheduled lines. INFOR: Information Systems and Operational Research, 54(2), 147-167.

[3] Ha, Q. M., Deville, Y., Pham, Q. D., Hà, M. H. (2018). On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 86, 597-621.

[4] Marinelli, M., Caggiani, L., Ottomanelli, M., Dell’Orco, M. (2018). En route truck drone parcel delivery for optimal vehicle routing strategies. IET Intelligent Transport Systems, 12 (4), 253– 261.

[5] Murray, C. C., Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109.