An iterative two‐step heuristic for the parallel drone scheduling traveling salesman problem

A recent evolution in urban logistics involves the usage of drones. In this article, we address a heuristic solution of the parallel drone scheduling traveling salesman problem, recently introduced by Murray and Chu. In this problem, deliveries are split between a vehicle and drones. The vehicle per...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2018-12, Vol.72 (4), p.459-474
Main Authors: Mbiadou Saleu, Raïssa G., Deroussi, Laurent, Feillet, Dominique, Grangeon, Nathalie, Quilliot, Alain
Format: Article
Language:English
Subjects:
city logistics
Completion time
Computer Science
Decoding
Delivery scheduling
drone delivery
Drone vehicles
Drones
Dynamic programming
Heuristic
Logistics
Operations Research
PDSTSP
Shortest-path problems
Traveling salesman problem
vehicle routing problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A recent evolution in urban logistics involves the usage of drones. In this article, we address a heuristic solution of the parallel drone scheduling traveling salesman problem, recently introduced by Murray and Chu. In this problem, deliveries are split between a vehicle and drones. The vehicle performs a classical delivery tour, while the drones are constrained to perform back and forth trips. The objective is to minimize completion time. We propose an iterative two‐step heuristic, composed of: a coding step that transforms a solution into a customer sequence, and a decoding step that decomposes the customer sequence into a tour for the vehicle and trips for the drones. Decoding is expressed as a bicriteria shortest path problem and is carried out by dynamic programming. Experiments conducted on benchmark instances confirm the efficiency of the approach and give some insights on this drone delivery system.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.21846