EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3453. The Vehicle Routing Problem with Drones and Outsourcing

Invited abstract in session MD-52: Scheduling and Routing Problems , stream Combinatorial Optimization.

Monday, 14:30-16:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Xuan Ren
School of Management, Northwestern Polytechnical University
2. Ola Jabali
Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano
3. Roberto Roberti
Information Engineering, University of Padova
4. Gongqian Liang
Northwestern Polytechnical University

Abstract

Recent scientific literature has shown that combining drones with trucks is effective for last-mile delivery. With the growing volumes of next-day delivery, not all customers may be served within a given day, especially when considering a limitation of the drivers’ working time. To this end, we investigate the vehicle routing problem with drones and outsourcing (VRPDO), where customers are served either by a given truck-drone fleet (each truck equipped with a single drone) or by outsourcing, with each customer incurring an individual fixed cost. The objective is to minimize the transportation costs of trucks and drones as well as the outsourcing costs. We propose a variable neighborhood search (VNS) algorithm for this problem, where we represent a VRPDO solution as customer sequences. Each sequence is evaluated by solving a problem that we refer to as the fixed sequence assignment problem (FRAP). Given a customer sequence, the FRAP assigns each customer to the truck, or the drone, or be outsourced, and determines truck and drone routes, in order to minimize total costs while satisfying a maximum-duration limit. We treat the FRAP as a resource-constrained shortest path problem and introduce an exact labeling algorithm to solve it. We further develop a heuristic labeling algorithm (HLA) for the problem and reinforce the VNS by presenting filtering strategies based on the HLA. Computational results show the effectiveness of our proposed approach in terms of solution quality.

Keywords

Status: accepted

Back to the list of papers