Two-phase heuristicalgorithmsforfulltruckloadsmulti-depotcapacitatedvehicle routing problemincarriercollaboration

Collaborative transportation,asanemergingnewmode,representsoneofthemajordevelopingtrendsof transportation systems.Focusingonthefulltruckloadsmulti-depotcapacitatedvehicleroutingproblem in carriercollaboration,thispaperproposesamathematicalprogrammingmodelanditscorresponding graph theorymodel,withtheobjectiveofminimizingemptyvehiclemovements.Atwo-phasegreedy algorithm isgiventosolvepracticallarge-scaleproblems.Inthefirstphase,asetofdirectedcyclesis created tofulfilthetransportationorders.Inthesecondphase,chainsthatarecomposedofcyclesare generated. Furthermore,asetoflocalsearchstrategiesisputforwardtoimprovetheinitialresults.To evaluate theperformanceoftheproposedalgorithms,twolowerboundsaredeveloped.Finally,compu- tational experimentsonvariousrandomlygeneratedproblemsareconducted.Theresultsshowthatthe proposed methodsareeffectiveandthealgorithmscanprovidereasonablesolutionswithinanacceptable computational time.