Stochastic models for analysis and optimization of unmanned aerial vehicle delivery on last-mile logistics

Abstract

Land transportation is generally considered one of the most expensive, polluting and least efficient parts of the logistics chain. Due to these issues, using unmanned aerial vehicles such as drones for package delivery in last-mile logistics becomes increasingly attractive. However, there are several significant obstacles in terms of technical aspects and performance capabilities of drones like limited flight coverage. In addition, supply chains are exposed to a broad range of uncertainties some of which may cause disruptions in the whole supply chain system. To hedge against these issues, a well-designed reliable network is a top priority. Most existing models for optimization within logistics chain are deterministic, lack reliability, or they are not computationally efficient for larger problems. This dissertation aims to improve the reliability and efficiency of the supply chain network through the development of stochastic optimization models and methods to help address important problems related to delivery of products using drones. To achieve this goal, this study has developed a generalized optimization model that captures the dynamic and stochastic nature of problems by using stochastic optimization and stochastic control. At first, this study addresses issues bordering on capacitated supply chain problems, specifically on how reliable supply chain networks can be designed in the face of random facility disruptions and uncertain demand. The proposed multi-period capacitated facility location and allocation problem is modeled as a two-stage stochastic mixed-integer formulation that minimizes the total establishing and transportation cost. To overcome the complexity of the model, the L-shaped method of stochastic linear programming is applied by integrating two types of optimality and feasibility cuts for solving the stochastic model. This research improves the proposed algorithm in two ways: replacing the single-cut approach with a multi-cut and showing relatively complete recourse in the stochastic model by reformulating the original model. According to computational results, the proposed solution algorithm solves large-scale problems while avoiding long run times as well. It is also demonstrated that substantial improvements in reliability of the system can often be possible with minimal increases in facility cost. Next, this research aims to construct a feasible delivery network consisting of warehouses and recharging stations through the development of a stochastic mixed-integer model, resulting in improving the coverage and reliability of the supply chain network. Due to the computational complexity of the scenario-based mixed-integer model, this research improves the performance of the genetic algorithm by considering each scenario independently in one of the steps of the algorithm to significantly improve the computational time need to find the solutions. Computational results demonstrate that the proposed algorithm is efficiently capable of solving large-scale problems. Finally, this dissertation analyzes tradeoffs related to charging strategies for recharging stations which can be viewed as warehouses in last-mile logistics with capacity constraints and stochastic lead times. To enhance delivery time, this research assumes that extra batteries are available at the recharging station where individual drones land when they run out of power and swap empty batteries with fully charged ones. Stochastic Markov decision models are formulated to handle stochasticity in the problem and determine the optimal policy for decision-makers by applying a policy iteration algorithm. To overcome of computational challenges, a novel approximation method called the decomposition-based approach is proposed to split the original Markov decision problem for the system with N states into N independent Markov chain processes. Through numerical studies, this dissertation demonstrates that the proposed solution algorithm is not only capable of solving large-scale problems, but also avoids long run times. It is also demonstrated how different stochastic rate like flight or demand, and inventory and backorder costs can affect the optimal decisions.