2007-Efficient evolutionary algorithm for the vehicle routing problem版本

《2007-Efficient evolutionary algorithm for the vehicle routing problem版本》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Ef¿cientEvolutionaryAlgorithmfortheVehicleRoutingProblemwithTimeWindows:EdgeAssemblyCrossoverfortheVRPTWYuichiNagataAbstract²Weproposeanevolutionaryalgorithm(EA)forbenchmarks.Thiscrossoverwasdesignedbyextendingedgethevehicleroutingproblemwithtimewindows(VRPT

2、W).Inassemblycrossover(EAX)[14][15],whichwasoriginallyparticular,acrossoveroperatorsuitableforsolvingtheVRPTWdesignedforthetravelingsalesmanproblem(TSP).arepresented.TheproposedcrossoverisdesignedbyextendingInthisresearch,wefurtherapplyEAXtotheVRPTW.edgeasse

3、mblycrossover(EAX)whichwasoriginallydesignedforthetravelingsalesmanproblem(TSP).Moreover,weproposeHowever,wefoundthatEAXdesignedfortheCVRPisnotanef¿cientmodi¿cationproceduretoeliminateviolationsofappropriateforsolvingtheVRPTWbecausethiscrossoverthecapacityco

4、nstraintsandthetimewindowconstraintsgeneratesinfeasiblesolutions(children)thatseriouslyviolatebecauseintermediatesolutionsgeneratedbyEAXviolatethesethetimewindowconstraint(thecapacityconstraintisalsoconstraints.TheEAiscomposedofEAX,themodi¿cationviolated).So

5、,wefurtherextendEAXtotheVRPTWsoprocedureandaverysimplelocalsearch.TheEAisappliedtothewell-knownGeringandHombergerbenchmarksforthethatchildrentendnottoviolatethetimewindowconstraint.VRPTW.TheEA¿ndsnewbest-knownsolutionsin119oftheMoreover,wealsoproposeanadditi

6、onalmodi¿cationproce-180instances(200±600customerbenchmarks).duretoeliminateviolationoftheconstraintswhenEAXgen-erateinfeasiblesolutions.Finally,weapplyanevolutionaryI.INTRODUCTIONalgorithm(EA)includingEAXandthemodi¿cationmethodLetanumberofcustomerswithknown

7、demandsandtimetothewell-knownGeringandHombergerbenchmarks[16]windowsbegiven.ThevehicleroutingproblemwithtimefortheVRPTW.windows(VRPTW)consistsof¿ndingaminimum-costrout-Theremainderofthispaperisorganizedasfollows.ingplanofaÀeetofvehicleswhichstartacommondepot

8、,First,theVRPTWisformulatedinsectionII.Andthendeliverloadstoallthecustomers,andreturntothedepot.weproposedEAXdesignedfortheVPPTWinsectionIIITherearetwoconstrains.Thetotaldemandofcustomersandthem