test
Search publications, data, projects and authors

Thesis

English

ID: <

10670/1.i7amm8

>

Where these data come from
Optimization of urban deliveries with drones and vehicles in parallel

Abstract

The growth of last-mile delivery and demand for next- and same-day service is pushing logistics beyond traditional transportation management and supply chain analytics. One recent evolution in urban logistics involves the usage of unmanned aerial vehicle (UAV) or drones in the delivery process. Delivery by drones offers new possibilities, but also induces new challenging routing problems. Proposals for drone delivery vary widely, with drones being used independently or in conjunction with delivery by trucks. In this thesis we address a truck-drone delivery scenario in wich one or several drones work in collaboration with one or several traditional delivery trucks to distribute parcels to customers from a depot. Truck(s) and drone(s) serve different sets of customers in parallel. A truck serves customers with a single tour starting from the depot, visiting a subset of customers and returning back to the depot, while a drone delivery involves a single stop with the drone departing from and returning to the depot (a drone travels back and forth between the depot and the customer locations). The objective is to minimize the completion time i.e., the time at which all the trucks and drones are back to the depot, with the service of all customers carried out. This problem is called Parallel Drone Scheduling Traveling Salesman Problem (PDSTSP) when a single truck is available for delivery. When there are several trucks the problem is coined Parallel Drone Scheduling Multiple Traveling Salesman Problem (PDSMTSP). We propose an iterative two-step heuristic for the PDSTSP. A coding step transforms a solution into a customer sequence, and a decoding step decomposes the customer sequence into a tour for the vehicle and a subset of customers assigned to drones. Decoding is expressed as a bicriteria shortest path problem and is carried out by dynamic programming. Experiments conducted on benchmark instances from the literature (which are instances of 10 and 20 customers) and new larger instances generated from the TSPLIB3 confirm the efficiency of the approach and the results permit a clear improvement over the existing literature. To solve the PDSMTSP which extends the PDSTSP by considering several vehicles, we propose a hybrid metaheuristic combining Iterated Local Search and Dynamic Programming. This heuristic is inspired from the iterative two-step heuristic developed for the same problem restricted to a single vehicle. 20 instances of sizes varying from 50 customers to 199 customers are selected from the CVRPLIB for experiments. Computational experiments comparing several variants of the hybrid metaheuristic give some insights on this drone delivery system. Mixed Integer Linear Programming (MILP) formulations for both problems are also provided and straightforward Branch-and-Cut algorithms are developped.

Your Feedback

Please give us your feedback and help us make GoTriple better.
Fill in our satisfaction questionnaire and tell us what you like about GoTriple!