Afficher la notice abrégée

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierKorea Advanced Institute of Science and Technology [KAIST]
dc.contributor.authorHAN, Jinil
hal.structure.identifierIBM Research - Ireland
hal.structure.identifierElectronics and Telecommunications Research Institute [DaeJeon] [ETRI]
dc.contributor.authorLEE, Chungmok
hal.structure.identifierKorea Advanced Institute of Science and Technology [KAIST]
dc.contributor.authorPARK, Sungsoo
dc.date.accessioned2024-04-04T02:21:35Z
dc.date.available2024-04-04T02:21:35Z
dc.date.issued2013-08-14
dc.identifier.issn0041-1655
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/189588
dc.description.abstractEnWe consider a vehicle routing problem with uncertain travel times in which a penalty is incurred for each vehicle that exceeds a given time limit. A traditional stochastic programming approach would require precise knowledge of the underlying probability distributions of random data. In a novel approach presented here, we assume that only rough information on future travel times is available, leading to the multiple range forecasts of travel times and the probabilities of each range being realized. In this setting, we replace the point estimates of travel times on a scenario by range estimates. For each scenario, we then find the robust routes that protect the solution against the worst case within the given ranges, and finally we find the routes with the minimum expected cost. We propose a branch-and-cut algorithm to solve the problem and report computational results on both randomly generated and the well-known Solomon's instances. The results demonstrate that our approach is a favorable one when exact information of probability distributions is not available.
dc.language.isoen
dc.publisherINFORMS
dc.subject.envehicle routing
dc.subject.enstochastic travel times
dc.subject.enrobust optimization
dc.subject.enstochastic programming
dc.subject.enbranch and cut
dc.title.enA Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times
dc.typeArticle de revue
dc.identifier.doi10.1287/trsc.2013.0476
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalTransportation Science
bordeaux.page373-390
bordeaux.volume48
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue3
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00857871
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00857871v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Transportation%20Science&rft.date=2013-08-14&rft.volume=48&rft.issue=3&rft.spage=373-390&rft.epage=373-390&rft.eissn=0041-1655&rft.issn=0041-1655&rft.au=HAN,%20Jinil&LEE,%20Chungmok&PARK,%20Sungsoo&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