一种基于角色的信任管理框架设计

内容需要下载文档才能查看

EUROJTranspLogist(2013)2:187–229

DOI10.1007/s13676-012-0017-6

RESEARCHPAPER

Staticrepositioninginabike-sharingsystem:modelsandsolutionapproaches

TalRaviv?MichalTzur?IrisA.Forma

Received:2May2012/Accepted:12December2012/Publishedonline:8January2013

ÓSpringer-VerlagBerlinHeidelbergandEURO-TheAssociationofEuropeanOperationalResearchSocieties2013

AbstractBike-sharingsystemsallowpeopletorentabicycleatoneofmanyautomaticrentalstationsscatteredaroundthecity,usethemforashortjourneyandreturnthematanystationinthecity.Acrucialfactorforthesuccessofabike-sharingsystemisitsabilitytomeetthe?uctuatingdemandforbicyclesandforvacantlockersateachstation.Thisisachievedbymeansofarepositioningoper-ation,whichconsistsofremovingbicyclesfromsomestationsandtransferringthemtootherstations,usingadedicated?eetoftrucks.Operatingsucha?eetinalargebike-sharingsystemisanintricateproblemconsistingofdecisionsregardingtheroutesthatthevehiclesshouldfollowandthenumberofbicyclesthatshouldberemovedorplacedateachstationoneachvisitofthevehicles.Inthispaper,wepresentourmodelingapproachtotheproblemthatgeneralizesexistingroutingmodelsintheliterature.Thisisdonebyintroducingauniqueconvexobjectivefunctionaswellastime-relatedconsiderations.Wepresenttwomixedintegerlinearprogramformulations,discusstheassumptionsassociatedwitheach,strengthenthembyseveralvalidinequalitiesanddominancerules,andcomparetheirperfor-mancesthroughanextensivenumericalstudy.Theresultsindicatethatoneoftheformulationsisveryeffectiveinobtaininghighqualitysolutionstoreallifeinstancesoftheproblemconsistingofupto104stationsandtwovehicles.Finally,wedrawinsightsonthecharacteristicsofgoodsolutions.

T.Raviv(&)ÁM.TzurÁI.A.Forma

IndustrialEngineeringDepartment,TelAvivUniversity,69978TelAviv,Israel

e-mail:talraviv@eng.tau.ac.il

M.Tzur

e-mail:tzur@eng.tau.ac.il

I.A.Forma

e-mail:irisforma@eng.tau.ac.il;Irisf@afeka.ac.il

I.A.Forma

AfekaTelAvivAcademicCollegeofEngineering,BneiEfraim218,TelAviv,Israel

123

188T.Ravivetal.Keywords

problemBike-sharingsystemsÁStaticrepositioningÁPickupanddelivery

Introductionandproblemde?nition

Bike-sharingsystemsallowpeopletorentabicycleatoneofthemanyautomaticrentalstationsscatteredaroundthecity,usethemforashortjourneyandreturnthematanystationinthecity.Recentlymanycitiesaroundtheworldestablishedsuchsystemsinordertoencouragetheircitizenstousebicyclesasanenvironmentallysustainableandsociallyequitablemodeoftransportation,andasagoodcomplementtoothermodesofmasstransitsystems(mode-sharing).

Arentalstationtypicallyincludesoneterminalandseveralbicyclestands.Theterminalisadevicecapableofcommunicatingwiththeelectroniclockers,whichareattachedtothebicyclestands.Whenauserrentsabicycle,asignalissenttotheterminalthatthelockerhasbeenvacated.Ausercanreturnabicycletoastationonlywhenthereisavacantlocker.Allrentalandreturntransactionsarerecordedandreportedinrealtimetoacentralcontrolfacility.Thus,thestateofthesystem,intermsofthenumberofbicyclesandnumberofvacantlockersavailableateachstation,isknowntotheoperatorinrealtime.Moreover,operatorsofbike-sharingsystemsmakethisinformationavailabletotheusersonline.

