Show simple item record

Solving the robust CVRP under demand uncertainty

hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorPESSOA, Artur
hal.structure.identifierMethods, Algorithms for Operations REsearch [MAORE]
dc.contributor.authorPOSS, Michael
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorVANDERBECK, François
dc.date.accessioned2024-04-04T03:03:03Z
dc.date.available2024-04-04T03:03:03Z
dc.date.issued2018
dc.date.conference2018-06-03
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/193042
dc.description.abstractEnIn this paper, we propose a Branch-Cut-and-price algorithm for the robust counterpart of the classical Capacitated Vehicle Routing Problem (CVRP). The deterministic version of this problem consists of finding a set of vehicle routes to serve a given set of customers with associated demands such that the sum of demands served by each vehicle does not exceed its capacity, and each customer is served exactly once. The total travel cost, given by the sum of distances traversed by all vehicles must be minimized. Here, only customer demands are assumed to be uncertain. We consider two types of uncertainty sets for the vector of customer demands: the classical budget polytope introduced by Bertsimas and Sim (2003), and a partitioned budget polytope, proposed by Gounaris et al (2013) for the CVRP with uncertain demands. The method proposed in this paper uses a set partitioning formulation to solve the problem, where each binary variable determines whether a given route is included or not in the solution. It considers only the routes that satisfy the capacity constraints for all possible demand vectors allowed by the uncertainty polytope. The linear relaxation for this formulation is solved by column generation, where the pricing subproblem is decomposed into a small number of deterministic subproblems with modified demand vectors. This reformulation allows the use of state-of-the-art techniques such as ng-routes, rank-1 cuts, specialized labeling algorithms, fixing by reduced costs and route enumeration. As a result, we were able to solve all 47 open instances proposed by Gounaris et al (2013), the largest one having 150 customers.
dc.language.isoen
dc.source.title7th International Workshop on Freight Transportation and Logistics
dc.subject.enRobust Optimization
dc.subject.enBudgeted Uncertainty
dc.subject.enBranch-Cut-and-Price
dc.subject.enVehicle Routing
dc.title.enSolving the robust CVRP under demand uncertainty
dc.typeCommunication dans un congrès
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.conference.titleODYSSEUS
bordeaux.countryIT
bordeaux.title.proceeding7th International Workshop on Freight Transportation and Logistics
bordeaux.conference.cityCalgliari
bordeaux.peerReviewedoui
hal.identifierhal-01703181
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2018-06-08
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01703181v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=7th%20International%20Workshop%20on%20Freight%20Transportation%20and%20Logistics&rft.date=2018&rft.au=PESSOA,%20Artur&POSS,%20Michael&SADYKOV,%20Ruslan&VANDERBECK,%20Fran%C3%A7ois&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record