A-vehicle-routing-algorithm-for-the-distribution-o

AvehicleroutingalgorithmforthedistributionoffreshvegetablesandsimilarperishablefoodAnaOsvalda,*,LidijaZadnikStirnbaUniversityofLjubljana,ViaFaiti7,34170Gorizia,ItalybBiotechnicalFaculty,UniversityofLjubljana,VecnaPot83,1000Ljubljana,Slovenia,ItalyReceived26March2006;receivedinrevisedform19July2007;accepted20July2007Availableonline2August2007AbstractAnalgorithmforthedistributionoffreshvegetablesinwhichtheperishabilityrepresentsacriticalfactorwasdeveloped.Thispar-ticularproblemwasformulatedasavehicleroutingproblemwithtimewindowsandtime-dependenttravel-times(VRPTWTD)wherethetravel-timesbetweentwolocationsdependsonboththedistanceandonthetimeoftheday.Themodelconsiderstheimpactoftheperishabilityaspartoftheoveralldistributioncostsandaheuristicapproach,basedonthetabusearchisusedtosolvetheproblem.TheperformanceofthealgorithmwasverifiedusingmodifiedSolomon’sproblems.UsingparameterstypicaloftheSlovenianfoodmarket,differentscheduleswereachieved,givingimprovementsofupto47%reductioninperishedgoods.2007ElsevierLtd.Allrightsreserved.Keywords:Vehicleroutingproblem;Distribution;Perishablefood;Time-dependent;Lossofquality1.IntroductionThedifficultyinpreservingthenutritionalcharacteristicsoffreshfood-stuffsduringtransportationpresentsadirectproblemtofooddistributorswheretheperishabilityoftheproducerequiresittobehandledinwaysnotnecessarilyconducivetothetraditionalviewofcosteffectivedistribu-tionactivities.Freshvegetablesprovidearepresentativeexampleofperishablegoods;thenutritionvalueandtasteareattheirbestdirectlyafterharvesting,decreasingastimeelapsesuntilthefoodisspoilt.IntheSlovenianmarket,aquickdistributionoffreshvegetablesisrequiredsince,oftheapproximately151,571,000kgoffreshvegetablesconsumedperyear,between50%and70%areimported,mainlyfromItalyandSpain.WhentheyarriveinSlovenia,theyarefirstdeliveredtothedistributioncentersandthendistributedtothefinalconsumerswhocanacquiretheproductinopti-malconditionsonly48haftertheharvesting.Inthetrans-portationofvegetablesinsulatedvehiclesareusedforinternationaltransportationandnon-insulatedvehiclesforthefinaldistribution.Adetaileddescriptionoftheveg-etablesconsumed,thetypicalquantitiesandthedistribu-tionprocessarepresentedinVadnalandBratusˇa(2002),Krizˇaj(2002)andKnavs(2003).Tomeasurethedecreaseinthevalueofaloadoffreshvegetables,wedefinethe‘‘quality”oftheload.Thequalityis100%whentheloadcanbesoldentirelyatthecurrentmarketpriceandthequalityis0%whentheloadhaslostitscommercialvalue.Thelossofqualityinthetransporta-tionofthevegetablesrepresentsasignificantcostforthecompanies.BySlovenianlaw,therecognizedvalueofthelossis8%,butoccasionallythelosscanbehigherandhavebeenreportedbytransportationcompaniesasupto23%(Krizˇaj,2002).Goods-distributioncompaniestrytoreducebasicdistri-butioncostsbasedonthenumberofvehiclesused,totaldistance-traveledandthetotaltravel-time.Thestandardviewisthatinaddressingbasicdistributionissuesdistributorsalso0260-8774/$-seefrontmatter2007ElsevierLtd.Allrightsreserved.doi:10.1016/j.jfoodeng.2007.07.008*Correspondingauthor.Tel.:[phone].E-mailaddress:[e-mail](A.Osvald).(2008)285–295indirectlyreducethelossofquality.Inthispaper,wepres-entamodelfortherepresentationofthelossofqualityandconsideritaspartoftheoveralldistributioncosts.Wemodelthedistributionproblembetweenthedistributioncentersandthecustomers(retailers)asavehicleroutingproblemwithtimewindowsandwithtime-dependenttra-vel-times(VRPTWTD)wherethetravel-timesbetweentwolocationsdependsonboththedistanceandonthetimeofday.Tominimizetheoveralldistributioncost,theobjec-tivefunctionmustnotonlymodelthenumberofvehicles,thetotaldistance-traveledandthetotaltravel-time,butadditionallythelossofqualityoftheload.2.LiteraturereviewDifferentmethodshavebeendevelopedtosolvethevehicleroutingproblem(VRP)andvehicleroutingprob-lemwithtimewindows(VRPTW).Theroutesshouldbechosentominimizethetotaldistributioncost.AdetaileddescriptionoftheseandotherrelatedproblemsincludingaliteraturereviewofthemethodsareprovidedinTothandVigo(2002).IntheVRPTWweknowthelocation,thedemandandthedeliverywindow(theearliestandlatesttimethatthecustomerisabletoaccepttheload)ofeachcustomer.Thesolutionispresentedbyoneormoreroutes,eachassociatedtoonevehicle(aroutebeginsatthedepot,traversesasubsetofcustomersinaspecifiedsequenceandreturnstothedepot).Eachcustomermustbeassignedonlytoonevehicleandtheloadmustnotexceedthevehiclecapacity.Variousworksaddressthetransportationoffood-stuffs,dealingwithpertinentissuestoourproblem.Tar-antilisandKiranoudis(2001)analyzedthedistributionofthefreshmilk.Theyformulatedtheproblemasahet-erogenousfixedfleetvehicleroutingproblem;thisisaVRPwithvehiclesthathavedifferentcapacity.Athresh-old-acceptingbasedalgorithmwasdevelopedaimingtosatisfythedistributionneedsofthecompany,allowingthemtoscheduletheirdistributionmanytimesaweek.TarantilisandKiranoudis(2002)presentedareal-lifedis-tributionproblemoffreshmeatinanareaofthecityofAthens.Theyformulatedtheproblemasanopenmulti-depo