Extended guidedtabusearchandanewpackingalgorithmforthe two-dimensionalloadingvehicleroutingproblem

In thispaper,wedevelopanextendedguidedtabusearch(EGTS)andanewheuristicpackingalgorithm for thetwo-dimensionalloadingvehicleroutingproblem(2L-CVRP).The2L-CVRPisacombinationof two well-knownNP-hardproblems,thecapacitatedvehicleroutingproblem,andthetwo-dimensional bin packingproblem.Itisverydifficulttogetagoodperformancesolutioninpracticeforthese problems.Weproposeameta-heuristicmethodologyEGTSwhichincorporatestheoriesoftabusearch and extendedguidedlocalsearch(EGLS).Ithasbeenprovedthattabusearchisaverygoodapproachfor the CVRP,andtheguidingmechanismoftheEGLScanhelptabusearchtoescapeeffectivelyfromlocal optimum.Furthermore,wehavemodifiedacollectionofpackingheuristicsbyaddinganewpacking heuristictosolvetheloadingconstraintsin2L-CVRP,inordertoimprovethecostfunctionsignificantly. The effectivenessoftheproposedalgorithmistested,andprovenbyextensivecomputational experimentsonbenchmarkinstances.