资源描述：
《The Vehicle Routing Problem with Stochastic Demand and Duration Constraints》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、TheVehicleRoutingProblemwithStochasticDemandandDurationConstraintsAlanL.Erera,JuanC.Morales,andMartinSavelsberghTheSupplyChain&LogisticsInstituteGeorgiaInstituteofTechnologySchoolofIndustrialandSystemsEngineeringAtlanta,GA30332-0205March4,2010AbstractTim
2、econsiderationshavebeenlargelyignoredinthestudyofvehicleroutingprob-lemswithstochasticdemands,eventhoughtheyarecrucialinpractice.Weshowthattourdurationlimitscane ectivelyandecientlybeincorporatedinsolutionap-proachesthatbuild xed,orapriori,toursforsuchp
3、roblems.Wedosobyassumingthateachtourmustbeduration-feasibleforalldemandrealizations,anddeterminethemaximumdurationofagivendeliverytourbysolvingtheoptimizationproblemofanadversary.Acomputationalstudydemonstratestheapproach,andshowsthatenforcingtourduratio
4、nlimitsimpactsthestructureofnearly-bestsolutionsandmaycreatetheneedforadditionaltours.However,fortheinstancesconsidered,thepricepaidforrobustnessissmallastheincreaseintotalexpectedtourdurationismodest.1IntroductionThevehicleroutingproblemwithstochasticde
5、mand(VRPSD)hasbeenstudiedalongsidemoretraditionaldeterministicroutingproblemssinceinitialworkbyTillman(1969),buthasreceivedrelativelylessattention.Mostrecentworkfocuseson nding xed,orapriori,tours.Akeychallengeintheseproblemsismodelingtourfeasibility.Inp
6、ractice,itisimpossibleifnotextremelycostlytoensurefeasibilityofasetofaprioritoursforallpossibledemandrealizations.Thus,mostmodelsaremore
exibleandallowsomerecoursedecisions.Usually,thefeasibilityoftheaprioritoursetisdeterminedgivena xedrecoursepolicythat
7、speci estheactionstotakewheneveraninfeasibility,ortourfailure,occursduringoperations.1Themostpopularrecoursepolicystudiedintheliteratureisonethatwedenotedetour-to-depot:whenavehiclecapacityinfeasibilityarises,i.e.,whenthedemandofacustomercannotbesatis ed
8、giventhecurrentvehicleremainingcapacity,thevehiclemakesanreturntriptothedepottorestock(orunload)beforeresumingitstour.Variousheuristicandexactoptimizationapproachesforconstructingasetofaprioritoursminimizingexpectedcostsgi
