一体化集货和配送车辆路径问题的混合遗传启发式算法

《一体化集货和配送车辆路径问题的混合遗传启发式算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、万方数据第18卷第3期系统管理学报V01．18No．32009年6月JournalofSystems&ManagementJun．2009文章编号：1005—2542(2009)03—0338—06一体化集货和配送车辆路径问题的混合遗传启发式算法王志坚1’2，王晓博3，李一军1(1．哈尔滨工业大学管理学院，哈尔滨150001；2．二炮司令部，北京100085；3．黑龙江大学信息管理学院，哈尔滨150080)【摘要】为满足电子商务客户多样化和个性化的需求，建立多约束条件的一体化集货和配送车辆调度模型。针对模型特

2、点，采用混合遗传启发式算法求解。首先，采用自然数编码，可以使问题变得更简洁；用最佳保留选择法，以保证群体的多样性；用改进的顺序交叉算子避免优良基因片断在顺序交叉时被破坏，保证算法能够收敛到全局最优；其次，对混合遗传算法求得的精英种群进行禁忌搜索求解。通过实例计算表明，该算法好于单独使用遗传算法或是禁忌搜索算法。关键词：集货与配送的车辆路径问题；混合遗传算法；禁忌搜索算法；混合遗传启发式算法中图分类号：TP29文献标识码：AStudyonHybridGeneticHeuristicAlgorithmforVeh

3、icleRoutingProblemwithBackhaulsWANGZhi-jianl“，WANGXiao—bo3，LIYi-juYll(1．SchoolofManagement，HarbinInstituteofTechnology，Harbin150001，China；2．SecondArtilleryCommand，Beijing100085，China；3．SchoolofInformationManagement，HeilongjiangUniversity，Harbin150080，China)

4、[Abstract]Inordertosatisfywiththeindividualandvariousdemandofcustomerundere-commerce，weestablishvehicleschedulingwithpicking—deliverymodel．AccordingtOthecharacteristicsofmodel，hybridgeneticheuristicalgorithmisusedtogettheoptimizationsolution．Firstofall，weus

5、enaturalnumbercodingSOastosimplifytheproblem．WeretainthebestselectionSOastoguardthediversityofgroup．Im—provedordinalcrossoveroperatorscanavoiddestroyinggoodgenepartsduringthecourseofordinalcross—overSOthatthealgorithmcanbeconvergenttotheoptimizationaswhole．

6、Secondly，stockeliteadoptinggeneticalgorithmtakesthehybridgeneticalgorithmwithtaboosearchingalgorithm．Theemulationandcalculationprovethatitisbetterthanonlyusinggeneticalgorithmandtaboosearchingalgorithm．Keywords：vehicleroutingproblemwithbackhauls；hybridgenet

7、icalgorithm；taboosearchingalgorithm；hybridgeneticheuristicalgorithm随着电子商务的迅速发展。为满足客户个性化的需求，一体化集货与配送的车辆路径问题(Vehi—cleRoutingProblemwithBackhauls，VRPB)引起广泛重视。VRPB问题可分为2种类型：①取消对收稿日期：2008—04—07基金项目：西部交通科技资助项目(200439800063)；黑龙江省科技攻关项目(GB05D202—3)作者简介：王志坚(1972一)，男

8、，博士生。研究方向为系统仿真与优化。E—mail：wangzhijian626@163．corn万方数据第3期王志坚，等：一体化集货和配送车辆路径问题的混合遗传启发式算法339先配送后集货的限制，但在每个客户点，只进行单纯的集货或单纯的配送作业，本文将上述配送策略称为单向配送／集货策略；②不仅取消对先配送后集货的限制，而且允许同一客户点同时有集货和配送的需求，本文将上述策略称为一体化集货与配送策略。