Waste-collection-vehicle-routing-problem-with-time

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

Computers&OperationsResearch33(2006)3624–3642∗,SeongbaeKimb,SuryaSahoobaDepartmentofIndustrialandManagementEngineering,POSTECH,Pohang,Kyungbuk,790-784,KoreabInstituteofInformationTechnology,Inc.,2204TimberlochPlaceSuite225,TheWoodlands,TX77380,USAAvailableonline21November2005AbstractInthispaper,weaddressareallifewastecollectionvehicleroutingproblemwithtimewindows(VRPTW)withconsiderationofmultipledisposaltripsanddrivers’lunchbreaks.Solomon’swell-knowninsertionalgorithmisextendedfortheproblem.Whileminimizingthenumberofvehiclesandtotaltravelingtimeisthemajorobjectiveofvehicleroutingproblemsintheliterature,herewealsoconsidertheroutecompactnessandworkloadbalancingofasolutionsincetheyareveryimportantaspectsinpracticalapplications.Inordertoimprovetheroutecompactnessandworkloadbalancing,acapacitatedclustering-basedwastecollectionVRPTWalgorithmisdeveloped.TheproposedalgorithmshavebeensuccessfullyimplementedanddeployedforthereallifewastecollectionproblemsatWasteManagement,Inc.AsetofwastecollectionVRPTWbenchmarkproblemsisalsopresentedinthispaper.Wastecollectionproblemsarefrequentlyconsideredasarcroutingproblemswithouttimewindows.However,thatpointofviewcanbeappliedonlytoresidentialwastecollectionproblems.Inthewastecollectionindustry,therearethreemajorareas:commercialwastecollection,residentialwastecollectionandroll-on-roll-off.Inthispaper,wemainlyfocusonthecommercialwastecollectionproblem.TheproblemcanbecharacterizedasavariantofVRPTWsincecommercialwastecollectionstopsmayhavetimewindows.ThemajorvariationfromastandardVRPTWisduetodisposaloperationsanddriver’slunchbreak.Whenavehicleisfull,itneedstogotooneofthedisposalfacilities(landfillortransferstation).Eachvehiclecan,andtypicallydoes,makemultipledisposaltripsperday.ThepurposeofthispaperistointroducethewastecollectionVRPTW,benchmarkproblemsets,andasolutionapproachfortheproblem.TheproposedalgorithmshavebeensuccessfullyimplementedanddeployedforthereallifewastecollectionproblemsofWasteManagement,theleadingproviderofcomprehensivewastemanagementservicesinNorthAmericawithnearly26,000collectionandtransfervehicles.2005ElsevierLtd.Allrightsreserved.Keywords:Wastecollection;Vehicleroutingproblemswithtimewindows;Capacitatedclustering∗Correspondingauthor.Tel.:+82542792371;fax:+82542792870.E-mailaddress:bkim@postech.ac.kr(B.-I.Kim).0305-0548/$-seefrontmatter2005ElsevierLtd.Allrightsreserved.doi:10.1016/j.cor.2005.02.045B.-I.Kimetal./Computers&OperationsResearch33(2006)3624–364236251.IntroductionWehavedevelopedandimplementedvariousvehicleroutingalgorithmsforWasteManagement,Inc.(WM),theleadingproviderofcomprehensivewastemanagementservicesinNorthAmericawithnearly26,000collectionandtransfervehicles(see[1]).Inthispaper,wepresentthealgorithmsforwastecollectionvehicleroutingproblemwithtimewindows(VRPTW)withconsiderationofmultipledumpsitelocationsanddrivers’lunchbreaks.Thewastecollectionbusinessisdividedintothreemajorareas:commercial,residentialandroll-on-roll-off(see[2]).Eachareaincludesmunicipalsolidwasteandrecyclingmaterial,andeachisverydifferentfromtheothers.Thecommercialwastecollectioninvolvesservicingcustomerssuchasstripmalls,restaurantsandsmallofficebuildings.EachcommercialrouteofWMmayservice60–400customers,withtwoorthreedisposaltripstodumpsiteseachday.Dependinguponthecustomerbase,thesamedrivermayvisitthesamecustomermultipletimesinoneweek.Theweeklyservicescheduleisfairlystatic,asmostcustomersdonotchangethefrequencyofserviceoften.Thecommercialcustomersmayhavetimewindows.Theresidentialwastecollectiongenerallyinvolvesservicingprivatehomes.Thenumberofhomesaresidentialroutemayservicevarieswidelyfrom150to1300homeseveryday.Thefrequencyofserviceperweekwillvarybasedontheclimate,geography,competitionandpriceofservice.Inthenorthernstates,itiscommontoservicearesidentialhomeonceperweek.Conversely,inthesouthernstates,itismoretypicaltoservicearesidentialhometwotimesperweek.Oncetheweeklyfrequencyisdeterminedforasetofroutes,theschedulerepeatsitselfeveryweek.TheserviceactivitiesforMondaywillrepeateverynon-holidayMonday.Theroll-on-roll-offcollectionintroducesadifferentroutingproblem.Thedifferentiatorbetweenroll-on-roll-offandcommercialisthesizeofthecontainer.Atypicalcommercialcontaineriseightlooseyards,whilearoll-on-roll-offcontainermayrangefrom20to40looseyardsandonlyonecontainermaybeservicedatatime.Notethat1cubicyardis0.765m3.Whilehaulingtheselargecontainers,itiscommonforeachcontainertobedisposedofandreturnedtotheoriginalcustomer’slocation.Tocomplicatetheproblem,manydifferentapproachesareusedtomakethisoperationmoreefficient.Oneexampleofservicingthecustomerwouldbetofirstdeliveranadditionalemptycontaineratthecustomerlocation,pickupthefullcontainer,traveltoadisposalfacilityandthendisposeofthecontents.Atthispoint,thevehiclemayserviceanothercustomerwiththesamesizecontainer.Thedifficultyariseswhenadriverisscheduledtoperformdifferenttypesofservicesthroughoutthedaytocustomerswithdifferentcontainersizesanddifferentservicerequ

1 / 19
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功