Stochastic optimisation of unmanned aerial vehicle assisted package delivery planning

• Main Author: Sawadsitang, Suttinee
• Other Authors: Dusit Niyato
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/146991
• Institution: Nanyang Technological University

The need for automated delivery services has never been greater. As the COVID-19 pandemic grips the world, manufacturers and retailers are faced with challenges to continue their businesses with social distancing in place. E-commerce, which has already been experiencing unprecedented growth, is now being adopted even more widely. Given an increase demand in delivery services and the need for social distancing measures, drone delivery becomes an attractive option. Unmanned aerial vehicle or drone delivery involves much less human interaction, incurs a much lower cost, offers a faster delivery, and is more eco-friendly than truck delivery. These advantages have led many big shippers such as UPS, Amazon, Japan Post, SingPost Alibaba, and JD.com to set their eyes on incorporating this novel delivery method to their businesses. One of the greatest challenges in a race to achieve drone delivery is how to manage the high probability of service interruptions to ensure punctual and reliable delivery. Beside technical issues, drone delivery services may be disrupted and fail due to a wide range of factors such as strong wind, rain, human abuse, and animal attacks. These unpredicted factors introduce uncertainties, which have not been considered in existing research on planning of drone delivery services. The first shipper to consider these uncertainties and derive an effective and efficient delivery plan to address them can gain significant competitive advantages and lead the transformation of delivery logistics services. In this thesis, I introduce (i) the joint ground and aerial delivery service optimisation and planning (GADOP) framework, (ii) multi-objective optimisation for drone delivery (MODD) framework, and (iii) Bayesian Shipper Cooperation in Stochastic Drone Delivery (BCoSDD) framework, which all of them explicitly incorporate uncertainty of drone package delivery, i.e., take-off and breakdown conditions. Firstly, the GADOP framework aims to minimise the total delivery cost given practical constraints, e.g., traveling distance limit. Specifically, I formulate the GADOP framework as a three-stage stochastic integer programming model. To deal with the high complexity issue of the problem, a decomposition method is adopted. To extend the study in stochastic drone delivery, I propose the MODD framework as a joint aerial delivery and outsourcing delivery as a three-objective optimisation. I apply the E-constraint method to handle the multi-objective optimisation in the MODDframework. I also consider a scenario in which multiple shippers can cooperate to minimise their drone delivery cost. The BCoSDD framework is composed of three functions, i.e., package assignment, shipper cooperation formation and cost management. The uncertainties of misbehaviour of cooperative shippers are also taken into account by dynamic Bayesian coalition formation game. The performance of the frameworks is evaluated using two data sets including Solomon benchmark suite and the real data from a Singapore logistics company. The tradeoffs among drone delivery, conventional ground-based delivery, and outsourcing carrier are presented for all proposed frameworks. Simulation results have shown that the GADOP framework always achieves a lower total payment than that of the expected value formulation (EVF) and the Parallel Drone Scheduling Traveling Salesman Problem (PDSTSP). The computational time gaps between the decomposed GADOP and the original GADOP are grown exponentially when the numbers of drones and uncertainty scenarios increase. Our experiments show that the decomposed GADOP solve about a hundred times faster than the original GADOPwhenthenumbersofdronesandscenarios are larger than 6 and 64, respectively. For the BCoSDD framework, the experiment results show that it can achieve the most effective solution, i.e., the lowest delivery cost, compared with other baseline approaches, i.e., deterministic drone delivery (DDD), stochastic drone delivery (SDD), shipper cooperation in deterministic drone delivery (CoDDD), and shipper cooperation in stochastic drone delivery (CoSDD). To sum up, the studies can help single/multiple shipper(s) plan the drone delivery more effectively.