A Study on Robot and Drone Assisted Delivery Problems and Their Solutions

The surge in online retail, driven by population growth, technology, and the Covid-19 pandemic, emphasizes the need for efficient last-mile delivery. This thesis explores Robot and Drone-Assisted Delivery Problems, addressing the need for innovative solutions in the integration of trucks and delivery robots or drones. Recent technological advancements allow drones to be launched or collected from moving vehicles without human intervention, challenging the common notion of restricting these actions to when the truck is stationary. Chapter 3 of this thesis introduces the Covering Salesman Problem with Nodes and Segments Using Drones (CSPNS-D), a problem whose approach determines the maximum coverage area of nodes or links serviced by a drone as the truck traverses the corresponding node or link. Three Mixed Integer Linear Programming (MILP) models, representing various drone coverage areas, were proposed to minimize the truck's working span. Results demonstrate optimal solutions for up to 35 customers, with substantial savings compared to the Traveling Salesman Problem (TSP). Additionally, a computationally efficient link removal heuristic is presented for larger instances. Chapter 4 introduces the Robot-Assisted Delivery Problem (RADP), integrating trucks, robots, and local depots. Two consistent MILP models, RADP-1 and RADP-2, optimize delivery schedules, with RADP-1 proving more efficient due to a large number of feasible operations in RADP-2. RADP-1 considers each arc and node separately in the modelling process, whereas RADP-2 treats combinations of arcs and nodes as a single operation. Unlike the CSPNS-D models, RADP only allows launching and collection of robots when the truck is stationary. RADP models, like CSPNS-D, pose NP-hard challenges, necessitating heuristic approaches for larger problems. The proposed P-Heur and K-Heur heuristics prioritize operations based on the node-time ratio and employ a K-Means algorithm for cluster decomposition and MILP solution, respectively, effectively addressing larger-scale challenges.