A variable neighborhood search for flying sidekick traveling salesman problem

• Date: 01 January 2020
• Published date: 01 January 2020
• Author: Puca Huachi Vaz Penna,Júlia Cária Freitas
• DOI: http://doi.org/10.1111/itor.12671

Intl. Trans. in Op. Res. 27 (2020) 267–290

DOI: 10.1111/itor.12671

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A variable neighborhood search for flying sidekick traveling

salesman problem

J´

ulia C´

aria de Freitas and Puca Huachi Vaz Penna

Departamento de Computac¸˜

ao, Universidade Federalde Ouro Preto, Campus Morro do Cruzeiro,

s/n, Ouro Preto-MG, 35400-000, Brazil

E-mail: juliacaria@decom.ufop.br [Freitas]; puca@ufop.edu.br [Penna]

Received 12 February2018; received in revised form 29 March 2019; accepted 29 March 2019

Abstract

The efficiency and dynamism of unmanned aerial vehicles, or drones, have presented substantial application

opportunities in several industries in the last years. Notably, logistic companies have given close attention

to these vehicles to reduce delivery time and operational cost. A variant of the traveling salesman problem

(TSP), called the flying sidekick traveling salesman problem, was introduced involving drone-assisted parcel

delivery. The drone launches from the truck, proceeds to deliver parcels to a customer, and then is recovered

by the truck at a third location. While the drone travels through a trip, the truck delivers parcels to other

customers as long as the drone has enough battery to hoverwaiting for the truck. This work proposes a hybrid

heuristic where the initial solution is created from the optimal TSP solution reached by a TSP solver. Next,

an implementation of the general variable neighborhood search is employed to obtain the delivery routes of

truck and drone. Computational experiments show the potential of the algorithm to improve significantly

delivery time. Furthermore, we provide a new set of instances based on the well-known traveling salesman

problem library instances.

Keywords: unmanned aerial vehicle; traveling salesman problem; drone delivery; last mile delivery; randomized variable

neighborhood descent

1. Introduction

According to the 2017 Global Online Consumer Report (Epstein, 2009) for 43% of the customers,

one of the most important characteristics when deciding where to buy is the enhanced delivery op-

tions. This is because the millenniums—people born between1980 and 2000—have a higher demand

for instant satisfaction than earlier generations. Even though they are increasingly comfortablebuy-

ing products online, they are more likely to visit shops to get the product right away, rather than

await delivery. Companies need to continually create ingenious ways to shorten delivery times and

therefore satisfy the needs of customers. One of the most innovative announcements envisioning

the improvement of delivery process occurred in December 2013 by Amazon’s CEO, Jeff Bezos,

who declared that one of the biggest e-commerce companies was testing drone parcel delivery. The

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

268 J. C. de Freitasand P. H. VazPenna / Intl. Trans. in Op. Res. 27 (2020) 267–290

Tabl e 1

Complementary features of truck and drone

Speed Weight Capacity Range

Drone High Light One Short

Truck Low Heavy Many Long

project involves a drone (generically known as unmanned aerial vehicles—UAV) that departs from

a warehouse loaded with a parcel, travels to the customer’s location where it drops the container,

and then returns to the warehouse. This operation demands no human intervention or guidance.

Since Amazon’s announcement, many companies started their drone delivery projects. Google calls

Project Wing the research team responsible for developing technologies to make this drone delivery

possible. Also in 2013, DHL launched a projectcalled Parcelcopter that accomplished over 100 suc-

cessful deliveries in 2016, including deliveries to remote villages within 30 minutes, which is faster

than transporting them across steep terrains in a car (Burgess, 2016). Another successful company

is JD.com, China’s second largest e-commerce, which is developing a drone capable of delivering

packages weighing as much as 1 metric ton throughout rural areas of the country flying 100 km

before recharging(Meredith and Kharpal, 2017). The automobile company Mercedes-Benz teamed

up with the drone logistic company Matternet to start a project based on a van drone delivery

concept. The project is a combination of work between van and drone in which the drone reads the

destination information using a QR code on the package; then it proceeds to deliver the goods with

a speed of up to 70 km/h and a range of 20 km (Etherington, 2017).

Even though drones are fast, their payload capacity is minimal, and limited endurance, that is,

the time it can stay floating on a full batterycharge, restricts their usage. The scenario wherea drone

delivers directly to each customer is not efficient, since after each visit the vehicle has to return to

the depot. On the other hand, trucks are heavy and slow, but they can carry many parcels. Table 1,

taken from Agatz et al. (2018a), summarizes truck and drone characteristics. The complementary

features of each vehicle are indicated in bold.

The high speed of the drone and the large capacity of the truck are complementary features

that can make the delivery process more efficient and, possibly, less expensive. A potential way to

take advantage of these attributes is by combining a drone and a truck to attend to all customers.

Hereafter is a brief description of the delivery model assumed in this work, which was introduced

by Murray and Chu (2015), known as the flying sidekick traveling salesman problem (FSTSP). In

this problem, the drone is launched from the truck, then proceeds to deliver goods to a customer,

and finally joins back the truck at the third location before the endurance of the drone is exhausted.

While the drone serves a customer, the truck can travel to deliver parcels to other customers. The

truck has to recover the drone at the third location before finishing the endurance of the drone.

The contributions of this work consist of combining the best features of each vehicle to build

a good truck and drone delivery route to parcel delivery. The proposed heuristic addresses the

traveling salesman problem (TSP) with drones proposed by Murray and Chu (2015) and Agatz

et al. (2018a). We propose a variable neighborhood search (VNS) based heuristic called hybrid

general variable neighborhood search (HGVNS) to tackle the TSP with drones problem. Although

VNS can be considered a simple algorithm to implement, it has demonstrated to be an efficient

metaheuristic by improving results in many fields. Several variants of VNS have been derived and

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies