A guidedlocalsearchprocedureforthemulti-compartmentcapacitatedarc routing problem

In thispaper,weintroduceandstudythemulti-compartmentcapacitatedarcroutingproblem—an extensionoftheclassicalcapacitatedarcroutingproblem,butwheretherequirededgeshaveademand for differentproducts,andmulti-compartmentvehiclesareavailabletoco-distributethese commodities.Wepresentalocalsearchalgorithmthatexploitswell-knownmoves(2-opt,re-insert, relocate,exchangeandcross).Wetakeadvantageofspeeduptrickssuchasmarkingandneighbour lists, andwecombinetheprocedurewiththeguidedlocalsearchmeta-heuristicinordertoreachhigh quality solutions.Wereportonresultsfromextensivecomputationalexperiments.Ouraimistoreveal in whatsituationsco-distributionbypartitionedvehiclessavesinroutingcostsascomparedwith separatedistributionwithun-partitionedtrucks.Weexploresensitivitiesinkeyproblemcharacteristics including,thenumberofcommodities,thevehiclecapacity,thelocationofthedepotandrequired edges, thedensityofrequirededges,andthedemandpercommodityfortherequirededges.