多车型多品种货物配装优化问题的混合启发式算法

《多车型多品种货物配装优化问题的混合启发式算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第20卷第6期2011年12月运筹与管理OPERATl0NSRESEARCHANDMANACEMENTSCIENCEV01．20．No．6Dec．2011多车型多品种货物配装优化问题的混合启发式算法王晓博1，李一军2(1．黑龙江大学信息管理学院．黑龙江哈尔滨150080；2．哈尔滨工业大学管理学院。黑龙江哈尔滨150001)摘要：为满足客户多样化和个性化的需求，建立能充分、均衡利用装载工具的载重和容积的多品种、多车型货物配装模型，并从全局、整体最优上设计混合启发式算法求解。首先，采用实数序列编码，使问题变得更简洁；基于容重比平衡法构建初始解，提高了解的可行性；用基于排序的选择与最

2、佳保留相结合策略，保证群体的多样性；采用改进的非一致变异，加强染色体的局部搜索能力；其次，对遗传算法求得的精英种群再进行禁忌搜索，提高了搜索效率；最后，通过实例计算证明了上述模型和算法的有效性，并为大规模解决实际问题提供思路。关键词：运筹学与控制论；零散货物配装；混合启发式算法；精英种群；容重比平衡法中图分类号：F224．3l文章标识码：A文章编号：1007—322l(2011)06-000l·08StudyOnHybrldHeur-sliCSAIgOrithmforOptimalLOadingPrOblemOfMuIti-mOdeIandMuIti-CargOWANGXiao．

3、bo。，LIYi-jun2(1．＆^DoZ矿坳肌口fiD凡肘口n口geme眦，肌ffon鲋口昭踟洳巧妇，胁r6流l50080，C^讯口；2．Sc危oof矿M口n口ge一，nent，j了ar6fnJns￡缸n￡e矿7kc^nDlog，，，舶r6inl50001，C矗￡，h口)Abstract：Inordertosatisfytheindividualandvariousdemand8ofcustomers，weestablishamulti．modelandmulti—cargoloadingproblemmodel．Hyb“dheuristicalgorithmisusedtog

4、ettheoptimizationsolution．Firstly，weusesequenceofrealnumber8coding80astosimplifythepmblem．Onthebasisofcubage—weightbalancealgo—rithm，weconstmctaninitialsolutiontoimpmvethefeasibility．Throughadoptingstrategycombining80rtingop·tionswiththebe8tresen，ed，ween8urethediVe玛ityofpopulation．Weadoptthei

5、mproVednon—unif0珊mutationsoastoenhancelocalsearchabilityofchmmosomes．Secondly，theelitepopulationgeneticalgorithmseek8ta—boo8earch，toimprovethesearche侬ciency．Finally，anexampleisgiVentoillustratetheef艳ctiVenessofthemodelsandmethodsanditcanol-feranthoughtto8ettlethepracticalproblemonalarge8cale．

6、KeywOrds：operationsresearchandcybemetics；loadingproblemofmulticategor)rgoods；hybridheuristicalgo—rithm；stockelite；cubage-we培htbalanceO引言根据货物和车辆的数量，配装问题可以分为两大类。一是待装的货物相对有限，要求使用的车辆数目最少。二是装载车辆相对有限，要求充分利用现有车辆的容积和载重量，尽可能多载货物，使车辆的利用率最高。货物配装问题是一个具有复杂约束条件的组合优化问题，属于NP-hard问题。收稿日期：20lO-05．15基金项目：国家社会科学

7、基金资助项目(10cGL076)．黑龙江省教育厅科学技术研究项目(11551332)作者简介：王晓博(1973·)，男，黑龙江省哈尔滨人，博士，剐教授，项士生导师，研究方向为物流系统仿真；李一军(1957·)。男，黑龙江省哈尔痪人。‘溥士，教授。博士生导师．研究方向为信息管理与信息系统。2运筹与管理2011年第20卷配装问题的研究方法主要有精确算法⋯、启发式算法和智能优化算法。启发式方法只能给出问题的局部最优解，缺乏全局寻优能力，尤其求大规模问题时，效率不高"1。Bhattach