组合运输的优化调度

2001年2月系统工程理论与实践第2期文章编号:1000-6788(2001 )02-0117-05组合运输的优化调度李军，郭强，刘建新(西南交通大学经济管理学院,四川成都610031)摘要:对多车场情况的非满载的小货运量运输问题进行了分析.提出采用组合运输方式可以提高车辆的使用效率,进而构造了由分组和连接构成的序列优化启发式算法,并用实例进行了验证.关键词:非满载; 分组;连接;行驶线路中图分类号: U116.2, 0221.1Optimal Scheduling onCombinatorial TransportationLI Jun, GUO Qiang, LIU Jian-xin(School of Economics and Management, Southwest Jiaotong University ,Chengdu 610031)Abstract In this paper, the vehicle-scheduling problem with non-full load at the caseof multiple depots is analyzed. The combinatorial transportation is presented in order toenhance the effectiveness of transportation utilizing a single vehicle. A sequentialheuristic algorithm is constructed, which consists of clustering and chaining. Lastly,the method is applied to a case study.Keywords non- full load; clustering; chaining ; vehicle routes1引言有多项货运任务,对每项任务,要求从发货点运送货物到收货点，已知某些任务的货运量小于车辆容量的二分之一,这时如果每项任务安排-辆车,则车辆处于不满载状态，造成车辆利用率不高.因而可考虑几项任务合起来用一辆车运输(货物可混装或车辆有分割仓前提下),即实行组合运输,-辆车在几个发货点装货,然后再到几个收货点卸货-般来说,几项任务的发货点和(或)收货点比较接近时,组合用一辆车运输才比较有利,这样的-些任务称为一组任务，一辆车完成 . -组内的所有任务后,在满足总行驶里程约束的前提下,可再考虑完成其它组的任务，即组与组之间进行一定的连接、这样大大提高了车辆的使用效率,使总发车数减少.问题可描述为:n项货物运输任务,编号为...n,对任务i,其发货点为u,收货点为v,货运量为g.共有m个车场可发出车辆.车辆容量为Q.存在一些任务,有g;SQ/2.2分组中国煤化工分组就是将位置比较靠近且货运量之和不大于2.1分组模型:MYHCNMHG各任务点的位置接近程度,可用各点与它们的重心距离来反映[。对一个组,有发货点重心和收货点重心两个指标.某一任务与-组的距离，应为此任务的发货点与所属分组的发货点重心距离和收货点与所，收稿日期7资助项目:国家自然科学基金(79700019)118系统工程理论与实践2001年2月属分组的收货点重心距离之和.设任务i的发货点坐标为(fa,fb,),收货点坐标为(sai,sb;).设组k的发货点重心坐标为(Fa,Jb,),收货点重心坐标为(san, sbn)定义分配变量如下:1任务i分配给组kXCki =0否则'minz=乙艺[fas- fa,)2+ (fb。- 16)°]”工n十22[(san- sa,)2 + (sbo- s),)9]1"zxu .> jgxe≤Q2r;=1 i= 1,.nxn=0 或2.2模型求解2.2.1 初始分组由于不同任务的发货、收货地点以及特性可能不同,合并在-起运输时,装卸车就具有-定的复杂性.-些任务虽然货运量可组合在. -起,但组合运输并不一定有利,因而分组也具有一定的复杂性、 为此,引入“人工容量”的概念,定义如下:Q;=Q.其中,β为系数,且0<β<1.可设计一定的分组规则,根据人工容量对任务进行初始分组. β可通过人机进行交互式调整,这样就可对不同任务的装卸车复杂性给予-定考虑,并估计了分组时的复杂性,增大了组之间调整的弹性.2.2.2组的调整 .采用动态聚类分析方法进行组的调整.聚类时,以初始分组作为聚类分析的初始分类,以组的重心作为聚类中心，按最接近原则将各任务进行聚类，判断分类是否合理的标准,是当前分类中各任务与它所属分类中心的距离是否是最近距离.需要注意的是,在按最接近原则聚类时,必须检查新的分类容量是否超过了车辆的实际容量.为了增加调整的弹性,初始分组是按人工容量得到的,而应用聚类方法修改分类时,应按实际容量进行.在进行组的调整时,可按下面步骤进行:1)以初始分组为初始分类;2)计算各类的发货点重心与收货点重心;3)计算各任务与各类的重心距离;4)检查各距离,若不存在与其它类距离比与当前自己所属分类距离更近的任务,则分类不变,得到最后分类,终止，否则,进行下一步;5)按最接近原则进行重新分类;6)计算各类的容量;7)若类容量在车辆实际容量限制内,则转回到不则切出空昌明制的类中,将距离该类重心最中国煤化工远的任务分给另-距它最近的类,回到6).若在此始分组,调整β的值,可值到不同的分组.MYHCNMHG3组内线路安排3.1初始线路形成3.1.1单独行骤樊撵点和收货点的线路分别对发货点和收货点应C-W节约算法求得各自的旅行商线路[2],然后再将哈密尔顿圈转换成哈密.第2期组合运输的优化调度119尔顿路,即两条有向线路.3.1.2发货点线路与收货点线路的连接由于分组是以各任务发货点和(或)收货点比较接近为基础的,因此，安排线路时.考虑车辆首先行驶完全部发货点后再驶向某一收货点,直至驶完全部收货点,目的是行驶的总距离最短、这样行驶线路的所有方案构成-棵有向树形图(图1).设组内共有m项任务,S为组的入点,它可向所有发货点u,ou..u.发车;由每一发货点u;为起始点向下可分成两枝,分枝结点即为行驶线路的发货点结束点u。和un;由每-发货点结束点向下可向所有收货点v,,...V发车;每一收货点起始点心向下又分成两枝,结点为收货点结束点vo,和Vr.在此采用动态规划方法,将已得到的发货点线路与收货点线路进行连接.根据动态规划原理,采用逆向递推方法进行初始线路音一M安排[3].整个过程分成五个阶段如下:阶段1组的入点S 至发货点起始点;s阶段2发货点起始 点至发货点终止点;u阶段3发货点终止点至收货点起始点;阶段4收货起始 点至收货点终止点.以,\1m以阶段的始点位置作为该阶段的状态,它既是该阶段某支路的起始点,又是前一阶段某支路的终点，设阶段pv好\的状态为sp.d,(sp)为决策变量,表示阶段p的状态变量为sp时选择的路径,D。(sp)为相应得允许决策集合. R。(sp，d,)表示在阶段p的状态sp时,采用策略dp时的阶段收图1树形图益,即相应的路径长度.设c(i,j)表示点i到点j的距离; L(i,j)表示以i为起始点,以j为终止点的旅行商线路的长度、各阶段的状态变量、允许决策集合和阶段收益分别示于表1中.设fp(sp)为阶段p的状态最优值,表示在阶段p的状态Sp到收货点终止点的最短距离,此动态规划的递推方程可写为fp(sp)= min [R,(sp,d,) + fp+l(sp+)]fs<(s)= 0f.(sn)即为所求的组内线路长,由fi(s1)确定的线路即为所求的初始线路.表1状态变量、允许决策集合和阶段收益pDp(sp)Rp(sprdp) .第一阶段s}(u;}第二阶段({u;|u;为发货点起始点}{u;|u;=uis，ur}L(u,aul)第三阶段.({u;|uj为发货点终止点}{v}c(uj,v)第四阶段{vklve为收货点起始点){v1 |v= VkerUh}L(ve+v)3.2组内线路的优化已安排的线路是基于先安排任务的发货点,再中国煤化工考虑在发货点间插入一些收货点,是否会使总行驶里程减少,这里利用or交指TYHCNMH G_设某点从当前位置中去掉的目标函数减少值.为............定位时的目标函数增加值为0x'.则当0x>Oz'时，重新定位有利.这里正向定位时，发货点只能在它的当前位置与收货点位置之间定位,收货点可以在当前位置之后的任一位置定位;反向定位时.发货点可以在当前位置之前的任一位置定位,收货点只能在它的当前位置与发货点位置戽调数据这是因为一项任务的收货点必须在其发货点之后出现.120系统工程理论与实践2001年2月4组间线路的连接把组与组进行连接,即把子线路连接起来以合并成完整的车辆路线.这里把每-组任务作为一项“任务”,忽略内部结构,仅考虑组内线路的起点与终点.利用C-W算法原理进行组的连接,类似于旅行商问题中非对称距离情况下的C-W算法[2].当有多个车场可收发空车时,遵循“就近发车,就近收车”的原则,即对每-组任务而言,由距离它的起点最近的车场发车,完成任务后回到距它的终点最近的车场.设一组任务i的起点为si.终点为t,组内线路长L..设有车场D.,D...D.可收发车,则连接子线路;和j时,比车辆单独行驶线路i和j的费用的节约值为.s(i,j)= mincDp; + L;十minc,D, + mincp, + Lj + minc,p,'mincD;一L;一C一L;一minc,pe= minc,Dg + mincDp;一Cts计算所有连接的“节约"值,然后根据“节约”值的大小进行连接，若对收发车有特殊要求,则按要求收发车.5实例分析有一组货运任务,编号为1,2,3,4,5,6,各自的货运量及相应的发货点和收货点坐标如表2所示.各任务用载重量10吨的车辆来完成.有三个车场,位置分别为D.(40,40),D2(20,40),D3(50.20).试安排车辆路线.表2各任务货运量 及位置任务i1234货运量(吨)5.22.51.81.50.5发货点坐标(10,40)(30,20)(50, 60)(60,40)(60,20)(40,20)收货点坐标(50,10)(20,50)(30,50)(50,40)(30 ,30)设β=0.85,则得到Qg=8.5(吨).得到初始分组如下:组一:任务1,任务2,任务6;组二:任务3,任务4.任务5.确定各组内的初始线路如下:us→u4→us→Us→v→Vz利用or交换法优化后,得到→V→U2→U2→llx→V8Us→us→Vs→tls→v→V3在组与组间连接后得到线路如下:D3→uls→us→U→us→v→U3中国煤化工，线路示于图2中,其中实线为车辆线路,虛线连接表TYHCNMHG6讨论初始分组是基于-定的规则进行的，由于问题结构.数据结构的不同而具有随机性,因此可设定不同的β值,得到多个分组,在进行组与组的连接时,同时考虑多个分组,从中选择最好的连接.但要注意,含有相同任务的羯者数搪能连接.第2期组合运输的优化调度12170 [605040●D:30204qD:4s1070中国煤化工图2MHCNMHG参考文献:[1] L库柏，U N勃哈特，LJ勒布朗，运筹学模型概论[M].魏国华,周仲良译，上海:上海科学技术出版社,1987.[2] 郭耀煌,李军，车辆优化调度[M].成都:成都科技大学出版社,1994.[3] 郭耀煙纺麩孱学原理与方法[M].成都: 西南交通大学出版社,1994. .