An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem
| Autor: | Nathalie Grangeon, Raïssa G. Mbiadou Saleu, Alain Quilliot, Laurent Deroussi, Dominique Feillet |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
Computer Networks and Communications Computer science 0211 other engineering and technologies 02 engineering and technology Travelling salesman problem Scheduling (computing) city logistics 0502 economics and business Vehicle routing problem dynamic programming 050210 logistics & transportation 021103 operations research 05 social sciences [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Drone Dynamic programming drone delivery Hardware and Architecture Shortest path problem heuristic vehicle routing problem PDSTSP Software Decoding methods Information Systems Coding (social sciences) |
| Zdroj: | Networks Networks, Wiley, 2018, 72 (4), pp.459-474. ⟨10.1002/net.21846⟩ Networks, 2018, 72 (4), pp.459-474. ⟨10.1002/net.21846⟩ |
| ISSN: | 0028-3045 1097-0037 |
| DOI: | 10.1002/net.21846⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text