组合运输的优化调度1

《组合运输的优化调度1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2001年2月系统工程理论与实践第2期　文章编号:100026788(2001)0220117205组合运输的优化调度李　军,郭　强,刘建新(西南交通大学经济管理学院,四川成都610031)摘要:对多车场情况的非满载的小货运量运输问题进行了分析,提出采用组合运输方式可以提高车辆的使用效率,进而构造了由分组和连接构成的序列优化启发式算法,并用实例进行了验证L关键词:非满载;分组;连接;行驶线路中图分类号:U116.2,O221.1aOptimalSchedulingonCombinatorialTransportationLI

2、Jun,GUOQiang,LIUJian2xin(SchoolofEconomicsandManagement,SouthwestJiaotongUniversity,Chengdu610031)AbstractInthispaper,thevehicle2schedulingproblemwithnon2fullloadatthecaseofmultipledepotsisanalyzed.Thecombinatorialtransportationispresentedinordertoenhancetheeffecti

3、venessoftransportationutilizingasinglevehicle.Asequentialheuristicalgorithmisconstructed,whichconsistsofclusteringandchaining.Lastly,themethodisappliedtoacasestudy.Keywordsnon2fullload;clustering;chaining;vehicleroutes1　引言有多项货运任务,对每项任务,要求从发货点运送货物到收货点L已知某些任务的货运量小于车辆

4、容量的二分之一,这时如果每项任务安排一辆车,则车辆处于不满载状态,造成车辆利用率不高L因而可考虑几项任务合起来用一辆车运输(货物可混装或车辆有分割仓前提下),即实行组合运输,一辆车在几个发货点装货,然后再到几个收货点卸货L一般来说,几项任务的发货点和(或)收货点比较接近时,组合用一辆车运输才比较有利,这样的一些任务称为一组任务L一辆车完成一组内的所有任务后,在满足总行驶里程约束的前提下,可再考虑完成其它组的任务,即组与组之间进行一定的连接L这样大大提高了车辆的使用效率,使总发车数减少L问题可描述为:n项货物运输任务,编号为1

5、,⋯,n,对任务i,其发货点为ui,收货点为vi,货运量为giZ共有m个车场可发出车辆,车辆容量为QZ存在一些任务,有giFQö2.2　分组分组就是将位置比较靠近且货运量之和不大于车辆容量的任务分成一组Z211　分组模型[1]各任务点的位置接近程度,可用各点与它们的重心距离来反映Z对一个组,有发货点重心和收货点重心两个指标Z某一任务与一组的距离,应为此任务的发货点与所属分组的发货点重心距离和收货点与所a收稿日期:1999206217资助项目:国家自然科学基金(79700019)©1995-2005TsinghuaTongfa

6、ngOpticalDiscCo.,Ltd.Allrightsreserved.118系统工程理论与实践2001年2月属分组的收货点重心距离之和Z设任务i的发货点坐标为(fai,fbi),收货点坐标为(sai,sbi).设组k的发货点重心坐标为(fak,fbk),收货点重心坐标为(sak,sbk)定义分配变量如下:1任务i分配给组kxki=0否则221ö2221ö2minz=66[fak-fai)+(fbk-fbi)]xki+66[(sak-sai)+(sbk-sbi)]xkikiki6gixkiFQi6xki=1i=1,⋯,

7、nkxki=0　或　1212　模型求解21211　初始分组由于不同任务的发货、收货地点以及特性可能不同,合并在一起运输时,装卸车就具有一定的复杂性Z一些任务虽然货运量可组合在一起,但组合运输并不一定有利,因而分组也具有一定的复杂性Z为此,引入“人工容量”的概念,定义如下:QB=BQ其中,B为系数,且0

8、行组的调整Z聚类时,以初始分组作为聚类分析的初始分类,以组的重心作为聚类中心,按最接近原则将各任务进行聚类Z判断分类是否合理的标准,是当前分类中各任务与它所属分类中心的距离是否是最近距离Z需要注意的是,在按最接近原则聚类时,必须检查新的分类容量是否超过了车辆的实际容量Z为了增加调整的弹性,