Acrucialfactorinthesuccessofabike-sharingsystemisitsabilitytomeetthe?uctuatingdemandforbicyclesateachstation.Inaddition,thesystemshouldbeabletoprovideenoughvacantlockerstoallowtheuserstoreturnthebicyclesattheirdestinations.Indeed,oneofthemaincomplaintsheardfromusersofbike-sharingsystemsrelatestounavailabilityofbicyclesand(evenworse)unavailabilityoflockersattheirdestination,see,e.g.,ShaheenandGuzman(2011)andmediareportsBrusselNieuws(2010)andTusia-Cohen(2012).Persistentunavailabilityofbicyclesand/orlockersengendersdistrustamongthesystem’susersandcouldeventuallyleadthemtoabandonit.

Wemeasureuserdissatisfactionwiththesystemthroughtheexpectednumberofshortageevents.Suchaneventoccurswhenauserwhowishestorentabicyclearrivesatanemptystationorauserwhowishestoreturnabicyclearrivesatafullstation,withnovacantlockers.Inordertoreduceshortages,operatorsofbike-sharingsystemsareresponsibletoregularlyremovebicyclesfromsomestationsandtransferthemtootherstations,usingadedicated?eetoflighttrucks.Werefertothisactivityasrepositioningofbicycles.Thegoalsoftheoperatorsaretominimizethenumberofshortagesincurredinthesystemandthe?eet’soperationalcosts.Consequently,repositioningofbicyclesinthesysteminvolvesroutingdecisionsconcerningthevehicles,startingfromandreturningtothedepot,andinventorydecisionsconcerningbicyclesintherentalstations.Thelatterinvolvesdeterminingthenumberofbicyclestoberemovedorplacedineachstationoneachvisitofthevehicles.Ideally,theoutcomeofthisoperationwouldbetomeetalldemandforbicyclesandvacantlockers,butthismaynotbepossibleduetodemanduncertainty,capacityconstraintsofthevehiclesandthestations,andtheinherentimbalancesintherentingandreturnratesatthevariousstations.Theimbalanceissometimes123

Staticrepositioninginabike-sharingsystem:modelsandsolutionapproaches189temporary,e.g.,highreturnrateinasuburbantrainstationduringthemorningandahighrentingrateduringtheafternoon,orpersistent,e.g.,relativelylowreturnratesinstationslocatedontopofhills.Therefore,anewmodelingapproachisrequired;onethatwillcorrectlyrepresentapracticalobjectiveoftherepositioningoperation,relatedtotheusers’satisfactionwiththesystem.Towardthatwede?neapenaltyfunction,whichrepresentstheexpectednumberofshortagesatanyinventorylevelateachstation.Theuseofsuchanobjective,combinedwithnewmodelcharacteristics,istheessenceofthispaper.

Therepositioningoperationcanbecarriedoutintwodifferentmodes:oneisduringthenightwhentheusagerateofthesystemisnegligible;theotherisduringthedaywhenthestatusofthesystemisrapidlychanging.Werefertotheformerasthestaticbicyclerepositioningproblem(SBRP)andtothelatterasthedynamicbicyclerepositioningproblem(DBRP).Someoperatorsusestaticrepositioning,

´(2009).somedynamic,andsomeuseacombinationofthetwo,Calle

Inthispaper,wefocusonthestaticmodeofoperationwhichbene?tsfromapracticaladvantagebecauseitallowstherepositioning?eettotravelswiftlyinthecitywithoutcontributingtotraf?ccongestionandparkingproblems.Staticrepositioningisusefulforarrangingtheinventoryofbicyclesinthesystemtowardthenextday.Whencombinedwithdynamicrepositioning,itreducestheamountofworkrequiredinthelattermode.Thestaticproblemneedstobesolvedonceatthebeginningofeverynight,basedonthestatusofthesystematthattimeandthedemandforecastforthenextday.Whiletheproblemliesinthegeneraldomainofvehicleroutingproblems,itinvolvessomeuniquecharacteristicsthatrequireappropriatemodeling.Themodelwepresentinthispapergeneralizesexistingroutingmodelsfromtheliterature,asshowninthenextsection.

