Mostrar el registro sencillo del ítem

A Competitive Heuristic Algorithm for Vehicle Routing Problems with Drones

hal.structure.identifierSchool of Management
dc.contributor.authorREN, Xuan
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorFROGER, Aurélien
hal.structure.identifierDipartimento di Electtronica, Informazione e Bioingegneria [Politecnico Milano] [POLIMI]
dc.contributor.authorJABALI, Ola
hal.structure.identifierSchool of Management
dc.contributor.authorLIANG, Gongqian
dc.date.accessioned2024-04-04T02:32:45Z
dc.date.available2024-04-04T02:32:45Z
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190410
dc.description.abstractEnWe 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.isoen
dc.subject.enDrones
dc.subject.enDynamic programming
dc.subject.enVariable neighborhood search
dc.subject.enRouting
dc.subject.enHeuristics
dc.title.enA Competitive Heuristic Algorithm for Vehicle Routing Problems with Drones
dc.typeDocument de travail - Pré-publication
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
hal.identifierhal-04010250
hal.version1
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-04010250v1
bordeaux.COinSctx_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


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem