A randomized variable neighborhood descent heuristic to solve the flying sidekick traveling salesman problem.
Nenhuma Miniatura disponível
Data
2018
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
Unmanned aerial vehicles (UAV), or drones, have the potential to reduce cost and
time in last mile deliveries. This paper presents the scenario which a drone works in
collaboration with a delivery truck to distribute parcels. This Traveling Salesman
Problem (TSP) variant has some particularities that make the originals constraints
insufficient. In more detail must be considered the flying time-limit of the drone
that inhibits them from visiting all customers and the parcel must not exceed the
payload of the drone. To solve the problem, the initial solution is created from the
optimal TSP solution obtained by the Concorde solver. Next, an implementation
of the Randomized Variable Neighborhood Descent (RVND) heuristic is used as
a local search to obtain the problem solution. To test the proposed heuristic, 11
instances based on the well-known TSP benchmark set were created. Computational
experiments show the use of drones for last mile delivery can reduce the total delivery
time up to almost 20%. Moreover providing a faster delivery this system has a
positive environmental impact as it reduces the truck travel distance.
Descrição
Palavras-chave
Unmanned aerial vehicle, Drone delivery, Last mile delivery
Citação
FREITAS, J. C. de; PENNA, P. H. V. A randomized variable neighborhood descent heuristic to solve the flying sidekick traveling salesman problem. Electronic notes in discrete mathematics, v. 66, p. 95-102, 2018. Disponível em: <https://www.sciencedirect.com/science/article/pii/S1571065318300593>. Acesso em: 16 jun. 2018.