Weformallyde?netheSBRPasfollows.Theinputoftheproblemisasetofstations,withonedesignatedasthedepot;initialinventory,capacity,andaconvexpenaltyfunctionforeachstation;atravel-timematrixbetweenstations;andasetofnon-identicalcapacitatedrepositioningvehicles.Asolutionisde?nedbyarouteforeachvehicleandthequantityofbicyclestoloadorunloadateachstationalongthisroute.Theplannedroutesmustsatisfyatimeconstraint.Thelengthofeachrouteiscalculatedasthesumofthetraveltimesbetweenallpairsofconsecutivestationsalongtherouteplusthetimeneededforloadingandunloadingatthestations,whichdependsonthequantitiesofbicycleshandled.Thegoalistominimizeaweightedobjectivethatconsistsofthesumofthestations’penaltycostsandthetotaloperatingcostsofthevehicles.Thisproblemde?nitiongeneralizesourpreliminarywork,seeFormaetal.(2010).

Thepenaltyfunctionateachstationmayrepresentanyobjectiveoftheoperator,aslongasitisconvexintheendinginventoryofthestation.Weadvocatetheusageofpenaltyfunctionsthatrepresenttheexpectednumberofshortagesinastationduringthenextdaygivenitsinitialinventory,itscapacity,andthestochasticcharacteristicsofthedemandprocess.RavivandKolka(2012)presentanef?cientproceduretocalculatethesefunctionsandprovetheirconvexity.Forthesakeofcompleteness,wesummarizedtherelevantresultsfromtheirpaperinAppendixA.Formoredetails,thereaderisreferredtothatpaper.

ThecontributionofthispaperisinpresentinganewandpracticalapproachtomodelingtheSBRP.Itinvolvesde?ninganon-traditionalobjectivefunction,which

123

190T.Ravivetal.isrelatedtothesatisfactionofusersinthesystem.Italsoincludesothernewcharacteristicssuchasloadingandunloadingtimeswithinatimeconstrainedsetting.Basedonthisapproachwepresenttwomixedintegerlinearprogram(MILP)formulations,whichdifferfromeachotherintheirmodelingchoicesandunderlyingassumptions.Onthemethodologicalside,theaboveformulationsarestrengthenedbysomevalidinequalitiesanddominancerulesthatarelikelytobeusefulinotherroutingproblems,especiallythosethataregeneralizedbythiswork.Finally,weappliedourmethodsonavarietyoflargeinstancesbasedonrealdataandachievedsmalloptimalitygapswithinareasonabletime.

Therestofthispaperisorganizedasfollows:in‘‘Literaturereview’’,wereviewtheliterature,describerelatedworkfromseveralapplicationareasandidentifythegapsthatshouldbeaddressed.In‘‘Modelformulation’’,wepresentourmodelingapproachbyspecifyingtheunderlyingassumptions,elaboratingonthechosenobjectivefunction,andpresentingourmathematicalformulations.In‘‘Algorithmicenhancements’’,wediscussalgorithmicenhancementsthatareusefulinsolvingthemathematicalmodelseffectively.In‘‘Numericalexperiments’’,wedescribeournumericalexperiments,theresults,andtheiranalysis.Finally,in‘‘Conclusionsanddiscussion’’,wediscusspossibleextensionsanddirectionsforfurtherresearch.Literaturereview

Inthissection,we?rstreviewrecentstudiesonbike-sharingsystemsandinparticularontherepositioningoperationinthosesystems.Thenwediscusstherelationoftherepositioningproblemtoclassicalroutingandinventory/routingproblemsfromtheliterature.

Modernbike-sharingsystemshavebecomeprevalentonlyinthelastfewyears;therefore,theexistingliteratureanalyzingthesesystemsisrelativelynew.Therearevariousinterestingresearchquestionsconcerningtheestablishment,operationandanalysisofbike-sharingsystems.Indeed,someworksstudystrategicproblems,suchasShuetal.(2010)andLinandYang(2011)whoaddressthequestionofbikerentalstations’capacityandlocations.Otherspresentempiricalanalysis,e.g.,DeMaio(2009)andHampshireandMarla(2011).FrickerandGast(2012)studythesystem’sbehaviorandtheeffectofvariousload-balancingstrategiesontheirperformances.Theyconcludethatinasymmetricsystems,repositioningofbicyclesbytrucksisnecessaryevenwhenanincentivemechanismtoself-balanceitisputinplace.VogelandMattfeld(2010)presentastylizedmodeltoassesstheeffectofdynamicrepositioningeffortsonservicelevels.Theirmodelisusefulforstrategicplanningbutisnotdetailedenoughtosupportrepositioningoperations.

