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.:[phone];fax:[phone].E-mailaddress:[e-mail](B.-I.Kim).0305-0548/$-seefrontmatter
2005ElsevierLtd.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