求解粮食调运问题的两阶段优化算法
- 作者:admin 来源:网络 日期:2010-1-23 6:40:07
- 我国引进粮食物流理论的时间不长,人们对粮食物流在经济中的作用的认识也是近年来才开始,对粮食企业的现代物流管理的研究就更相对不足了。但是,根据我国的国情及资料表明,我国粮食调运的现状是:粮食运输体系各自为政,运输设施和配套设备落后,散粮汽车、火车运力不足,有时完全依赖社会车辆,一些运输资源也得不到有效地整合与利用,流通成本大大提高。流通不合理,中间环节多,效率低。这些都直接造成成本加大,市场竞争能力弱,形成了目前中国粮食物流成本普遍高于国外的局面。
粮食调运优化问题属于一种多回路运输问题,这个问题可简要描述如下:有N个目的地,每个目的地有一个确定的需求量,di,i=1,…,n,需要将粮食从供应地的粮库运输到各个目的地,共有K辆运输卡车,每辆卡车的装载量为Q。通常追求的目标是使所有卡车的总运输距离最短,也追求运输费用最少,但这两者并不是一致的。
有许多文献对这类运输问题进行了研究,有些采用了整数规划等传统方法,有些采用了遗传算法、禁忌搜索等较新的方法。通常求解该问题的方法可分为精确方法和启发式方法,还有最近出现的元启发式(metaheuristics)方法。http://www.dxlww.net 代写论文网
关于精确方法如文献[1]~[3],其测试问题的实例包含的目的地的数量太少,当目的地太多收稿日期:2008-06-30基金项目:“十一五”国家科技支撑计划重点项目(2008BADA8B03),“十一五”国家科技支撑计划(2006BAD08B01),河南省高校新世纪优秀人才支持计划(2006HANCET-15)作者简介:张秋闻(1982-),男,博士.时,则难以运算。虽然启发式和元启发式方法可以求解较大规模的运输问题如文献[4]~[6],但是这些文献都很少考虑到带有各种约束条件的实际运输问题,文献中考虑的问题与实际问题存在着一定的差距,提出的相关方法都不容易直接实现和实际应用,许多参考文献处理的只是简化的运输问题,只考虑到了整个运输路线的最短,而并没有考虑到异种车型或其它的最优化规则,更不用说与粮食调运优化问题相关的具体的约束条件,例如每条路线所到目的地的数量限制、部分卡车不能到达某些目的地,或者卡车未满载而带来的损失等。
粮食调度车辆的路线优化,是粮食调度优化中的一个关键环节。正确合理地安排散粮车辆的调度线路,可以有效地减少散粮车辆的空驶率,有效地增加散粮车辆的利用率。实现合理线路运输,从而达到科学化的粮食调运管理。本文根据粮食调运的突出特点,对粮食调运调度路径优化进行研究,提出了一个解决粮食调运优化问题的两阶段求解方法,该方法由图搜索算法和蚁群算法组成:在第一阶段,由图搜索算法产生所有可行的运输路线,由于在所有的可能的路线中大部分路线不满足问题的约束条件,在算法运行中,根据实际问题的约束对产生的搜索树进行剪枝,提高了图搜索算法的效率;在第二阶段,以追求总的运输成本最低为目标,采用蚁群算法,从第一阶段产生的可行路线集合中选取最佳路线。由于第一阶段产生的可行路线数量较小,所以第二阶段中粮食调运模型的变量和约束条件与问题求解的传统粮食调运模型比较大大减少,算法的运行速度快,且具有较好的鲁棒性。该算法经过粮食调运的实例测试,证明两阶段优化算法在粮食调运过程中具有良好的性能。
1 粮食调运优化模型1.1 传统的粮食调运模型记G=(V,E)为赋权图[7];E为边集,各粮库间的(距离)权值为dij。(1) V—粮库集合V={i},i=1,…,n,且i=0指初始粮库;(2) M—散粮车辆集合,M={k},k=1,…,m,(散粮车辆数) ;(3)qi—粮库i的粮食需求量,i∈V(i=0时q0=0);(4)dij—粮库i到粮库j的距离;(5)Qk—散粮车辆的载重量,Qk≥max{qi,i∈V}。Δxkij=1,如果散粮车辆k在访问粮仓i之后立即访问粮仓j0, 其它ykt=1,如果散粮车辆k在访问粮仓i0, 其它根据以上假设,可建立模型如下:minF={∑i∑j∑kdijxkij} (1)∑iykt=1,i∈v(2)∑ixkij=ykj,j∈v, k(3)∑jxkij=ykj,i∈v, k(4)∑i,j∈s×s∑xkij≤|S|-1,S v,2≤|S|≤n-1 (5)xkij∈(0,1),ykij=(0,1) (6)
这里(1)式为目标函数,即使用散粮汽车调运路径最短;约束式(2)保证每个散粮车辆对每个定点访问一次;约束式(3),(4),(5),(6)是为能形成回路。|S|为图G的定点个数。
该模型并没有考虑到粮食调运问题的全部因素,事实证明该模型是不适合的,主要基于以下原因:(1)效率不高:该模型使用N2个变量,并需要很长的计算机运行时间才能得出最优解。
(2)不完备:该模型不能考虑到实际问题的所有影响因素,并且这种情况影响到运行效率的测量,有些特殊情况下问题的部分限制条件不能被满足,例如不同装载量的卡车不能到达某些目的地。
(3)目标函数:问题的最终目标并不是使运输距离最短,真正需要的是使总的运输成本最低。这是该模型主要缺陷。最小化运输距离将导致许多未满载的车辆运输很短的路线。因此,需要一个更复杂的模型来使运输成本最小化。
1.2 模型改进
根据粮食调运遵循的原则,传统的粮食调运问题的目标函数不能达到最优,需要增加目标函数和调粮车辆的载重量限制的约束式,传统的粮食调运模型的目标函数只要求粮食调运路径最短,这只考虑到了粮食紧急调运应遵循的原则的一点,而粮食调运的高效率和低成本没有考虑进去,我们可以要求把运粮汽车数量最少,运输距离最小,这两个条件考虑进去则达到了粮食紧急调运遵循的原则。这样增加约束目标函数:minM=∑mk=1qi/Qk(7)minN={∑i∑j∑kdijxkijqi} (8)∑i=1qiykt≤Qk, k(9)
这里(7), (8)式为目标函数,即使用散粮汽车数量最少,运输距离最小;约束式(9)为调粮车辆限制。这样就三个目标函数(1),(7),(8),对于粮食调运问题的多个目标优化顺序为:首先最小化运粮车辆的行驶路径,即尽量减少到达所需的车辆数目;然后在所需运粮车的最少的规模上优化车辆总的行驶路程。
2 基于两阶段优化的粮食调运算法
2.1 图搜索算法优化
对于粮食调运问题,当目的地数量较多时,所有的可能运输路线的数量非常大。但是这些可能的路线当中只有一部分是可行的路线。这里提出的两阶段求解方法,首先根据粮食调运的约束条件用图搜索算法得出所有可行的运输路线,然后,构建一种新的模型,在这些可行的运输路线中进行选择,这样新模型具有较少变量,可以在合理的时间内进行求解。经过对粮食调运实际数据的仔细调研,得出如下的结论:
(1)散粮车辆的最大载重量是有限的。
(2)一条路线的长度不能超过一定路程,这也限制了运输路线的数量。
(3)由于载重量、道路狭小、桥梁等原因,限制了部分散粮车辆不能到达某些目的地。
考虑到这些限制条件,实际可行的路线将少很多。用一个简单的例子对图搜索算法进行说明:考虑到只
代写论文联系方式
联系QQ：904272800
联系信箱：904272800@qq.com
代写论文导航
客户、写手申请单
最新论文
热点论文