Severalapproachestomodelingandoptimizingtherepositioningproblemhaverecentlybeendeveloped.Thereareessentialdifferencesbetweenthemintheunderlyingassumptionsconcerningtheperceivedsystem’sbehaviorandtheproblem’sobjective,aswediscussnext.Benchimoletal.(2011)andChemlaetal.(2011)addressthestaticrepositioningproblem,assumingthatagiventargetinventorylevelexistsforeachstationinthesystemsothattheobjectiveoftherepositioningoperationistoachievethistargetatminimumtravelcost.Themethod123

Staticrepositioninginabike-sharingsystem:modelsandsolutionapproaches191bywhichthetargetlevelsareobtainedisnotspeci?ed.Sincenodeviationfromthetargetlevelisallowed,notimeconstraintisimposedontherepositioningoperation(otherwise,itmaynotbefeasible).AresultoftheseassumptionsisthattheproblemresemblesthedeterministicC-deliveryTSP(ChalasaniandMotwani1999)orasinglevehicle,singlecommoditypickupanddeliveryproblem(PDP),discussed

?anetal.(2012)extendtheabovestudiesbyallowingthe?nalbelow.Erdog

inventoryateachstationtobewithinapre-speci?edintervalinsteadofatagiventargetvalue.

Themodelspresentedinthispapergeneralizetheabove-mentionedstudiessincewedonotspecifyatargetinventorylevelorinterval,butratherallowreachinganyinventorylevelanduseaconvexpenaltyfunctiontoexpressitscost.Indeed,the

?anetal.(2012)(resp.,ChemlaSBRPcanbecastastheproblempresentedinErdog

etal.(2011))byselectingpenaltyfunctionsthatassignavalueofzeroforeach?nalinventorylevelinsidethedesiredinterval(resp.,atthetargetlevel)andaverylargenumberforeachinventoryleveloutsideit(resp.,differentfromit).

Contardoetal.(2012)presentamathematicalprogrammingformulationforthedynamicrepositioningproblem(DBRP)andusedecompositionschemestoobtainlowerboundsandfeasiblesolutions.Althoughtheirformulationbearssomesimilaritytoourtime-indexedformulation,see‘‘Time-indexedformulation’’,therearetwoimportantdifferences:?rst,theirsettingisdeterministicanddoesnottakeintoconsiderationthestochasticnatureofthedemandsforbicyclesandforlockerswhileinourmodelthisstochasticitycanbeexpressedbytheconvexpenaltyfunction.Second,ourmodelincludesloadingandunloadingtimes,whichareproportionaltothenumberofbicyclesloaded/unloaded,whereasContardoetal.(2012)donotrefertothesetimesanditisunclearwhetherandhowtheycanbeincorporatedintheirformulationorintheirsolutionmethod.Inpractice,loadingandunloadingtimescompriseamajorportionoftherepositioningtime;hence,theirinclusioniscrucialforacorrectrepresentationoftheproblemandforobtaininggoodrepositioningplans.

NairandMiller-Hooks(2011)useastochasticprogrammingapproachtoperformrepositioninginsharedmobilitysystems.Theirmodelassumesthatthecostofmovingobjects(bicyclesorcars)betweentwogivenstationsisknownandrepresentedbya?xedplus-linearfunction,sothatnoroutingconstraintsandcostsareconsidered.Thisassumptionmayberealisticfortheone-waycar-sharingsystemsthatmotivatedtheirwork,buttoosimplisticforthebicyclerepositioningproblemaddressedhere.Moreover,theirmodelcalculatesvehicleshortagesbasedonthenetdemandduringsomeplanningperiod,whichdoesnottakeintoconsiderationthedynamicsofthedemandduringthatperiod.Suchcalculationsmaybevalidonlywhenarelativelyshortplanningperiodisconsidered.

RavivandKolka(2012)showhowtocalculatetheexpectednumberofshortagesasafunctionoftheinventorylevelatthebeginningoftheday,whichcanbeusedinourmodeltorepresentthedynamicsofthedemand.Theirmethodrequiresasinputtheratesoftwoindependentnon-homogenousPoissondemandstreamsforusersseekingtorentbicyclesandusersseekingtoreturnbicyclesatasinglestation,duringsomeplanningperiod,e.g.,duringthenextday.Althoughtheirmodelconsidersonlyasinglestationsystem,theydemonstratethroughsimulationthat

123