二维指派模型

《二维指派模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、0引言二维不平衡指派问题模型及其求解李雪芹，丰伟(西南交通大学交通运输学院，成都610031)摘要：文章通过界定二维指派及不平衡指派问题，针对运输换装过程中货物批数和车辆数不等的情况，建立了二维不平衡指派问题的优化模型，给出了遗传算法进行求解的方法。关键词：指派问题；遗传算法；随机；编码中图分类号：U492文献标识码：A文章编号：1002—6487(2008)10-0159-03在运输过程中经常会遇到这样的问题：有多辆车需要装载多种货物。每辆车装载各种货物的成本不同，如何派车完成装载任务使成本最小，这便是指派问题。但在现实生活中，有时会遇上更复杂的指派问题。，定义

2、1设有K项运输任务．有m组车辆可承担这些任务，每组车辆的数目与任务数相同，每一项任务由每组各出一辆车共同完成。由于每辆车型号不同’各车辆完成运输任务的费用也不同，若要完成全郎任务，如何指派任务使费用最小就是in维指派问题。定义2在定义l中．取m=2．且每组车辆数量分别为I和J。如果I、J和K中至少有两个不相等．则此问题为二维不平衡指派问题。要求完成K项任务．且当有车辆没有分配任务时，则不允许有车辆分配多项任务。如果每辆车都指派了任务．还有剩余任务．则允许车辆分配多项任务。国内外文献对于一维指派问题研究较多，算法也比较成熟。如匈牙利算法【”、动态规划法【习、分枝定界

3、法【目等。对于一维不平衡指派问题有差额求解法f41，对于多维指派问题的研究主要是用动态规划法151。文献【6】用改进的匈牙利算法解决一维不平衡指派问题，文献【7】用近似算法解决指派问题，文献[8】用智能蚁群算法求解规模比较大的一维指派问题。从国内外研究现状来看．尚未见对二维不平衡指派问题的研究。本文试图建立二维不平衡指派问题模型，并给出求解算法。1I'al题描述及其数学模型设有K批货物需要从A地运输到N地，途经B地换装，A地可用车辆有I辆，B地可用车辆为J辆。每辆车一次只能运输一批货物，同一车辆运输不同批次的货物费用不同。如果I，J，K中有两个或者两个以上不相等，

4、如何优化车辆与货物的搭配。使运输费用最小。根据定义1及定义2，此问题是一个二维不平衡指派问题。根据I，J和K的大小可以分为几种情况。由于I和J是对应被指派的A和B两地的车辆数，因此I≤J与J≤I对于此问题来说是一样的。假设I≤J。以Y；和uj分别代表A地车辆i和B地车辆J运输的货物批数，Y。和Uj的表达式为：f0或1，当K≤I(表示车辆i最多可分配1项任务，最少可不分配任务)；yl-{1一[(K—I)／I】之间的整数，当I

5、uJ_{l一【(K．J)佃之间的整数，当J

6、，2，⋯J；(3)j=lk=1IJ∑∑x。k-l，k=1，2，⋯，K(4)i=1J=1IJ∑yF∑uj_K(5)l=1l2式(2)表示车辆A。运输货物批数为Y；，式(3)表示车辆B，运输货物批数为uj，式(4)表示每批货物必须且只能由A地某一车辆和B地某一车辆共同运输，式(5)表示A地车辆和B地车辆运输货物的总批数为K。基金项目：交通部行业联合科技攻关计划资助项目(2004353351060)统计与决策2008年第20期(总第262期)159该模型如用全枚举法和动态规划法求解．二维不平衡指派问题的复杂度约为O(K4)191，当K值较大时，计算量将会很大。为了减少运

7、算时间。采用遗传算法f10l进行求解。2遗传算法求解2．1编码及解码如果采取的编码在交叉变异中会产生大量不可行解，会降低算法求解的效率。本文为了使染色体在交叉及变异过程中不产生不可行解，对染色体实行二次编码。即对染色体进行一次编码之后，在前一次编码的基础上再次编码。遗传算法的解码过程与编码过程刚好相反。(1)遗传算法的一次编码A地第i辆车代码为i，B地第j辆车代码为j，第k批货物代码为k。染色体的长度为2K。染色体Chrom中第1～K各位置对应的编码数值为A地车辆代码．第K+I～2K各位置对应的编码数值为B地车辆代码。该染色体表示的指派任务可表述为：位置i和K+i

8、分别与A地