A Competitive Heuristic Algorithm for Vehicle Routing Problems with Drones
Ola Jabali, professor at the Politecnico di Milano
Via Zoom click here
Abstract:
We propose a heuristic algorithm capable of handling eight possible versions of the vehicle routing problems with drones (VRPD). These are characterized according to three axes, 1) single or multiple trucks each equipped with a single drone, 2) allowing the drone to land and wait or not, and 3) minimizing the transportation cost or minimizing the makespan. One of our main algorithmic contributions relates to a subproblem of the VRPD, which we refer to as the fixed route drone dispatch problem (FRDDP). Given a sequence of customers being visited by a truck, the FRDDP determines a subset of customers to be visited by the drone. Solving the FRDDP exactly with dynamic programming entails a computational complexity of O(n3), where n is the number of customers contained in the route. Considering that the FRDDP is very frequently solved in local search algorithms, we introduce a heuristic dynamic program (HDP) with a computational complexity of O(n2), for each of the two FRDDP objectives. We embed HDPs in a hybrid variable neighborhood search algorithm, which we reinforce by developing filtering strategies based on the HDP. We compare via seven benchmarks the performance of our algorithm on four versions of the VRPD that have been studied in the literature. Considering the VRPD with minimizing the transportation cost, our method identifies new best-known solutions for 42 of 112 instances. For the VRPD with minimizing the makespan, our method computes 607 out of 644 optimal solutions and identifies 119 new best-known solutions among the 798 instances.
Bio:
Ola Jabali is an associate professor at the operations research and discrete optimization group of DEIB (Dipartimento di Elettronica, Informazione e Bioingegneria) at the Politecnico di Milano. She is also an affiliated professor at HEC Montréal, Canada, and a collaborating member of the Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT). She obtained her BSc. and MSc. in industrial engineering from the Technion, Israeli Institute of Technology in 2003 and 2006, respectively. She received her Ph.D. in industrial engineering in 2010 from the Eindhoven university of technology. In 2011 she was a post-doctoral fellow at Polytechnique Montréal. From 2012 till 2016 she was an assistant professor at the Department of Logistics and Operations Management at HEC Montréal. Her research interests deal with modelling realistic problems arising in transportation, production and logistics. She mainly focuses on optimizing transportation problem, in particular problems related to pollution, electric vehicles, uncertainty, fleet composition and customer service.
