Afficher la notice abrégée

A branch-cut-and-price approach for the single-trip and multi-trip two-echelon vehicle routing problem with time windows

hal.structure.identifierLaboratoire de l'intégration, du matériau au système [IMS]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorMARQUES, Guillaume
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
hal.structure.identifierLaboratoire de l'intégration, du matériau au système [IMS]
dc.contributor.authorDESCHAMPS, Jean-Christophe
hal.structure.identifierLaboratoire de l'intégration, du matériau au système [IMS]
dc.contributor.authorDUPAS, Rémy
dc.date.accessioned2024-04-04T02:37:12Z
dc.date.available2024-04-04T02:37:12Z
dc.date.issued2022-03-16
dc.identifier.issn0041-1655
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/190785
dc.description.abstractEnThe paper studies the two-echelon capacitated vehicle routing problem with time windows, in which delivery of freight from depots to customers is performed using intermediate facilities called satellites. We consider the variant of the problem with precedence constraints for unloading and loading freight at satellites. In this variant allows for storage and consolidation of freight at satellites. Thus, the total transportation cost may decrease in comparison with the alternative variant with exact freight synchronization at satellites. We suggest a mixed integer programming formulation for the problem with an exponential number of route variables and an exponential number of precedence constraints which link first-echelon and second-echelon routes. Routes at the second echelon connecting satellites and clients may consist of multiple trips and visit several satellites. A branch-cut-and-price algorithm is proposed to solve efficiently the problem. This is the first exact algorithm in the literature for the multi-trip variant of the problem. We also present a post-processing procedure to check whether the solution can be transformed to avoid freight consolidation and storage without increasing its transportation cost. It is shown that all single-trip literature instances solved to optimality admit optimal solutions of the same cost for both variants of the problem either with precedence constraints or with exact synchronization constraints. Experimental results reveal that our algorithm can be used to solve these instances significantly faster than another recent approach proposed in the literature.
dc.language.isoen
dc.publisherINFORMS
dc.title.enA branch-cut-and-price approach for the single-trip and multi-trip two-echelon vehicle routing problem with time windows
dc.typeArticle de revue
dc.identifier.doi10.1287/trsc.2022.1136
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalTransportation Science
bordeaux.page1598-1617
bordeaux.volume56
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue6
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-03139799
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-03139799v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Transportation%20Science&rft.date=2022-03-16&rft.volume=56&rft.issue=6&rft.spage=1598-1617&rft.epage=1598-1617&rft.eissn=0041-1655&rft.issn=0041-1655&rft.au=MARQUES,%20Guillaume&SADYKOV,%20Ruslan&DESCHAMPS,%20Jean-Christophe&DUPAS,%20R%C3%A9my&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée