Mostrar el registro sencillo del ítem

A new family of route formulations for split delivery vehicle routing problems

hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorBALSTER, Isaac
hal.structure.identifierUniversidade Federal da Paraiba / Federal University of Paraiba [UFPB]
dc.contributor.authorBULHÕES, Teobaldo
hal.structure.identifierUniversidade Federal de São Carlos [São Carlos] [UFSCar]
dc.contributor.authorMUNARI, Pedro
hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorPESSOA, Artur
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierFormulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]
dc.contributor.authorSADYKOV, Ruslan
dc.date.accessioned2024-04-04T02:37:07Z
dc.date.available2024-04-04T02:37:07Z
dc.date.issued2022-11-30
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190777
dc.description.abstractEnWe propose a new family of formulations with route-based variables for the split delivery vehicle routing problem with and without time windows. Each formulation in this family is characterized by the maximum number of different quantities of demand that can be delivered to a customer during a vehicle visit. As opposed to previous formulations in the literature, the exact delivery quantities are not always explicitly known in this new family. The validity of these formulations is ensured by an exponential set of non-robust constraints. We also explore a property of optimal solutions that allows us to specify a minimum delivery quantity based on customer demand and vehicle capacity, and this number is often greater than one. We use this property to reduce the number of possible delivery quantities in our formulations, improving the solution times of the computationally strongest formulation in the family. In addition, we propose new variants of non-robust cutting planes that strengthen the formulations, which are limited-memory subset-row covering inequalities and limited-memory strong $k$-path inequalities. Finally, we develop a branch-cut-and-price algorithm to solve our formulations enriched with the proposed valid inequalities, which resorts to state-of-the-art algorithmic enhancements. We show how to effectively manage the non-robust cuts when solving the pricing problem that dynamically generates route variables. Numerical results indicate that our formulations and BCP algorithm establish new state-of-the-art results for the variant with time windows since all benchmark instances with 50 customers and many instances with 100 customers are solved to optimality for the first time. Several instances of the variant without time windows are solved to proven optimality for the first time.
dc.language.isoen
dc.title.enA new family of route formulations for split delivery vehicle routing problems
dc.typeRapport
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
bordeaux.type.institutionInria Centre at the University of Bordeaux
hal.identifierhal-03900628
hal.version1
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03900628v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2022-11-30&rft.au=BALSTER,%20Isaac&BULH%C3%95ES,%20Teobaldo&MUNARI,%20Pedro&PESSOA,%20Artur&SADYKOV,%20Ruslan&rft.genre=unknown


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