A Competitive Heuristic Algorithm for Vehicle Routing Problems with Drones
| hal.structure.identifier | School of Management | |
| dc.contributor.author | REN, Xuan | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE] | |
| dc.contributor.author | FROGER, Aurélien | |
| hal.structure.identifier | Dipartimento di Electtronica, Informazione e Bioingegneria [Politecnico Milano] [POLIMI] | |
| dc.contributor.author | JABALI, Ola | |
| hal.structure.identifier | School of Management | |
| dc.contributor.author | LIANG, Gongqian | |
| dc.date.accessioned | 2024-04-04T02:32:45Z | |
| dc.date.available | 2024-04-04T02:32:45Z | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190410 | |
| dc.description.abstractEn | We propose a heuristic algorithm capable of handling multiple variants of the vehicle routing problem with drones (VRPD). Assuming that the drone may be launched from a node and recovered at another, these variants are characterized according to three axes, 1) minimizing the transportation cost or minimizing the makespan, 2) the drone may land and wait or not, and 3) single or multiple trucks each equipped with a single drone. One of our main algorithmic contributions relates to a subproblem of the VRPD, which we refer to as the fixed route drone dispatch problem (FRDDP). Given a sequence of customers being visited by a truck, the FRDDP determines a subset of customers to be visited by the drone. Solvingthe FRDDP exactly with dynamic programming entails a computational complexity of O(n^3), where n is the number of customers contained in the route. Considering that the FRDDP is very frequently solved in local search algorithms, we introduce a heuristic dynamic program (HDP) with a computational complexity of O(n^2) for each of the two FRDDP objectives. We embed HDPs in a hybrid variable neighborhood search algorithm, which we reinforce by developing filtering strategies based on the HDP. We benchmark the performance of our algorithm on nine benchmark sets pertaining to four VRPD variants resulting in 932 instances. Our algorithm computes 651 of 680 optimal solutions and identifies 189 new best-known solutions. | |
| dc.language.iso | en | |
| dc.subject.en | Drones | |
| dc.subject.en | Dynamic programming | |
| dc.subject.en | Variable neighborhood search | |
| dc.subject.en | Routing | |
| dc.subject.en | Heuristics | |
| dc.title.en | A Competitive Heuristic Algorithm for Vehicle Routing Problems with Drones | |
| dc.type | Document de travail - Pré-publication | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| hal.identifier | hal-04010250 | |
| hal.version | 1 | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-04010250v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=REN,%20Xuan&FROGER,%20Aur%C3%A9lien&JABALI,%20Ola&LIANG,%20Gongqian&rft.genre=preprint |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||